Skip to main content

Importance of postfix; convert expression

Short answer

Postfix eliminates parentheses and precedence, enabling O(n) evaluation with a single stack pass. Converting (a+b*c+(d/e*f)-g) yields abc*+de/f*+g-.

What is the importance of postfix expression? Convert the given infix expression (a+bc+(d/ef)-g) into equivalent postfix expression showing the status of stack in each steps.

Importance of postfix expression

  1. No brackets needed: the order of operations is fully decided by the position of operators.
  2. No precedence or associativity rules at evaluation time; a compiler need not look back or ahead.
  3. Easy evaluation with a stack: scan once from left to right, push operands, and on an operator pop two operands and push the result. Time is O(n).
  4. Used by compilers and calculators: expressions are converted to postfix, then to machine code or evaluated (e.g., stack-based machines, HP calculators).
  5. Simple to generate and store: the postfix form is a linear string which is easy to process.

Conversion of (a + b * c + (d / e * f) - g)

The outer brackets of the given expression do not change the result and are omitted in the table. Rules used:

  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
1a(empty)a
2++a
3b+ab
4*+*ab
5c+*abc
6++abc*+
7(+(abc*+
8d+(abc*+d
9/+(/abc*+d
10e+(/abc*+de
11*+(*abc*+de/
12f+(*abc*+de/f
13)+abc*+de/f*
14--abc*+de/f*+
15g-abc*+de/f*+g
end(pop all)(empty)abc*+de/f*+g-

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

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Data Structure and Algorithm chapter 2 questions →