AlgoViz
HomeStack

Infix to Postfix Conversion

Medium

Operands out, operators on the stack

Problem

Convert an infix expression (a+b*c) to postfix (abc*+) using operator precedence.

In simple words

Output operands right away; hold operators on a stack, popping ones of higher or equal precedence.

The idea

Send operands straight to the output and hold operators on a stack, popping any that bind at least as tightly before pushing a new one. Parentheses push and pop as explicit barriers, and the result needs no brackets because postfix order encodes precedence.

The trick

  • Pop while the stack top has greater or equal precedence — for right-associative operators, strictly greater.
  • '(' pushes as a barrier; ')' pops back to it and discards both.
  • Flush whatever remains on the stack at the end.

This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.

0
0

Step 1 of 2. Here's the example — a+b*c Values: 0.

1/2
Optimal
timeO(n)spaceO(n)
1for token:2  if operand: output3  elif '(' : push4  elif ')' : pop until '('5  else: pop while top has >= precedence; push op6pop rest

Input

array
[0]

Output

answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Example

Input:
a+b*c
Output:
abc*+

Practice this problem:GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.