Module 4 · Interactive topic

Expression Conversion

Infix · Postfix · Prefix — one stack does it all

People write infix (a + b * c), but a computer prefers postfix (a b c * +) or prefix (+ a * b c): no brackets and no priority rules are needed, because the order of the symbols says what to do first. A stack converts between all of them. Pick one of the six conversions and watch it work.

  • Infixa + b (operator in the middle)
  • Postfixa b + (operator after)
  • Prefix+ a b (operator before)
  • Stackholds what has to wait
Expression Conversion Ready
Infix
Stack (0 on it)
bottom
Output
  • Symbol being read
  • Pushed / output
  • About to pop

Ready

Comparisons 0 Shifts 0
Ready

Symbols: letters, numbers (up to 3 digits), + − * / ^ and brackets (infix only), up to 15 · Keyboard: ← → step · Space play / pause · R reset

How it works

Every operation, in plain steps

These are exactly the steps the visualizer animates.

Why does a stack help?

Infix (a + b * c) needs brackets and priority rules, so it is hard for a computer to read. Postfix (a b c * +) and prefix (+ a * b c) put every operator next to its operands, so the order of the symbols already says what to do first. A stack remembers whatever has to WAIT: the operators that must wait for a higher-priority operator (infix → postfix / prefix), or the operands that must wait for their operator (the other four conversions).

int prec(char op) {              // higher number = done first
    if (op == '^') return 3;     // works right to left
    if (op == '*' || op == '/') return 2;
    if (op == '+' || op == '-') return 1;
    return 0;
}

char stack[50];  int top = -1;   // push: stack[++top] = c;   pop: c = stack[top--];

Infix → Postfix

  1. Read left to right. An operand goes straight to the output.
  2. "(" is pushed. ")" pops operators to the output until the "(".
  3. An operator first pops every operator of higher priority (or equal, if it goes left to right), then it is pushed.
  4. At the end, pop everything left on the stack to the output.

Infix → Prefix

  1. Reverse the expression and swap each "(" with ")".
  2. Convert it like infix → postfix, but equal priorities do NOT pop (only ^ does).
  3. Reverse the output.
  4. The result is the prefix expression.

Postfix → Infix

  1. Read left to right. An operand is pushed.
  2. An operator pops two pieces: the first pop is the RIGHT operand, the second the LEFT one.
  3. Push (left op right) back as ONE piece.
  4. At the end one piece is left: the infix expression.

Postfix → Prefix

  1. Read left to right. An operand is pushed.
  2. An operator pops two pieces: first = right operand, second = left operand.
  3. Push op left right back as ONE piece.
  4. At the end one piece is left: the prefix expression.

Prefix → Infix

  1. Read RIGHT to left. An operand is pushed.
  2. An operator pops two pieces: the first pop is the LEFT operand, the second the RIGHT one.
  3. Push (left op right) back as ONE piece.
  4. At the end one piece is left: the infix expression.

Prefix → Postfix

  1. Read RIGHT to left. An operand is pushed.
  2. An operator pops two pieces: first = left operand, second = right operand.
  3. Push left right op back as ONE piece.
  4. At the end one piece is left: the postfix expression.

Priority and order

  1. ^ comes first, then * and /, then + and −.
  2. Equal priority: + − * / go left to right; ^ goes right to left.
  3. Brackets override priority.
  4. Postfix and prefix need no brackets at all.
Algorithm

Pseudocode

Language-independent steps. The visualizer shows the same logic in C, Python and Java.

1 INFIX-TO-POSTFIX(tokens)
2 for each token t, left to right
3 if t is an operand then output t
4 else if t = "(" then PUSH(t)
5 else if t = ")"
6 while top ≠ "(" do output POP()
7 POP() // throw the "(" away
8 else // t is an operator
9 while stack not empty and top ≠ "(" and
10 (prec(top) > prec(t) or (prec(top) = prec(t) and t ≠ ^))
11 output POP()
12 PUSH(t)
13 while stack not empty do output POP()
Complexity

How fast is each operation?

n = number of symbols in the expression. Every symbol is read once, and pushed and popped at most once, so every conversion takes O(n) time. The stack may hold up to n pieces, so it needs O(n) extra space. (We count each symbol as one step. The conversions that join pieces into longer strings also copy those strings, which a real program pays a little extra for.)

Operation Best Average Worst Speed
Push or pop O(1) O(1) O(1) Instant
Any of the six conversions O(n) O(n) O(n) Grows with n
Extra space (the stack) O(1) O(n) O(n) Grows with n

The same expression in all three notations

Infix Postfix Prefix
a + b a b + + a b
a + b * c a b c * + + a * b c
(a + b) * c a b + c * * + a b c
a − b − c a b − c − − − a b c
a ^ b ^ c a b c ^ ^ ^ a ^ b c

What waits on the stack?

Conversion Reads On the stack An operator…
Infix → Postfix left to right operators waits until higher priorities have left
Infix → Prefix left to right, on the reversed copy operators same, with the equal-priority rule flipped
Postfix → Infix / Prefix left to right pieces (operands) pops two pieces and joins them
Prefix → Infix / Postfix right to left pieces (operands) pops two pieces and joins them
Practice

Check your understanding

Answer each question — you will see the explanation straight away.

0 / 6 correct
Question 1

What is the postfix form of a + b * c ?

Question 2

While converting a + b * c to postfix, the symbol * arrives and + is on top of the stack. What happens?

Question 3

Why does a closing bracket ")" pop operators from the stack?

Question 4

Converting postfix to infix, an operator pops two pieces. The FIRST one popped is its…

Question 5

A prefix expression is read…

Question 6

What is * + a b c (prefix) written as infix?

Assessment

Stacks quiz

Test yourself: 5 questions, 70% to pass. Create a free account to take the quiz, save your progress and work towards the certificate.

Create a free account →
← Previous topic Stack Basics Next topic → Tower of Hanoi