Skip to main content

Polish notation and postfix conversion

Short answer

Polish (prefix) places operator before operands; reverse Polish (postfix) places after, removing brackets. Postfix of (a+b*c+(d*e+f)*g) is abc*+de*f+g*+.

What is polish notation and reverse polish notation? Convert the following expression to postfix expression using Stacks: P: (a + b * c + (d * e + f) * g)

Polish and reverse Polish notation

  • Polish notation (prefix): the operator is written before its operands, e.g. +ab. It was introduced by the Polish logician Jan Łukasiewicz.
  • Reverse Polish notation (postfix): the operator is written after its operands, e.g. ab+.
  • The usual form a+b (operator between operands) is infix.

Both prefix and postfix need no brackets and no precedence rules, because the order of operators already fixes the order of evaluation. Example: (a+b)*c → prefix *+abc, postfix ab+c*.

Conversion of P: (a + b * c + (d * e + f) * g)

  1. Scan the infix expression left to right.
  2. Operand: copy it to the output.
  3. (: push it.
  4. ): pop operators to the output until (; discard both brackets.
  5. Operator: pop operators of higher or equal precedence from the stack top (for ^ only higher) to the output, then push the scanned operator.
  6. At the end, pop all remaining operators to the output.

Precedence: ^ > * / > + -.

StepSymbolStack (bottom → top)Postfix output
1((-
2a(a
3+(+a
4b(+ab
5*(+*ab
6c(+*abc
7+(+abc*+
8((+(abc*+
9d(+(abc*+d
10*(+(*abc*+d
11e(+(*abc*+de
12+(+(+abc*+de*
13f(+(+abc*+de*f
14)(+abc*+de*f+
15*(+*abc*+de*f+
16g(+*abc*+de*f+g
17)(empty)abc*+de*f+g*+
end(pop all)(empty)abc*+de*f+g*+

Postfix: abc*+de*f+g*+

Check by the order of evaluation: b*c, then a+(b*c), then d*e, (d*e)+f, *g, and the final +.

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Data Structure and Algorithm chapter 2 questions →