Stacks and Queues

Balanced Parentheses

Walk a string of bracket characters. Push every opening bracket. On a closing bracket, pop and verify it matches; mismatch or empty-stack pop means unbalanced. At end of string, stack must be empty.

Algorithm

Canonical input "({[]})" (balanced) finishes with the stack empty and the result true.

stack push/pop Use a plain `std::vector<char>` (`push_back` / `pop_back` / `back`) as the stack.
matching map A small `std::unordered_map<char, char>` mapping each closing bracket to its expected opener keeps the lesson compact.

Basic Implementation

basic.cpp
Replay: real traced execution (multi-file project)
#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>

int main() {
    std::string text = "({[]})";
    std::unordered_map<char, char> pairs = {{')', '('}, {']', '['}, {'}', '{'}};
    std::vector<char> stack;
    bool balanced = true;
    for (size_t i = 0; i < text.length(); ++i) {
        char ch = text[i];
        if (ch == '(' || ch == '[' || ch == '{') {
            stack.push_back(ch);
        } else {
            if (stack.empty() || stack.back() != pairs[ch]) {
                balanced = false;
                break;
            }
            stack.pop_back();
        }
    }
    if (!stack.empty()) {
        balanced = false;
    }
    std::cout << (balanced ? "true" : "false") << std::endl;
    return 0;
}

  1. text ← ({[]})

    6int main() {7    std::string text = "({[]})";8    std::unordered_map<char, char> pairs = {{')', '('}, {']', '['}, {'}', '{'}};
    values this step({[]})text

  2. stack ← []

    8std::unordered_map<char, char> pairs = {{')', '('}, {']', '['}, {'}', '{'}};9std::vector<char> stack;10bool balanced = true;
    values this step[]stack

  3. balanced ← true

    9std::vector<char> stack;10bool balanced = true;11for (size_t i = 0; i < text.length(); ++i) {
    values this steptruebalanced

  4. stack ← [(]

    11for (size_t i = 0; i < text.length(); ++i) {12    char ch = text[i];13    if (ch == '(' || ch == '[' || ch == '{') {
    values this step[(]stack(ch

  5. stack ← [(, {]

    11for (size_t i = 0; i < text.length(); ++i) {12    char ch = text[i];13    if (ch == '(' || ch == '[' || ch == '{') {
    values this step[(, {]stack{ch

  6. stack ← [(, {, []

    11for (size_t i = 0; i < text.length(); ++i) {12    char ch = text[i];13    if (ch == '(' || ch == '[' || ch == '{') {
    values this step[(, {, []stack[ch

  7. stack ← [(, {]

    11for (size_t i = 0; i < text.length(); ++i) {12    char ch = text[i];13    if (ch == '(' || ch == '[' || ch == '{') {
    values this step[(, {]stack]ch

  8. stack ← [(]

    11for (size_t i = 0; i < text.length(); ++i) {12    char ch = text[i];13    if (ch == '(' || ch == '[' || ch == '{') {
    values this step[(]stack}ch

  9. stack ← []

    11for (size_t i = 0; i < text.length(); ++i) {12    char ch = text[i];13    if (ch == '(' || ch == '[' || ch == '{') {
    values this step[]stack)ch

  10. balanced ← true, stdout ← true

    25}26std::cout << (balanced ? "true" : "false") << std::endl;27return 0;
    values this steptruebalancedtruestdout[]stack

Complexity

  • Time: O(n)
  • Space: O(n) worst case

Implementation notes

  • C++: a plain std::vector<char> doubles as a stack via push_back and pop_back; avoid std::stack to keep the iteration shape visible.
  • The std::unordered_map<char, char> documents the closing -> opening map without leaking object identity into the replay.
  • The replay highlights the current character, shows the stack updating each frame, and surfaces the final balanced/unbalanced verdict.