Brackets and expressions

Brackets come in pairs, and the pair opened last must be closed first. That is exactly the stack rule. The same idea lets a program work out the value of a sum like 5 + (1 + 2) × 4 in one pass.

Matching brackets

Text is balanced if every opening bracket ( [ { has a matching closing bracket ) ] } after it, and pairs do not cross. {[()()]} is balanced. ([)] is not: the ) closes the ( while the [ inside it is still open.

Read the text from left to right with a stack:

• An opening bracket: push it.
• A closing bracket: the stack must not be empty, and its top must be the matching opening bracket. If so, pop it. If not, stop: the text is not balanced.
• At the end: the stack must be empty. Anything left was opened and never closed.

The step for a closing bracket is the one that needs care. A dict gives the opening bracket that each closing bracket needs:

pair = {')': '(', ']': '[', '}': '{'}

# c is a closing bracket
if not stack or stack.pop() != pair[c]:
    return False      # nothing is open, or the wrong kind is

not stack is checked first, so pop() never runs on an empty stack. After the loop, return not stack: the text is balanced only if nothing is left open. STAQ-P1 asks you to put the whole function together.

Each character is pushed at most once and popped at most once, so the time is O(n) for a text of n characters. The stack can hold up to n items, when every character opens a bracket.

Why a stack fits this job

Counting is not enough. Counting opens and closes of each kind would accept ([)], which has one of each. The order matters: a closing bracket must match the most recent bracket that is still open. “Most recent still open” is the top of a stack.

If the text has only one kind of bracket, a single counter does work: add 1 for (, take 1 for ), and the count must never go below 0 and must end at 0. A counter is a stack whose items are all the same, so only its size matters.

Postfix expressions

In normal writing an operator sits between its two numbers: 1 + 2. In postfix it comes after them: 1 2 +. Postfix needs no brackets and no rules about which operator goes first. 5 1 2 + 4 * + 3 - means 5 + (1 + 2) × 4 − 3, which is 14.

To work out a postfix expression, push each number. When an operator arrives, pop two numbers, apply the operator, and push the result. At the end, the one number left is the answer. Switch the figure above to “Postfix sum” to watch.

From normal order to postfix

Calculators and compilers read normal (infix) expressions by turning them into postfix first. The usual method is Dijkstra’s shunting-yard algorithm. It uses a stack for operators:

• A number goes straight to the output.
• An operator first pops to the output every operator on the stack that should be done before it (a stronger one, like * over +, or an equal one, since - and / work left to right). Then it is pushed.
• ( is pushed. ) pops operators to the output until the matching (, which is thrown away.
• At the end, pop everything left to the output.

For 5 + (1 + 2) * 4 the output is 5 1 2 + 4 * +. Each token is pushed and popped at most once, so this is also O(n).

Now try STAQ-P1, Brackets in order and STAQ-P2, The postfix calculator.