Stacks

A stack stores values with last-in, first-out access: the newest value is the next one removed. Think of unfinished work nested inside other work. A function call must finish before its caller resumes, a closing bracket must match the most recent unmatched opening bracket, and undo must reverse the newest action first. A stack deliberately exposes fewer operations than a vector so this discipline is easy to maintain. We will recognize correctly nested brackets and explain why the same structure powers iterative DFS and expression evaluation.

Prerequisites: Loops, strings, functions, and Arrays and Vectors.

Build the idea

1. Learn the interface. Include <stack> and create stack<char> st;. push(x) adds x on top, top() reads that value, pop() removes it, and empty() checks whether a value exists. pop returns nothing. If a removed value is needed, copy top before popping. Calling top or pop on an empty stack is invalid. The C++ adaptor uses deque by default; it can also use a vector as its backing container. A stack does not offer arbitrary indexing or iteration because those operations are outside its interface.
2. Turn nesting into an invariant. Read the string from left to right. After any processed prefix, the stack contains precisely the opening brackets that have not yet been matched, ordered from oldest at the bottom to newest at the top. An opening bracket adds a new unfinished pair. A closing bracket must match the newest unfinished opening: otherwise the pairs cross or the types differ. Checking the top is therefore sufficient; searching deeper would accept invalid nesting. For ([{}]), the stack grows (, [, { and then shrinks in exactly the reverse order.
3. Trace a failing example. For ([)], the first two characters leave '(' then '['. When ')' appears, the newest opening is '['. Their types disagree, so reject immediately. Although there is a '(' deeper in the stack, matching it would cross the pending square-bracket pair. A closer with an empty stack also fails immediately. At the end, the stack must be empty: (() has no bad closing bracket, but one unfinished opening remains. These are three different failure conditions: extra closer, wrong type, and leftover opener.
4. Connect a stack to graph search. In iterative DFS, push the starting vertex; repeatedly remove a vertex and push newly discovered neighbors. Marking vertices when pushing prevents the same vertex from being inserted many times. A simple vertex stack finds reachability, but does not automatically reproduce recursive discovery and finishing order. To simulate recursion exactly, store frames containing both a vertex and its next-neighbor index. That frame represents the work the recursive function would resume after its child returns. Postorder computations such as subtree sizes depend on this distinction.
5. Connect a stack to arithmetic. A postfix expression such as 3 5 + 2 * needs no parentheses. Push each number. On an operator, pop the right operand first, then the left, compute, and push the result. After '+' the stack contains 8; after '*' it contains 16. The operand order matters for subtraction and division. In infix parsing, an operator stack delays lower-priority work until higher-priority work finishes. The bracket checker below teaches the same principle of postponing an operation until its nested work is complete.
6. Read and adapt the program. The helper matches checks one opener/closer pair without modifying storage. balanced owns a fresh stack for each test case and returns as soon as a mismatch is certain. Input is read as complete lines, so an empty line represents the empty bracket sequence and is valid. Spaces are ignored; any other non-bracket symbol is rejected. This explicit policy prevents accidental acceptance of arbitrary characters. For a problem allowing ordinary text, change that policy to ignore letters rather than silently relying on the current implementation.

C++17 implementation

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<stack>
#include<string>
#include<limits>
using namespace std;
bool matches(char open,char close){
    return (open=='('&&close==')')||(open=='['&&close==']')||(open=='{'&&close=='}');
}
bool balanced(const string&s){
    // Bottom-to-top: unmatched openings from oldest to newest.
    stack<char>pending;
    for(char c:s){
        if(c==' '||c=='\t'||c=='\r'){
            continue;
        }
        if(c=='('||c=='['||c=='{'){
            pending.push(c); // This opening now awaits a closer.
        }
        else if(c==')'||c==']'||c=='}'){
            if(pending.empty()||!matches(pending.top(),c)){
                return false;
            }
            pending.pop(); // Finish the innermost unmatched pair.
        }
        else{
            return false;
        }
    }
    return pending.empty(); // No unfinished openings may remain.
}
int main(){
    int t;
    if(!(cin>>t)||t<0){
        return 0;
    }
    cin.ignore(numeric_limits<streamsize>::max(),'\n');
    while(t--){
        string s;
        getline(cin,s);
        cout<<(balanced(s)?"YES":"NO")<<'\n';
    }
}

Complexity analysis

Each character is read once and each opening is pushed and popped at most once: O(L) time for length L and O(L) worst-case extra space. Deeply nested openings attain the space bound. With the default deque backing container, stack push/pop/top are O(1); a vector-backed stack has amortized O(1) push. Iterative DFS takes O(n+m) when every vertex and edge is processed a constant number of times.

Common mistakes and edge cases. Checking only whether the total counts of '(' and ')' match misses bad order and bracket types. Returning true before checking for leftover openings accepts incomplete sequences. Do not call top before checking empty. A simple stack traversal is not always an exact replacement for recursive DFS when finishing events matter. Recursive DFS uses the program's call stack and may overflow on a long path; an explicit stack gives control over storage.

Example input and output

First t ≥ 0, followed by exactly t lines containing brackets and optional spaces/tabs. A blank line is a valid test case. Output YES for correctly nested (), [], {} and NO otherwise.

Input

4
([]{})
([)]
(()

Output

YES
NO
NO
YES

The first sequence nests correctly. The second crosses bracket types. The third leaves one opening unmatched. The fourth test case is an empty line; doing nothing leaves an empty stack, so it is balanced.

Practical applications

Use stacks for balanced syntax, undo, postfix evaluation, iterative DFS, and processing nearest relevant elements. Monotonic stacks add an ordering invariant to the basic LIFO discipline and solve next-greater-element and histogram problems in linear time.

Check your understanding

Why is ([)] invalid even though opening and closing counts match?

Put it into practice

Modify the checker to print the 1-based position of the first invalid closing bracket, or the earliest unmatched opening if input ends too early.

Show a hint

Store pairs of bracket character and input position instead of characters alone.

← PreviousNext lesson →