PK

PKBytes

Explore tracks
Chapter 12: Stacks and Stack-Based Algorithms
12.03Beginner / Intermediate6 topics20 min6 interactive animations

Expression problems

Stacks parse expressions: balanced parentheses and multiple bracket kinds, converting infix to postfix and prefix with the shunting-yard method, evaluating postfix expressions and the role of operator precedence and associativity.

Learning goals

  • Check bracket matching with a stack
  • Convert infix to postfix and prefix
  • Evaluate postfix expressions
  • Apply precedence and associativity rules correctly

Prerequisites

Implementations
12.03.1

Balanced parentheses

A string of parentheses is balanced when every opener is closed in the right order. Scan left to right: push each opener, and for each closer pop an opener (failing if the stack is empty). The string is balanced if the stack is empty at the end. For a single bracket type a counter is enough, but a stack generalises. O(n) time.

Run the balanced and unclosed-opener presets.

Java
1static boolean balanced(String s) {
2    int depth = 0;
3    for (char c : s.toCharArray()) {
4        if (c == '(') depth++;
5        else if (c == ')' && --depth < 0) return false;     // closer with nothing open
6    }
7    return depth == 0;
8}

Balanced brackets with a stack

Interactive · edit the input

Your input

Try

char[] s · length 6

{
[
(
)
]
}
012345
ReadingAlready checkedMatched pairMismatch

stack of openers (top is last)

empty
Setup

Push every opener; each closer must match the most recent unclosed opener, which is exactly the top of the stack.

Step 1 / 8
Java
1static boolean isBalanced(String s) {
2    Deque<Character> stack = new ArrayDeque<>();
3    for (char c : s.toCharArray()) {
4        if (c == '(' || c == '[' || c == '{') stack.push(c);              // remember the opener
5        else if (c == ')' || c == ']' || c == '}') {
6            if (stack.isEmpty()) return false;                            // a closer with nothing open
7            char open = stack.pop();                                      // the most recent opener must match
8            if (!matches(open, c)) return false;
9        }
10    }
11    return stack.isEmpty();                                               // leftover openers are unmatched
12}

Live state

No condition evaluated on this step
Execution trace (dry run table)Show 8 steps
StepLineStateWhat happens
1L2Push every opener; each closer must match the most recent unclosed opener, which is exactly the top of the stack.
2L4i=0 c='{' depth=1'{' opens: push it. Depth 1.
3L4i=1 c='[' depth=2'[' opens: push it. Depth 2.
4L4i=2 c='(' depth=3'(' opens: push it. Depth 3.
5L7i=3 c=')' depth=2')' closes '(' from index 2: pop. Depth 2.
6L7i=4 c=']' depth=1']' closes '[' from index 1: pop. Depth 1.
7L7i=5 c='}' depth=0'}' closes '{' from index 0: pop. Depth 0.
8L11return=trueEvery opener was closed in the right order and the stack is empty: balanced. O(n) time, O(n) space.
12.03.2

Multi-bracket matching

With several bracket kinds a counter is not enough: ([)] has matching counts but wrong nesting. Push each opener and require each closer to match the kind of the top opener. Characters that are not brackets are ignored. The stack depth is the nesting depth at any point.

The wrong-kind preset ([)] fails even though each kind balances on its own.

Java
1static boolean isBalanced(String s) {
2    Deque<Character> stack = new ArrayDeque<>();
3    for (char c : s.toCharArray()) {
4        if (c == '(' || c == '[' || c == '{') stack.push(c);
5        else if (c == ')' || c == ']' || c == '}') {
6            if (stack.isEmpty()) return false;
7            char open = stack.pop();
8            if ((c == ')' && open != '(') || (c == ']' && open != '[') || (c == '}' && open != '{')) return false;
9        }
10    }
11    return stack.isEmpty();
12}

Balanced brackets with a stack

Interactive · edit the input

Your input

Try

char[] s · length 6

{
[
(
)
]
}
012345
ReadingAlready checkedMatched pairMismatch

stack of openers (top is last)

empty
Setup

Push every opener; each closer must match the most recent unclosed opener, which is exactly the top of the stack.

Step 1 / 8
Java
1static boolean isBalanced(String s) {
2    Deque<Character> stack = new ArrayDeque<>();
3    for (char c : s.toCharArray()) {
4        if (c == '(' || c == '[' || c == '{') stack.push(c);              // remember the opener
5        else if (c == ')' || c == ']' || c == '}') {
6            if (stack.isEmpty()) return false;                            // a closer with nothing open
7            char open = stack.pop();                                      // the most recent opener must match
8            if (!matches(open, c)) return false;
9        }
10    }
11    return stack.isEmpty();                                               // leftover openers are unmatched
12}

Live state

No condition evaluated on this step
Execution trace (dry run table)Show 8 steps
StepLineStateWhat happens
1L2Push every opener; each closer must match the most recent unclosed opener, which is exactly the top of the stack.
2L4i=0 c='{' depth=1'{' opens: push it. Depth 1.
3L4i=1 c='[' depth=2'[' opens: push it. Depth 2.
4L4i=2 c='(' depth=3'(' opens: push it. Depth 3.
5L7i=3 c=')' depth=2')' closes '(' from index 2: pop. Depth 2.
6L7i=4 c=']' depth=1']' closes '[' from index 1: pop. Depth 1.
7L7i=5 c='}' depth=0'}' closes '{' from index 0: pop. Depth 0.
8L11return=trueEvery opener was closed in the right order and the stack is empty: balanced. O(n) time, O(n) space.
12.03.3

Infix-to-postfix

In postfix (reverse Polish) notation operators follow their operands, so no parentheses or precedence rules are needed to evaluate it. Dijkstra's shunting-yard algorithm converts infix: operands go straight to the output; an operator first pops every stacked operator of higher precedence (or equal precedence if it is left-associative) to the output and is then pushed; ( is pushed; ) pops until the matching (. At the end pop everything. O(n).

Convert 3+4*(2-1) and watch which operators wait on the stack.

Java
1static String toPostfix(String s) {
2    StringBuilder out = new StringBuilder(); Deque<Character> ops = new ArrayDeque<>();
3    for (char c : s.toCharArray()) {
4        if (Character.isDigit(c)) out.append(c);
5        else if (c == '(') ops.push(c);
6        else if (c == ')') { while (ops.peek() != '(') out.append(ops.pop()); ops.pop(); }
7        else {
8            while (!ops.isEmpty() && ops.peek() != '(' && (prec(ops.peek()) > prec(c) || (prec(ops.peek()) == prec(c) && c != '^')))
9                out.append(ops.pop());
10            ops.push(c);
11        }
12    }
13    while (!ops.isEmpty()) out.append(ops.pop());
14    return out.toString();
15}
16static int prec(char op) { return op == '^' ? 3 : (op == '*' || op == '/') ? 2 : 1; }

Expression conversion and evaluation with stacks

Interactive · edit the input

Your input

Try

char[] expression · length 9

3
+
4
*
(
2
-
1
)
012345678
ReadingConsumed

operator stack (top is last)

empty

output

empty
Setup

Shunting-yard: digits go straight to the output; operators wait on a stack until a weaker operator or a closing parenthesis forces them out.

Step 1 / 12
Java
1static String toPostfix(String s) {
2    StringBuilder out = new StringBuilder(); Deque<Character> ops = new ArrayDeque<>();
3    for (char c : s.toCharArray()) {
4        if (Character.isDigit(c)) out.append(c);                              // operands go straight to the output
5        else if (c == '(') ops.push(c);
6        else if (c == ')') { while (ops.peek() != '(') out.append(ops.pop()); ops.pop(); }
7        else {                                                                 // an operator
8            while (!ops.isEmpty() && ops.peek() != '(' && (prec(ops.peek()) > prec(c) || (prec(ops.peek()) == prec(c) && c != '^')))
9                out.append(ops.pop());                                         // stronger (or equal, if left-associative) goes first
10            ops.push(c);
11        }
12    }
13    while (!ops.isEmpty()) out.append(ops.pop());
14    return out.toString();
15}
16static int evalPostfix(String p) {
17    Deque<Integer> st = new ArrayDeque<>();
18    for (char c : p.toCharArray()) {
19        if (Character.isDigit(c)) st.push(c - '0');
20        else { int b = st.pop(), a = st.pop(); st.push(apply(c, a, b)); }     // the right operand was pushed last
21    }
22    return st.pop();
23}
24// infix to prefix: reverse the string, swap '(' and ')', run toPostfix with the pop test
25// 'prec(top) > prec(c) || (prec(top) == prec(c) && c == \'^\')', then reverse the result

Live state

No condition evaluated on this step
Execution trace (dry run table)Show 12 steps
StepLineStateWhat happens
1L2Shunting-yard: digits go straight to the output; operators wait on a stack until a weaker operator or a closing parenthesis forces them out.
2L4c='3' output=33 is an operand: append to the output.
3L8c='+' output=3'+' binds tighter than the stack top (or the stack has no operator): push it.
4L4c='4' output=344 is an operand: append to the output.
5L8c='*' output=34'*' binds tighter than the stack top (or the stack has no operator): push it.
6L5c='(' output=34'(' always goes on the stack.
7L4c='2' output=3422 is an operand: append to the output.
8L8c='-' output=342'-' binds tighter than the stack top (or the stack has no operator): push it.
9L4c='1' output=34211 is an operand: append to the output.
10L6c=')' output=3421-')' pops operators to the output until '(' is found (-), then discards the pair.
11L13output=3421-*+End of input: pop every remaining operator to the output.
12L14return="3421-*+"Postfix: "3421-*+". Operands keep their order and operators follow their operands.
12.03.4

Infix-to-prefix

In prefix (Polish) notation each operator comes before its operands. The simple method: reverse the infix string, swap every ( with ), convert with the shunting-yard algorithm but pop only on strictly higher precedence (plus equal precedence for the right-associative ^), then reverse the result. Alternatively build an expression tree and print it in preorder.

Choose Infix to prefix in the animation.

Java
1static String toPrefix(String infix) {
2    StringBuilder rev = new StringBuilder();
3    for (int i = infix.length() - 1; i >= 0; i--) {
4        char c = infix.charAt(i);
5        rev.append(c == '(' ? ')' : c == ')' ? '(' : c);
6    }
7    StringBuilder out = new StringBuilder(); Deque<Character> ops = new ArrayDeque<>();
8    for (char c : rev.toString().toCharArray()) {
9        if (Character.isDigit(c)) out.append(c);
10        else if (c == '(') ops.push(c);
11        else if (c == ')') { while (ops.peek() != '(') out.append(ops.pop()); ops.pop(); }
12        else {
13            while (!ops.isEmpty() && ops.peek() != '(' && (prec(ops.peek()) > prec(c) || (prec(ops.peek()) == prec(c) && c == '^')))
14                out.append(ops.pop());
15            ops.push(c);
16        }
17    }
18    while (!ops.isEmpty()) out.append(ops.pop());
19    return out.reverse().toString();
20}

Expression conversion and evaluation with stacks

Interactive · edit the input

Your input

Try

char[] expression · length 9

3
+
4
*
(
2
-
1
)
012345678
ReadingConsumed

operator stack (top is last)

empty

output

empty
Setup

Shunting-yard: digits go straight to the output; operators wait on a stack until a weaker operator or a closing parenthesis forces them out.

Step 1 / 12
Java
1static String toPostfix(String s) {
2    StringBuilder out = new StringBuilder(); Deque<Character> ops = new ArrayDeque<>();
3    for (char c : s.toCharArray()) {
4        if (Character.isDigit(c)) out.append(c);                              // operands go straight to the output
5        else if (c == '(') ops.push(c);
6        else if (c == ')') { while (ops.peek() != '(') out.append(ops.pop()); ops.pop(); }
7        else {                                                                 // an operator
8            while (!ops.isEmpty() && ops.peek() != '(' && (prec(ops.peek()) > prec(c) || (prec(ops.peek()) == prec(c) && c != '^')))
9                out.append(ops.pop());                                         // stronger (or equal, if left-associative) goes first
10            ops.push(c);
11        }
12    }
13    while (!ops.isEmpty()) out.append(ops.pop());
14    return out.toString();
15}
16static int evalPostfix(String p) {
17    Deque<Integer> st = new ArrayDeque<>();
18    for (char c : p.toCharArray()) {
19        if (Character.isDigit(c)) st.push(c - '0');
20        else { int b = st.pop(), a = st.pop(); st.push(apply(c, a, b)); }     // the right operand was pushed last
21    }
22    return st.pop();
23}
24// infix to prefix: reverse the string, swap '(' and ')', run toPostfix with the pop test
25// 'prec(top) > prec(c) || (prec(top) == prec(c) && c == \'^\')', then reverse the result

Live state

No condition evaluated on this step
Execution trace (dry run table)Show 12 steps
StepLineStateWhat happens
1L2Shunting-yard: digits go straight to the output; operators wait on a stack until a weaker operator or a closing parenthesis forces them out.
2L4c='3' output=33 is an operand: append to the output.
3L8c='+' output=3'+' binds tighter than the stack top (or the stack has no operator): push it.
4L4c='4' output=344 is an operand: append to the output.
5L8c='*' output=34'*' binds tighter than the stack top (or the stack has no operator): push it.
6L5c='(' output=34'(' always goes on the stack.
7L4c='2' output=3422 is an operand: append to the output.
8L8c='-' output=342'-' binds tighter than the stack top (or the stack has no operator): push it.
9L4c='1' output=34211 is an operand: append to the output.
10L6c=')' output=3421-')' pops operators to the output until '(' is found (-), then discards the pair.
11L13output=3421-*+End of input: pop every remaining operator to the output.
12L14return="3421-*+"Postfix: "3421-*+". Operands keep their order and operators follow their operands.
12.03.5

Postfix evaluation

Evaluate postfix with one stack: push operands; on an operator pop the two top values (the right operand is the one popped first), apply the operator and push the result. A valid expression leaves exactly one value. The division operator needs the operands in the right order, and Java's integer division truncates toward zero.

Choose Evaluate a postfix expression and try 23*54*+.

Java
1static int evalPostfix(String p) {
2    Deque<Integer> st = new ArrayDeque<>();
3    for (char c : p.toCharArray()) {
4        if (Character.isDigit(c)) st.push(c - '0');
5        else {
6            int b = st.pop(), a = st.pop();
7            st.push(switch (c) { case '+' -> a + b; case '-' -> a - b; case '*' -> a * b; default -> a / b; });
8        }
9    }
10    return st.pop();
11}

Expression conversion and evaluation with stacks

Interactive · edit the input

Your input

Try

char[] expression · length 9

3
+
4
*
(
2
-
1
)
012345678
ReadingConsumed

operator stack (top is last)

empty

output

empty
Setup

Shunting-yard: digits go straight to the output; operators wait on a stack until a weaker operator or a closing parenthesis forces them out.

Step 1 / 12
Java
1static String toPostfix(String s) {
2    StringBuilder out = new StringBuilder(); Deque<Character> ops = new ArrayDeque<>();
3    for (char c : s.toCharArray()) {
4        if (Character.isDigit(c)) out.append(c);                              // operands go straight to the output
5        else if (c == '(') ops.push(c);
6        else if (c == ')') { while (ops.peek() != '(') out.append(ops.pop()); ops.pop(); }
7        else {                                                                 // an operator
8            while (!ops.isEmpty() && ops.peek() != '(' && (prec(ops.peek()) > prec(c) || (prec(ops.peek()) == prec(c) && c != '^')))
9                out.append(ops.pop());                                         // stronger (or equal, if left-associative) goes first
10            ops.push(c);
11        }
12    }
13    while (!ops.isEmpty()) out.append(ops.pop());
14    return out.toString();
15}
16static int evalPostfix(String p) {
17    Deque<Integer> st = new ArrayDeque<>();
18    for (char c : p.toCharArray()) {
19        if (Character.isDigit(c)) st.push(c - '0');
20        else { int b = st.pop(), a = st.pop(); st.push(apply(c, a, b)); }     // the right operand was pushed last
21    }
22    return st.pop();
23}
24// infix to prefix: reverse the string, swap '(' and ')', run toPostfix with the pop test
25// 'prec(top) > prec(c) || (prec(top) == prec(c) && c == \'^\')', then reverse the result

Live state

No condition evaluated on this step
Execution trace (dry run table)Show 12 steps
StepLineStateWhat happens
1L2Shunting-yard: digits go straight to the output; operators wait on a stack until a weaker operator or a closing parenthesis forces them out.
2L4c='3' output=33 is an operand: append to the output.
3L8c='+' output=3'+' binds tighter than the stack top (or the stack has no operator): push it.
4L4c='4' output=344 is an operand: append to the output.
5L8c='*' output=34'*' binds tighter than the stack top (or the stack has no operator): push it.
6L5c='(' output=34'(' always goes on the stack.
7L4c='2' output=3422 is an operand: append to the output.
8L8c='-' output=342'-' binds tighter than the stack top (or the stack has no operator): push it.
9L4c='1' output=34211 is an operand: append to the output.
10L6c=')' output=3421-')' pops operators to the output until '(' is found (-), then discards the pair.
11L13output=3421-*+End of input: pop every remaining operator to the output.
12L14return="3421-*+"Postfix: "3421-*+". Operands keep their order and operators follow their operands.
12.03.6

Operator precedence

Precedence says which operator binds tighter (* before +); associativity says what happens between operators of the same precedence: - and / are left-associative (a - b - c = (a - b) - c) while exponentiation is right-associative (2^3^2 = 2^(3^2) = 512). The shunting-yard pop condition encodes both: pop while the stack top has higher precedence, or equal precedence and the new operator is left-associative.

Compare 2^3^2 (right-associative) with 8-3-2 (left-associative) in the animation.

OperatorPrecedenceAssociativity
^3 (highest)right
* /2left
+ -1left

Expression conversion and evaluation with stacks

Interactive · edit the input

Your input

Try

char[] expression · length 9

3
+
4
*
(
2
-
1
)
012345678
ReadingConsumed

operator stack (top is last)

empty

output

empty
Setup

Shunting-yard: digits go straight to the output; operators wait on a stack until a weaker operator or a closing parenthesis forces them out.

Step 1 / 12
Java
1static String toPostfix(String s) {
2    StringBuilder out = new StringBuilder(); Deque<Character> ops = new ArrayDeque<>();
3    for (char c : s.toCharArray()) {
4        if (Character.isDigit(c)) out.append(c);                              // operands go straight to the output
5        else if (c == '(') ops.push(c);
6        else if (c == ')') { while (ops.peek() != '(') out.append(ops.pop()); ops.pop(); }
7        else {                                                                 // an operator
8            while (!ops.isEmpty() && ops.peek() != '(' && (prec(ops.peek()) > prec(c) || (prec(ops.peek()) == prec(c) && c != '^')))
9                out.append(ops.pop());                                         // stronger (or equal, if left-associative) goes first
10            ops.push(c);
11        }
12    }
13    while (!ops.isEmpty()) out.append(ops.pop());
14    return out.toString();
15}
16static int evalPostfix(String p) {
17    Deque<Integer> st = new ArrayDeque<>();
18    for (char c : p.toCharArray()) {
19        if (Character.isDigit(c)) st.push(c - '0');
20        else { int b = st.pop(), a = st.pop(); st.push(apply(c, a, b)); }     // the right operand was pushed last
21    }
22    return st.pop();
23}
24// infix to prefix: reverse the string, swap '(' and ')', run toPostfix with the pop test
25// 'prec(top) > prec(c) || (prec(top) == prec(c) && c == \'^\')', then reverse the result

Live state

No condition evaluated on this step
Execution trace (dry run table)Show 12 steps
StepLineStateWhat happens
1L2Shunting-yard: digits go straight to the output; operators wait on a stack until a weaker operator or a closing parenthesis forces them out.
2L4c='3' output=33 is an operand: append to the output.
3L8c='+' output=3'+' binds tighter than the stack top (or the stack has no operator): push it.
4L4c='4' output=344 is an operand: append to the output.
5L8c='*' output=34'*' binds tighter than the stack top (or the stack has no operator): push it.
6L5c='(' output=34'(' always goes on the stack.
7L4c='2' output=3422 is an operand: append to the output.
8L8c='-' output=342'-' binds tighter than the stack top (or the stack has no operator): push it.
9L4c='1' output=34211 is an operand: append to the output.
10L6c=')' output=3421-')' pops operators to the output until '(' is found (-), then discards the pair.
11L13output=3421-*+End of input: pop every remaining operator to the output.
12L14return="3421-*+"Postfix: "3421-*+". Operands keep their order and operators follow their operands.

Practice ladder

Now try it yourself

Easy

  • Is “{[()]}” balanced? Is “([)]”?
  • Evaluate the postfix expression 53+2*

Medium

  • Convert 8-3-2 and 2^3^2 to postfix and explain the difference
  • Convert (1+2)*3-4 to prefix

Advanced

  • Extend the evaluator to multi-digit numbers and unary minus

Key takeaways

  • Bracket matching: push openers, pop on closers, end empty.
  • Shunting-yard turns infix into postfix with one operator stack.
  • Postfix evaluation: operands push, operators pop two and push the result.