Editor

Python Program to Convert Infix to Postfix

Intermediate · Data structures

In infix notation the operator sits between its operands, as in A + B * C, while in postfix notation it comes after them, as in A B C * +. A computer can evaluate postfix from left to right with no brackets or precedence rules. This program converts infix to postfix with a stack that holds operators until it is their turn, which is how calculators and compilers do it.

Program

infix_to_postfix.py
PRECEDENCE = {"+": 1, "-": 1, "*": 2, "/": 2, "^": 3}
def infix_to_postfix(expression):
stack = [] # operators and "(" waiting their turn
output = []
for ch in expression.replace(" ", ""):
if ch.isalnum(): # an operand goes straight out
output.append(ch)
elif ch == "(":
stack.append(ch)
elif ch == ")":
while stack[-1] != "(": # pop back to the matching "("
output.append(stack.pop())
stack.pop() # drop the "(" itself
else: # an operator
# Pop operators that must be done first: higher precedence,
# or equal precedence (except ^, which groups right to left)
while stack and stack[-1] != "(" and (
PRECEDENCE[stack[-1]] > PRECEDENCE[ch]
or (PRECEDENCE[stack[-1]] == PRECEDENCE[ch] and ch != "^")
):
output.append(stack.pop())
stack.append(ch)
while stack: # what is left goes at the end
output.append(stack.pop())
return " ".join(output)
examples = ["A + B * C", "(A + B) * C", "A * (B + C) / D", "A ^ B ^ C",
"A + B * (C ^ D - E) ^ (F + G * H) - I"]
for expr in examples:
print("Infix: ", expr)
print("Postfix:", infix_to_postfix(expr))
Output
Infix:   A + B * C
Postfix: A B C * +
Infix:   (A + B) * C
Postfix: A B + C *
Infix:   A * (B + C) / D
Postfix: A B C + * D /
Infix:   A ^ B ^ C
Postfix: A B C ^ ^
Infix:   A + B * (C ^ D - E) ^ (F + G * H) - I
Postfix: A B C D ^ E - F G H * + ^ * + I -

How it works

  1. Operands (letters or digits) go straight to the output, in the same order as in the infix expression.
  2. An opening bracket is pushed onto the stack, and a closing bracket pops operators to the output until the matching ( turns up.
  3. Before an operator is pushed, every operator on the stack that must be done first is popped to the output: one with higher precedence, or one with the same precedence for left-to-right operators like - and /.
  4. ^ (power) is the exception, because A ^ B ^ C means A ^ (B ^ C), so an equal ^ stays on the stack and the result is A B C ^ ^.
  5. At the end, the operators still on the stack are popped to the output; the program expects single-character operands and correctly matched brackets.

Other ways to write it

Showing the stack at every step

Showing the stack at every step
precedence = {"+": 1, "-": 1, "*": 2, "/": 2}
expression = "A*(B+C)/D"
stack, output = [], ""
print(f"{'Symbol':8}{'Stack':8}Postfix")
for ch in expression:
if ch.isalnum():
output += ch
elif ch == "(":
stack.append(ch)
elif ch == ")":
while stack[-1] != "(":
output += stack.pop()
stack.pop()
else:
while stack and stack[-1] != "(" and precedence[stack[-1]] >= precedence[ch]:
output += stack.pop()
stack.append(ch)
print(f"{ch:8}{''.join(stack):8}{output}")
while stack:
output += stack.pop()
print("Postfix:", output)
Output
Symbol  Stack   Postfix
A               A
*       *       A
(       *(      A
B       *(      AB
+       *(+     AB
C       *(+     ABC
)       *       ABC+
/       /       ABC+*
D       /       ABC+*D
Postfix: ABC+*D/

This prints the table textbooks ask you to draw, with the symbol read, the stack after it and the postfix so far on each row; it leaves out ^, so >= works for every operator.

Evaluating a postfix expression

Evaluating a postfix expression
def evaluate_postfix(postfix):
stack = []
for token in postfix.split():
if token.isdigit():
stack.append(int(token)) # numbers wait on the stack
continue
right = stack.pop() # the top is the second number
left = stack.pop()
if token == "+":
stack.append(left + right)
elif token == "-":
stack.append(left - right)
elif token == "*":
stack.append(left * right)
else:
stack.append(left / right)
return stack.pop()
print("2 3 4 * + =", evaluate_postfix("2 3 4 * +"))
print("5 1 2 + 4 * + 3 - =", evaluate_postfix("5 1 2 + 4 * + 3 -"))
Output
2 3 4 * + = 14
5 1 2 + 4 * + 3 - = 14

Postfix is easy for a computer: read left to right, push numbers, and when an operator arrives, pop two numbers, apply it and push the answer back, with no brackets or precedence needed.

Try it yourself

Add % to PRECEDENCE with the same precedence as *, and convert "A % B + C".

Edit the program above and press Run, or open it in the full editor to save it and share it. To watch it run line by line, open it in the visualizer.

Related programs

All Python programs · CBSE class 12 practical file · Python exercises