Stacks and balanced parentheses

Why it matters

A stack is the simplest structure that remembers order. The undo command in a text editor, the back button in a browser and the way a program remembers where to return after a function call all work like stacks. In interviews, the balanced parentheses question is one of the first problems that tests whether you can turn a rule into code. By the end of this lesson you will build a stack from an array, use the standard library version, and check bracket strings such as ({[]}) in one pass.

Start with a pile of plates

Before any code, think about the problem a stack solves. You have items, and you will need to take them out again later. The question is which item comes out first. You can pick any rule you like. A data structure is a way to store items together with a rule for getting them back out. Different rules give different structures, and each rule makes some operations cheap and others impossible.

Imagine a stack of plates in a kitchen. A helper puts clean plates on the pile. When you need a plate, you take the top one. You do not reach under the pile for the bottom plate, because that would make the whole pile fall. The rule is simple: the last plate placed is the first plate removed. Programmers call this LIFO, which stands for last in, first out.

LIFO matters because many tasks need the most recent thing first. If you type a sentence, then type another, and then press undo, the editor must undo the newest change, not the oldest one. A stack is the natural way to keep that history. The newest change is on top, so it is the first one that comes off.

The idea: LIFO

Here is the rule in precise form. A stack is a collection where items are added and removed at one end only. That end is called the top. The formal name for adding an item is push, and the name for removing the top item is pop.

The four operations you need are these:

• push(x): put x on the top. The stack grows by one.
• pop(): remove the top item. The stack shrinks by one.
• top() (some languages call it peek): read the top item without removing it.
• empty(): report whether there are no items.

Each of these takes the same amount of work no matter how many items the stack holds. Computer scientists write this as O(1), read "order one" or "constant time". Constant time means the work does not grow with the number of items. Pushing onto a stack of one million items takes about as long as pushing onto a stack of three items.

Step through it below. Watch how each push puts a new item on the top and how each pop removes the item that was added most recently.

Watch for two things in the animation. First, the item you added last is always the one that leaves first. Second, the stack never needs to move the items already inside it. Only the top changes. That is why every operation is so fast.

Build a stack from an array

The easiest way to store a stack in C++ is an array plus a counter. Think of the array as a row of boxes numbered from 0. The counter n says how many boxes are in use. The top item is in box n - 1. Pushing writes into box n and then adds one to n. Popping subtracts one from n and reads the box that n now points at.

The array holds 10, 20 and 30 in boxes 0 to 2, with the counter n equal to 3 and the top at box 2

A class groups data and the functions that act on it. In C++ you write class Stack { ... };. Inside it, int data[CAP]; is a fixed block of memory with room for CAP integers, and int n = 0; is the counter. The word public: marks the functions that any code may call. Everything above it is private, which means only the class itself may touch it.

Here is the complete program. It is runnable, so you can press Run and see the output.

Press Run. The output is:

30
30
20
10
underflow

Here is what happens, line by line. After the three pushes, the array holds 10 20 30 in boxes 0, 1 and 2, and n is 3. The first top() reads box 2, which is 30. The first pop() subtracts one from n, making it 2, and returns box 2, which is 30. The second pop() returns 20 and makes n equal to 1. The top() reads box 0, which is 10. Then the program pops 10, so n becomes 0. The last pop() finds the stack empty and prints underflow.

Read the functions one at a time. push checks for a full array first. If there is room, data[n++] = x; does two things in one line. The n++ form uses the current value of n as the index, then adds one. So the value lands in the free box and the counter moves past it. pop works in the other order. data[--n] first subtracts one from n, then reads that box. The box at the old top index becomes free, and the value you read is the one you removed.

The top function is marked const because it only reads. The empty and full functions are also const. Marking a function const is a promise to the compiler that it will not change the object. The compiler checks that promise, so it is a useful safety habit.

What happens inside memory

The array lives in one block of memory. Its boxes sit side by side, so the computer finds box i by starting at the first box and moving forward i steps. That is why reading any box is O(1), and it is why an array is a good base for a stack.

Only the counter n tells you where the active part ends. The old values left in boxes after n are not erased. They are simply ignored. If you later push a new value, it overwrites the old one. This detail surprises beginners, and it is harmless, because your code must never read a box at or above n.

Overflow and underflow

Two error words come up with every stack. Overflow means you tried to push onto a stack that has no room. With a fixed array that is the full() check in the code above. Underflow means you tried to pop or read the top of an empty stack. The code prints underflow in that case.

A stack built on a linked list (a chain of small blocks, each pointing to the next) does not overflow, because it asks the system for memory one block at a time. Push becomes "add a block at the head" and pop becomes "remove the head block". Both are still O(1). The cost is that each block needs extra memory for its pointer. Either design is correct. The array version is faster in practice, because the boxes are packed together.

The standard library stack

In real code you should use std::stack from the <stack> header. It already handles memory and the counter for you. Notice one important difference: its pop() returns nothing. You read the value with top() first, and then call pop() to remove it.

Output:

2 2
1

The angle brackets in stack<int> say what the items are. stack<int> holds integers, and stack<char> holds single characters. You will see this pattern for every container in the standard library, and it is the reason the compiler checks the types of the values you push.

Two facts are worth knowing. First, std::stack is an adapter. It does not store items itself. By default it uses a std::deque (a double-ended queue, which you will meet at the end of this module) to hold them, and it only exposes the stack operations. Second, calling top() or pop() on an empty std::stack is undefined behaviour. That phrase means the C++ rules do not say what happens. The program might crash, print garbage, or seem to work. You must check empty() first.

Where stacks hide in real programs

Stacks are everywhere once you start looking:

• Undo. Each action goes on a stack. Undo pops the newest action and reverses it.
• Browser back button. Each page you visit is pushed. Going back pops the current page.
• Function calls. When a function calls another function, the computer saves where it was on a stack, the call stack. When the inner function returns, the saved position is popped. The recursion lesson in this course shows this in detail.
• Expression evaluation. Calculators and compilers read 2 + 3 * 4 in several ways, and stacks are how they keep the pending pieces while they work.

The last item leads to a useful exercise later in this lesson.

Balanced parentheses

Now the main problem. A string made of brackets is balanced when every opening bracket has a matching closing bracket of the same kind, and the pairs are properly nested. The three kinds are round ( ), square [ ] and curly { }.

Examples that are balanced: (), []{}, ({[]}), and an empty string. Examples that are not: (, )(, ([)], {[}].

The string ([)] looks like it has the right number of each bracket, but the order is wrong. The [ was opened after the (, so it must close before the (. The ) arrives while [ is still open, which breaks the rule. This is why counting brackets is not enough. You must check the order.

The last opened bracket must be the first one closed. That sentence describes a stack exactly. So the algorithm is:

1. Walk through the string from left to right.
2. When you see an opening bracket, push it.
3. When you see a closing bracket, the stack must not be empty, and its top must be the matching opening bracket. If so, pop it. Otherwise the answer is no.
4. At the end, the stack must be empty. Leftover openers mean some bracket was never closed.

The diagram below shows the stack state at each step for {[()]}.

Stack contents while checking the string with curly, square and round brackets, one row per character, ending with an empty stack

Notice what the stack remembers at each moment. It holds exactly the openers that are still waiting for a partner, in the order they were opened. The top is the most recent waiting opener, which is the only one that can be closed next without breaking the nesting. That one fact is the whole algorithm.

A slower way, and why the stack wins

Before the stack, many beginners try a different idea. Repeatedly delete the pairs (), [] and {} wherever they appear next to each other. If the string shrinks to nothing, it is balanced.

Try it on ([{}]). Remove {} to get ([]). Remove [] to get (). Remove () to get the empty string, so the answer is yes. This works, and it is a good way to understand what balance means. But it is slow. Each removal can require scanning the whole string again. In the worst case the work grows with the square of the length, which is O(n squared). For a string of 100,000 characters, that is about ten billion steps, far too slow.

The stack does the same job in one pass. Each character is looked at once. The stack is the memory of the pairs that have not been closed yet, so nothing needs to be rescanned. This is the reason the stack is the right tool: it turns a repeated search into a single left-to-right walk.

Worked example 1: a balanced string

Check {[()]} by hand. Keep a list that stands for the stack, with the top on the right.

The string ends with an empty stack, so it is balanced. Each closing bracket matched the top at the moment it arrived.

Worked example 2: an unbalanced string

Now check ([)].

The algorithm stops at step 3 and says no. It never needs to look at the last character.

Worked example 3: a string that is short but wrong

Check (]. Step 1 pushes (. Step 2 reads ], which is a closer. The stack is not empty, so the code looks at the top, which is (. A ] needs a [ on top, so the match fails and the answer is no. Beginners sometimes expect a special error for "wrong kind of bracket". You do not need one. The same check that handles order also handles the kind.

The checker in code

The next program turns the algorithm into C++. The first line of input is how many strings follow. Each string has no spaces, so cin >> s reads it as one word. Type the input into the Input box exactly as shown below, then press Run.

Input box, one value per line:

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

Output:

YES
NO
NO
NO

Read the function from top to bottom. The for (char c : s) loop visits each character. The if branch handles openers. The else if branch handles closers. The return false lines are the early exits. The final return st.empty(); performs the check at the end. The four strings show the four reasons a string can fail: wrong order (([)]), leftover openers (((), and a closer with nothing open ()). The first string passes all the checks.

The complexity is O(n) time, where n is the length of the string, because each character is handled once and each push and pop is O(1). The space is O(n) in the worst case, when every character is an opener, such as ((((.

Notice the cout << (balanced(s) ? "YES" : "NO") line. The parentheses around the condition are needed. Without them, << binds tighter than ?:, so the line is read as (cout << balanced(s)) ? "YES" : "NO". That prints a 1 or a 0 and throws away the text. This is a small precedence rule, and it is worth remembering whenever you combine output with a condition.

Evaluating an expression in postfix

A second classic use of a stack is evaluating postfix expressions. In normal writing, the operator goes between its numbers, as in 3 + 4. That is called infix. In postfix, the operator comes after its two operands. So 3 4 + means 3 plus 4, and 2 3 4 * + means 2 plus (3 times 4), which is 14.

Postfix needs no brackets or precedence rules. The evaluator is simple. Read tokens from left to right. A number goes on the stack. An operator pops the two numbers on top, applies the operator, and pushes the result. The rule works because the operator always needs the two most recent pending values, and those are exactly the two on top of the stack.

Here is the program. It reads one expression per line and prints each result. Type the three lines in the Input box.

Input box:

2 3 4 * +
5 1 2 + 4 * + 3 -
10 2 8 * + 3 -

Output:

14
14
23

Trace the second line by hand, because it is the best test of your understanding. The tokens are 5 1 2 + 4 * + 3 -. Push 5, push 1, push 2: the stack is 5 1 2, with 2 on top. The + pops 2 and then 1, and pushes 3, giving 5 3. Push 4: 5 3 4. The * pops 4 and 3 and pushes 12: 5 12. The + pops 12 and 5 and pushes 17: 17. Push 3: 17 3. The - pops 3 and then 17, computes 17 minus 3, and pushes 14. The answer is 14.

Notice the order of b and a. The right operand is on top, so it is popped first, and it goes into b. The left operand comes out second, and goes into a. Swapping them would give the wrong answer for subtraction and division. This is a common bug, and it is the reason the code names the popped values b (right) and a (left).

The program does not check for bad input. If a line has an operator with only one number before it, st.top() is called on an empty stack. In a real tool you would check the stack size before each pop and print an error. Practice exercise 5 asks you to add that check.

Debugging walkthrough: a checker that says yes too often

Real programs have bugs, and the way you find them is part of the skill. Here is a version of the checker with one mistake. It is runnable. Predict its output before you press Run.

Output:

(() -> YES
(( -> YES
() -> YES
)( -> NO

Three of the four answers are wrong. The string (() has one opener left over, and (( has two. The buggy function returns true at the end without asking whether the stack is empty. Only )( is right, because its first closer finds an empty stack.

The way to find this kind of bug is to trace one failing input by hand, the same way you traced ([)] above. Trace ((. Push, push, and the stack holds two openers. The loop ends with no closers at all. The function returns true. The trace shows you exactly which line was too generous. The fix is one line: replace return true; with return st.empty();.

A second habit helps. Before you trust a checker, test it on a string you know is balanced, one you know is unbalanced, and one that is almost right but has a single leftover. Those three tests catch most stack mistakes. The first two would not expose this bug, because () is balanced and ([)] is caught by the order check. Only the leftover test exposes it. That is why a good test set covers each kind of failure, not just the obvious ones.

Testing a stack program

A stack program is easy to test, because every input has one clear answer. Before you trust a checker, build a small table of inputs and write the expected answer next to each one. Every row should test a different kind of failure, so that a single passing row does not hide a bug. Here is a table for the bracket checker:

The empty string is the one input that needs care. The checker reads each string with cin >> s, and that skips empty words, so the empty string cannot be typed into the Input box. Test it by calling the function directly in a small main of your own. The correct answer is YES, because the loop does nothing and the stack is empty.

Notice that the table covers both kinds of failure. Some inputs fail while the loop is running, such as ) and ([)]. Others pass the loop and fail at the end, such as ( and ((). A checker that handles only the first kind is the buggy version from the debugging walkthrough. Include one row for each place the algorithm can return an answer.

It helps to write the expected answer before you run the program. If you run first and then copy the output into the table, you test nothing, because you are only checking that the program agrees with itself. Predicting the answer first forces you to trace the algorithm, and a mismatch then points at either your trace or your code.

What should a stack return when it is empty?

Our class returns -1 from pop when the stack is empty, and it prints a message. That choice is a sentinel value, a special number that means "no answer". A sentinel works only when the sentinel can never be a real item. If the stack may hold -1, the caller cannot tell an empty stack from a stored -1. The safe habit, used in the programs above, is to call empty() before top() or pop(), so the sentinel is never read.

Other designs exist. A function can return a pair, one part saying whether the answer is valid and the other holding the value. It can also throw an exception when the stack is empty. Each design has a cost. A pair makes every call site a little longer. An exception is slower and can be missed if nobody catches it. The standard library chose to make the caller check empty(), which is fast and keeps the rule visible. Learn that rule, because you will see it in most C++ code.

Common mistakes and the messages you will see

Mistake 1: forgetting the #include <stack> line. If you use stack<int> without the include, g++ reports this:

e1.cpp:2:5: error: 'stack' was not declared in this scope
    2 |     stack<int> s;
      |     ^~~~~

The fix is to add #include <stack> at the top. The caret points at the name the compiler does not know. Read the first error line first. The later errors are often follow-on messages caused by the first one.

Mistake 2: using the return value of pop(). In std::stack, pop() returns nothing, so this line does not compile:

error: void value not ignored as it ought to be
    7 |     int x = s.pop();
      |             ~~~~~^~

Write int x = s.top(); s.pop(); instead. Read first, then remove.

Mistake 3: a missing semicolon. A common typo looks like this:

error: expected ';' before 'cout'
    6 |     s.push(4)
      |              ^

The compiler points at the place where it expected the semicolon, which is the end of the line before the error. Fix the line above, not the line it names.

Mistake 4: calling top() on an empty stack. This one compiles, and it may run, which makes it dangerous. The C++ library has an optional safety mode. When you compile with -D_GLIBCXX_ASSERTIONS on g++, an empty std::stack stops with a message like this one, which is shortened here:

.../bits/stl_stack.h:260: ... top() ...: Assertion '!this->empty()' failed.

The program then ends with exit code 134. Without that mode, the program may print garbage or crash without a clear message. The rule is simple: test empty() before every top() and pop(). You will not need the safety mode to write correct code, but it helps you find the bug when the check is missing.

Mistake 5: a wrong final check. The buggy checker above shows this. Forgetting the last st.empty() lets (( pass.

Mistake 6: confusing order and count. A string can have the same number of each bracket and still be wrong, as in ([)]. Always check the order, which is the whole point of the stack.

Mistake 7: reversing the operands. In the postfix program, writing a - b with b taken first gives the wrong sign. Test subtraction and division with two numbers whose order matters, such as 10 3 -, which should print 7.

Interview questions and what they test

Balanced parentheses appears in interviews because it tests three things. Can you name the right data structure? Can you handle edge cases? Can you explain the cost?

Expect these follow-up questions:

• What is the complexity? Time O(n), because each character is processed once. Space O(n) in the worst case, when all characters are openers.
• Can you do it without a stack? For one bracket type, a counter is enough, because you only need to know how many openers are open. With several bracket types, the order matters, and a counter cannot remember which type is on top. So the stack is needed in general.
• What about the empty string? It is balanced. The loop does nothing and the stack is empty, so the answer is yes.
• What if the input has other characters? Decide the rule first. The usual choice is to ignore letters and digits, and say so before you code it.
• How many insertions would balance a string? Count the closers that found nothing to match, and add the openers left at the end. This is practice exercise 6.

Interviewers also watch how you talk. Say the rule aloud before you write code: "I push openers, and each closer must match the top." Then test it on three inputs before you say you are done.

Variations and edge cases

Test your code with these inputs, because many bugs live at the edges:

• An empty string: expected yes.
• A single opener, such as (: expected no. The final check catches it.
• A single closer, such as ): expected no. The empty-stack check catches it.
• Only closers, such as )]}: expected no.
• A long run of openers followed by closers, such as 500 ( then 500 ): expected yes, and the stack reaches a depth of 500.
• A mismatch deep inside a long string, such as ((((([))))): expected no, and the mismatch is found at the ) after the [.

Each variation changes one thing. When you add a new case, ask which line of the algorithm it exercises. A test that exercises no line of the code is not worth much.

Real-world uses

Compilers check that every { in your code has a }. Editors highlight matching brackets by walking the same algorithm. Parsers for markup languages use the same idea to match opening and closing tags, because a tag that opens later must close earlier. The core rule, the last thing opened must close first, appears in all of them.

Practice

1. Easy. Reverse a string using a stack. Push every character, then pop them into a new string. Try the word stack and check that you get kcats.

2. Easy. Read the output of this sequence without running it: push 4, push 9, pop, push 7, top, pop, pop. Write down each printed value. Only top prints in this sequence.

3. Easy. Check whether {[()()]} is balanced, step by step, with a table like the one in this lesson.

4. Easy. Explain in one sentence why counting the brackets is not enough to check ([)].

5. Medium. Add a check to the postfix evaluator so that an operator with fewer than two numbers on the stack prints error instead of crashing. Hint: check st.size() before each pop.

6. Medium. Write a function that returns the minimum number of brackets to add to make a string balanced. Hint: scan with a stack, and count the closers that find the stack empty. At the end, add the number of openers left on the stack.

7. Medium. Write longestBalancedPrefix, which returns the length of the longest prefix of a string that is balanced. Hint: the stack is empty exactly at the end of each balanced prefix.

8. Medium. Build a stack that also returns its minimum value in O(1) time. Hint: keep a second stack that pushes the smaller of the new value and the current minimum, and pops together with the main stack.

9. Hard. Explain why the balanced check takes O(n) time even though it contains a loop that can pop. Give the number of pushes and pops in terms of n.

10. Hard. Extend the checker so that * is a wildcard that may stand for an opener, a closer, or nothing. Describe the approach, and explain why one stack is no longer enough.

What you now know

• A stack is a LIFO collection with push, pop, top and empty, each O(1).
• You can build one from an array and a counter, or use std::stack, whose pop does not return a value.
• Reading top() or pop() on an empty stack is undefined behaviour, so check empty() first.
• Balanced brackets are checked by pushing openers and matching each closer against the top.
• Postfix evaluation uses the same idea: push numbers, and let each operator pop two.
• Check the order, not just the counts, and check for leftovers at the end.