Postfix Notation

Example

  • Infix: a + b

  • Postfix: ab+

  • Infix: a + b + c * d + e * f
  • Postfix: ab+ cd*+ ef*+

How to read:

((ab+) (cd* )+ (ef* )+)
1. (ab+) → a * b = A
2. (cd*) → c * d = B
3. (A + B) → (a * b) + (c * d) = C
4. (ef*) → e * f = D
5. (C + D) → (a * b + c * d) + (e * f)

Why?

  • Computers can calculate expressions simply by scanning left to right.
  • Parentheses are no longer needed.

Algorithm to Convert Infix → Postfix

  1. Put "(" into the stack → because it has the lowest priority.
  2. Read the infix expression from left to right.
  3. If you read an operand → print the operand itself.
  4. If you read an operator → pop all operators in the stack which have higher priority than the current operator, then push the current operator into the stack.
  5. At the end → pop all remaining operators.

Example Walkthrough

Infix:

a + b * c + d

Step-by-step process:

Input (in) Operator in Stack Compare Output (out)
a (   a
+ ( +   a
b ( +   ab
* ( + *   ab
c ( + *   abc
+ ( + pop * abc*+
d ( +   abc*+d

Result:

Postfix = abc*+d+

Which represents:

((ab c*) + (d+))

Updated: