Step 6 of 6

Challenge: balanced brackets

Besides the main containers, the standard library has adapters: std::stack, std::queue and std::priority_queue. They wrap another container and allow only a few operations, which makes your intent clear.

A stack is last in, first out, like a pile of plates: you only touch the top.

Operation	Meaning
`push(x)`	put `x` on top
`top()`	look at the top element
`pop()`	remove the top element (returns nothing)
`empty()`, `size()`	as usual

Here a stack evaluates arithmetic written in postfix (reverse Polish) notation, where 3 4 + 2 * means (3 + 4) * 2:

#include <iostream>
#include <sstream>
#include <stack>
#include <string>

int eval_postfix(const std::string& expr) {
    std::stack<int> st;
    std::istringstream in(expr);
    std::string tok;
    while (in >> tok) {
        if (tok == "+" || tok == "-" || tok == "*") {
            int b = st.top(); st.pop();     // the right operand is on top
            int a = st.top(); st.pop();
            if (tok == "+") st.push(a + b);
            else if (tok == "-") st.push(a - b);
            else st.push(a * b);
        } else {
            st.push(std::stoi(tok));
        }
    }
    return st.top();
}

int main() {
    std::cout << eval_postfix("3 4 + 2 *") << "\n";
    std::cout << eval_postfix("10 2 3 * -") << "\n";
}

14
4

(std::istringstream splits the text into words the way std::cin would; the next module covers it properly. std::stoi converts a string like "42" into the int 42.)

Why a stack fits brackets

Brackets have the same shape as this problem: the most recent thing you opened is the first thing that must close. So:

For an opening bracket, push it.
For a closing bracket, the stack must not be empty, and its top must be the matching opener. Pop it.
At the end, the stack must be empty, or some opener was never closed.

Common mistakes

Calling top() or pop() on an empty stack. That's undefined behavior, so check empty() first. The string ")" must return false, not crash.
Forgetting step 3: "((" has no mismatches but isn't balanced.
Expecting pop() to return the value. Read top() first, then pop().

Your turn: write bool balanced(const std::string& s) for (), [] and {}. Other characters are ignored.

Previous: pair and tuple