Valid Brackets and Expression Evaluation

26 min · Intermediate

Brackets in a code line open and close in a nested order, just like function calls. A stack keeps the open ones in order, so it checks them in one pass. The same idea evaluates postfix and plain arithmetic.

The last opener must close first

In {[()]} the bracket opened last is (, and it must close first. A stack remembers the openers. Each closer must match the top.

Six steps reading the text { [ ( ) ] }. Each opener is pushed on the stack. Each closer pops the matching opener. The stack is empty at the end, so the brackets are valid.

Example 1 · Brute force: remove pairs again and again

Python

1def is_valid_slow(text):2    while "()" in text or "[]" in text or "{}" in text:3        text = text.replace("()", "").replace("[]", "").replace("{}", "")4    return text == ""5
6
7print(is_valid_slow("{[()]}"))8print(is_valid_slow("([)]"))

Output

True
False

What this code does

Removing touching pairs repeatedly leaves an empty text when the brackets are valid.
Each pass scans the text and there can be n / 2 passes, so the time is O(n squared). The stack does it in one pass.

Valid brackets in code

Push every opener. For a closer, the stack must not be empty and its top must be the matching opener. At the end the stack must be empty.

Python

1def is_valid(text):2    pairs = {")": "(", "]": "[", "}": "{"}3    stack = []4    for ch in text:5        if ch in "([{":6            stack.append(ch)7        elif ch in pairs:8            if not stack or stack.pop() != pairs[ch]:9                return False10    return not stack

Example 2 · Valid brackets with a stack

Python

1def is_valid(text):2    pairs = {")": "(", "]": "[", "}": "{"}3    stack = []4    for ch in text:5        if ch in "([{":6            stack.append(ch)7        elif ch in pairs:8            if not stack or stack.pop() != pairs[ch]:9                return False10    return not stack11
12
13for text in ["{[()]}", "([)]", "((", "())", "total(a[1]) + b"]:14    print(text, is_valid(text))

Output

{[()]} True
([)] False
(( False
()) False
total(a[1]) + b True

What this code does

([)] fails because ) meets [ on top. (( fails because the stack is not empty at the end.
Letters and spaces are ignored, so the same function checks a code line.

Example 3 · Watch the stack grow and shrink

Python

1stack = []2for ch in "{[()]}":3    if ch in "([{":4        stack.append(ch)5    else:6        stack.pop()7    print(ch, "".join(stack))

Output

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

What this code does

The depth rises to three and falls back to zero. This is the pattern drawn in the picture.
Each printed line shows the openers that are still waiting.

Example 4 · Minimum brackets to add

Python

1def min_add(text):2    open_count = 03    added = 04    for ch in text:5        if ch == "(":6            open_count += 17        elif open_count:8            open_count -= 19        else:10            added += 111    return added + open_count12
13
14print(min_add("())"))15print(min_add("((("))16print(min_add("()()"))

Output

1
3
0

What this code does

With one bracket type, a counter replaces the stack. An unmatched ) needs an opener, and each left over ( needs a closer.
This is O(n) time and O(1) space. With several bracket types you need the real stack.

A dict maps each closer to its opener. The function runs in O(n) time and uses O(n) space for the stack.

Postfix expressions

Postfix notation writes an operator after its two operands, so 3 4 + means 3 plus 4. It needs no brackets and one stack can evaluate it from left to right.

In 3 4 + 2 * each operator comes after its two numbers. Read left to right, push numbers, and let an operator pop two numbers and push the result.

Python

1def eval_postfix(tokens):2    stack = []3    for token in tokens:4        if token in "+-*":5            right = stack.pop()6            left = stack.pop()7            if token == "+":8                stack.append(left + right)9            elif token == "-":10                stack.append(left - right)11            else:12                stack.append(left * right)13        else:14            stack.append(int(token))15    return stack[0]

Example 5 · Evaluate a postfix expression

Python

1def eval_postfix(tokens):2    stack = []3    for token in tokens:4        if token in "+-*":5            right = stack.pop()6            left = stack.pop()7            if token == "+":8                stack.append(left + right)9            elif token == "-":10                stack.append(left - right)11            else:12                stack.append(left * right)13        else:14            stack.append(int(token))15    return stack[0]16
17
18print(eval_postfix("3 4 + 2 *".split()))19print(eval_postfix("10 2 8 * + 3 -".split()))

Output

14
23

What this code does

3 4 + 2 * is (3 + 4) * 2 = 14. 10 2 8 * + 3 - is 10 + 16 - 3 = 23.
Each token is pushed or used once, so the time is O(n).

Example 6 · The order of operands matters

Python

stack = [10, 4]right = stack.pop()left = stack.pop()print(left - right)print(right - left)

Output

6
-6

What this code does

The first pop is the right operand. For 10 4 - the answer is 10 - 4 = 6, not -6.
The same rule holds for division. Always take the right operand first.

The first value popped is the right operand. Subtraction and division depend on that order.

Infix with + - * /

For 2+3*4, multiplication must happen before addition. Keep a stack of terms to add. A * or / changes the top term at once. A + or - pushes a new signed term. The answer is the sum of the stack.

Python

1def calc(text):2    stack, num, op = [], 0, "+"3    for ch in text + "+":4        if ch.isdigit():5            num = num * 10 + int(ch)6        elif ch != " ":7            if op in "+-":8                stack.append(num if op == "+" else -num)9            elif op == "*":10                stack.append(stack.pop() * num)11            else:12                stack.append(int(stack.pop() / num))13            num, op = 0, ch14    return sum(stack)

Example 7 · Calculator for + - * /

Python

1def calc(text):2    stack, num, op = [], 0, "+"3    for ch in text + "+":4        if ch.isdigit():5            num = num * 10 + int(ch)6        elif ch != " ":7            if op == "+":8                stack.append(num)9            elif op == "-":10                stack.append(-num)11            elif op == "*":12                stack.append(stack.pop() * num)13            else:14                stack.append(int(stack.pop() / num))15            num, op = 0, ch16    return sum(stack)17
18
19print(calc("2+3*4"))20print(calc(" 14 - 6 / 4 "))21print(calc("100*2-50"))

Output

14
13
150

What this code does

The extra + at the end flushes the last number. Spaces are skipped.
14 - 6 / 4 is 14 - 1 = 13 because the division truncates.

int(a / b) truncates toward zero. This is fine for small numbers. Floor division // would round -7 / 2 down to -4.

Next step

Check your understanding

11 quick questions

1def is_valid_slow(text):2 while "()" in text or "[]" in text or "{}" in text:3 text = text.replace("()", "").replace("[]", "").replace("{}", "")4 return text == ""5 6 7print(is_valid_slow("{[()]}"))8print(is_valid_slow("([)]"))

1def is_valid(text):2 pairs = {")": "(", "]": "[", "}": "{"}3 stack = []4 for ch in text:5 if ch in "([{":6 stack.append(ch)7 elif ch in pairs:8 if not stack or stack.pop() != pairs[ch]:9 return False10 return not stack11 12 13for text in ["{[()]}", "([)]", "((", "())", "total(a[1]) + b"]:14 print(text, is_valid(text))

1def min_add(text):2 open_count = 03 added = 04 for ch in text:5 if ch == "(":6 open_count += 17 elif open_count:8 open_count -= 19 else:10 added += 111 return added + open_count12 13 14print(min_add("())"))15print(min_add("((("))16print(min_add("()()"))

Postfix expressions

Postfix notation writes an operator after its two operands, so 3 4 + means 3 plus 4. It needs no brackets and one stack can evaluate it from left to right.

In 3 4 + 2 * each operator comes after its two numbers. Read left to right, push numbers, and let an operator pop two numbers and push the result.

1def eval_postfix(tokens):2 stack = []3 for token in tokens:4 if token in "+-*":5 right = stack.pop()6 left = stack.pop()7 if token == "+":8 stack.append(left + right)9 elif token == "-":10 stack.append(left - right)11 else:12 stack.append(left * right)13 else:14 stack.append(int(token))15 return stack[0]

1def calc(text):2 stack, num, op = [], 0, "+"3 for ch in text + "+":4 if ch.isdigit():5 num = num * 10 + int(ch)6 elif ch != " ":7 if op in "+-":8 stack.append(num if op == "+" else -num)9 elif op == "*":10 stack.append(stack.pop() * num)11 else:12 stack.append(int(stack.pop() / num))13 num, op = 0, ch14 return sum(stack)

1def calc(text):2 stack, num, op = [], 0, "+"3 for ch in text + "+":4 if ch.isdigit():5 num = num * 10 + int(ch)6 elif ch != " ":7 if op == "+":8 stack.append(num)9 elif op == "-":10 stack.append(-num)11 elif op == "*":12 stack.append(stack.pop() * num)13 else:14 stack.append(int(stack.pop() / num))15 num, op = 0, ch16 return sum(stack)17 18 19print(calc("2+3*4"))20print(calc(" 14 - 6 / 4 "))21print(calc("100*2-50"))