Skip to main content

Algorithm for infix to postfix conversion

Short answer

A stack is a linear LIFO structure supporting push and pop. The algorithm to convert infix to postfix scans each symbol: operands are appended to output; operators are pushed to a stack after popping any operators of higher or equal precedence; parentheses handle grouping. Example: A+B*C-D/E yields postfix ABC*+DE/-.

Define stack. Write an algorithm to convert infix expression into postfix expression using stack.

A stack is a linear data structure in which insertion (push) and deletion (pop) take place only at one end called the top. The last element inserted is the first to be removed, so it follows LIFO (Last In First Out).

Algorithm: infix to postfix

Algorithm InfixToPostfix(infix)
Input : a valid infix expression
Output: postfix expression
1. Create an empty stack S; postfix = ""
2. For each symbol x of infix, from left to right:
     if x is an operand:
         append x to postfix
     else if x is '(':
         push(S, x)
     else if x is ')':
         while top(S) != '(':
             append pop(S) to postfix
         pop(S)                       /* discard '(' */
     else:                            /* x is an operator */
         while S not empty and top(S) != '(' and
               prec(top(S)) >= prec(x):   /* > for '^' */
             append pop(S) to postfix
         push(S, x)
3. While S is not empty:
     append pop(S) to postfix
4. Return postfix

Example: A + B * C - D / E

StepSymbolStack (bottom → top)Postfix output
1A(empty)A
2++A
3B+AB
4*+*AB
5C+*ABC
6--ABC*+
7D-ABC*+D
8/-/ABC*+D
9E-/ABC*+DE
end(pop all)(empty)ABC*+DE/-

Answer: ABC*+DE/-

(Check: B*C and D/E bind tighter than + and -; the postfix ABC*+DE/- evaluates in that order.)

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Data Structure and Algorithm chapter 2 questions →