Infix to postfix with the shunting-yard method in Python

Why this matters

Type 3 + 4 * 2 into a scientific calculator and it returns 11, not 14. The calculator knows that * is done before +. Most programming languages and spreadsheets follow this rule too. A compiler, which is the program that turns source code into something a computer can run, must apply this rule when it reads your code.

Normal written maths puts each operator between its two numbers. This is called infix notation. People read it easily, but a computer has to work out which operator to handle first, and the answer depends on brackets and on the precedence rules.

There is a second notation, called postfix, where each operator comes after the numbers it works on. Postfix needs no brackets, and a computer can read it from left to right with one stack. So a common step in a calculator or a compiler is to convert infix into postfix first.

This lesson shows that conversion. The method is called the shunting-yard method, after the railway yards where wagons are sorted onto tracks. It is usually credited to Edsger Dijkstra. The next lesson, Calculator with two stacks, skips the postfix step and evaluates the infix expression directly.

Three ways to write one sum

Take the sum of 3 and 4. There are three ways to write it.

• Infix: 3 + 4. The operator sits between the numbers.
• Postfix: 3 4 +. The operator comes after both numbers. This is also called reverse Polish notation.
• Prefix: + 3 4. The operator comes before the numbers.

This lesson only needs infix and postfix. The spaces in 3 4 + separate the pieces. Each piece is called a token. A token is one number, one operator, or one bracket.

Postfix reads like a list of steps. Read 3 4 2 * + from left to right:

1. Put 3 aside.
2. Put 4 aside.
3. Put 2 aside.
4. * means multiply the two most recent numbers that are set aside. That is 4 and 2, giving 8.
5. + means add the two most recent numbers. That is 3 and 8, giving 11.

The original infix form was 3 + 4 * 2, and it means the same thing. The postfix form needs no brackets and no precedence rule, because the order of the tokens already says what to do first. That is why computers like it.

Stacks, briefly

The algorithm uses a stack. A stack is a pile where you only touch the top. Three actions matter:

• push puts a value on the top of the pile.
• pop removes the value on the top and gives it back.
• peek looks at the top value without removing it.

A stack is last in, first out. The last value you pushed is the first one you pop.

In Python, a list is the usual stack. append pushes, pop removes and returns the last item, and [-1] peeks at the last item without removing it. The end of the list is the top of the stack. A short program that uses each action is below. Its output follows it.

*
*
False
['+']

The * was appended last, so it is on top. ops[-1] shows it and leaves it in place. pop removes it and returns it, so the second line is * again. not ops is False because + is still in the list, and the last line shows that + is the only value left.

Precedence and associativity

Precedence is how strongly an operator binds its numbers. A higher number binds more tightly, so it is done first.

Associativity decides the order when two operators have the same precedence. Subtraction and division go from left to right. The expression 8 - 3 - 2 means (8 - 3) - 2, which is 3. It does not mean 8 - (3 - 2), which is 7.

The same goes for division. 8 / 4 / 2 means (8 / 4) / 2, which is 1. Reading it the other way would give 8 / (4 / 2), which is 4. Keep this in mind. A common mistake, shown later in this lesson, is to get it wrong.

The rules of the shunting-yard method

The method reads the tokens from left to right. It uses two things: an output list, which will hold the postfix tokens in order, and an operator stack, which holds operators and open brackets while they wait.

1. Number: add it to the output.
2. Open bracket (: push it onto the operator stack.
3. Close bracket ): pop operators from the stack into the output until you pop the matching (. Throw that ( away. If the stack runs out before you find a (, the brackets do not match.
4. Operator: before you push it, look at the top of the operator stack. While the top is an operator with the same or higher precedence, pop it into the output. Stop when the top is ( or the stack is empty. Then push the new operator.
5. End of input: pop everything left on the operator stack into the output. If a ( is still there, a closing bracket is missing.

Rule 4 is the heart of the method. Think of the stack as a pile of waiting jobs. A waiting operator on the stack has to be done before the new operator only when it binds at least as tightly. If it binds more tightly, it has to be done first, so it goes to the output now. If it binds less tightly, it waits, because the new operator should be done first.

Rule 3 is why brackets work. Everything between ( and ) is handled before anything outside. The ( acts as a wall. Rule 4 never pops past a (, so the operators inside the brackets stay on the stack until the closing bracket arrives.

Worked example 1: 2 + 3 * 4

Start with a short case. Read the tokens one at a time. The operator stack is shown with the top on the left.

When * arrives, the stack holds +. The + binds less tightly than *, so * waits on top of it. At the end, the * comes off first, then the +. The postfix form 2 3 4 * + means: multiply 3 and 4 to get 12, then add 2 to get 14. That is correct, because 2 + 3 * 4 is 14.

Compare this with the wrong idea of doing + first. That would give 20, which is wrong. The stack keeps + waiting so that the multiplication can happen first.

Worked example 2: (2 + 3) * (4 - 1) / 3

Now add brackets and a same-precedence case. The output is built as a single text, so each row shows the output so far.

Two steps need a closer look.

The first is the ) after 3. Everything inside the brackets is finished before the * is read. The + is popped, and the ( is thrown away. The stack is then empty, so the * is pushed onto nothing.

The second is the / after ). The * is on the stack with precedence 2, and / also has precedence 2. The rule says to pop operators of equal or higher precedence, so * goes to the output first. This keeps the left-to-right order: (5 * 3) / 3 in that order. The result is 5.

Worked example 3: 3 + 4 * 2 / (1 - 5)

This example uses every rule. Here is the trace that the Python program prints for it. The program is shown in full in the next section, so you can run it yourself.

3      number: send to output                 output=3                  stack=[]
+      operator: pop equal or higher, push    output=3                  stack=[+]
4      number: send to output                 output=3 4                stack=[+]
*      operator: pop equal or higher, push    output=3 4                stack=[*, +]
2      number: send to output                 output=3 4 2              stack=[*, +]
/      operator: pop equal or higher, push    output=3 4 2 *            stack=[/, +]
(      open bracket: push                     output=3 4 2 *            stack=[(, /, +]
1      number: send to output                 output=3 4 2 * 1          stack=[(, /, +]
-      operator: pop equal or higher, push    output=3 4 2 * 1          stack=[-, (, /, +]
5      number: send to output                 output=3 4 2 * 1 5        stack=[-, (, /, +]
)      close bracket: pop to (                output=3 4 2 * 1 5 -      stack=[/, +]
end    pop everything left                    output=3 4 2 * 1 5 - / +

Read the row where / arrives. The stack holds * and +. The * has precedence 2, the same as /, so it is popped to the output. The + has precedence 1, which is lower than /, so it stays. The / is pushed on top of +. The output now holds 3 4 2 *, which is 4 * 2.

Then the brackets. ( is pushed. 1 goes to the output. - is pushed on top of (, and 5 goes to the output. The ) pops - to the output and throws away the (. The output is now 3 4 2 * 1 5 -, which is (1 - 5).

At the end, the stack holds / and +. They are popped in that order. The final postfix is 3 4 2 * 1 5 - / +.

Check the value. In postfix form, 4 2 * gives 8, 1 5 - gives -4, 8 -4 / gives -2, and 3 -2 + gives 1. The infix expression also gives 3 + (8 / -4), which is 1. The two forms agree.

The Python program

The program below follows the rules exactly. It has three parts.

• precedence returns 2 for * and /, 1 for + and -, and 0 for anything else. It looks the operator up in a dictionary, so there is no long chain of if lines.
• tokenize turns the text into a list of tokens. It reads a run of digits as one token, so 12 is one token, not 1 and 2. It skips spaces. It raises an error on any other character.
• to_postfix applies the five rules. When the trace argument is True, it prints one line per token showing the output and the operator stack.

Save the code as shunting.py. The stack is a list, and the top of the stack is its last item. The tokens are strings, so each one is compared with ==, which checks whether two strings hold the same text.

Run it with this command:

python3 shunting.py

The output below was produced with Python 3.14:

Trace:
3      number: send to output                 output=3                  stack=[]
+      operator: pop equal or higher, push    output=3                  stack=[+]
4      number: send to output                 output=3 4                stack=[+]
*      operator: pop equal or higher, push    output=3 4                stack=[*, +]
2      number: send to output                 output=3 4 2              stack=[*, +]
/      operator: pop equal or higher, push    output=3 4 2 *            stack=[/, +]
(      open bracket: push                     output=3 4 2 *            stack=[(, /, +]
1      number: send to output                 output=3 4 2 * 1          stack=[(, /, +]
-      operator: pop equal or higher, push    output=3 4 2 * 1          stack=[-, (, /, +]
5      number: send to output                 output=3 4 2 * 1 5        stack=[-, (, /, +]
)      close bracket: pop to (                output=3 4 2 * 1 5 -      stack=[/, +]
end    pop everything left                    output=3 4 2 * 1 5 - / +
result: 3 4 2 * 1 5 - / +
 
(2 + 3) * (4 - 1) / 3  ->  2 3 + 4 1 - * 3 /
8 - 3 - 2  ->  8 3 - 2 -
2 * (3 + 4  ->  error: unmatched '('
7 + x  ->  error: unknown character 'x' at position 4
1 + 2)  ->  error: unmatched ')'

The stack is printed with its top on the left, so stack=[*, +] means * is on top of +. The program builds that text by reversing the list, because the list stores its top at the end.

The f"..." strings are f-strings. A value inside {} is put into the text. The part after a colon, such as :<6, pads the value to a width of six characters and aligns it to the left. That is how the columns line up.

Common mistakes

Using > where the rule says >=. The rule pops operators of equal precedence too. If you pop only higher precedence, a chain of same-level operators piles up on the stack, and the order goes wrong. Here is the output of the same program with > in place of >=, for the input 8 - 3 - 2:

8 3 2 - -

That output means 8 - (3 - 2), which is 7. The correct answer is 3. The fix is to pop when the top has the same or higher precedence, which is what >= does.

Forgetting to throw away the (. When a ) arrives, the ( must be removed from the stack and not sent to the output. If it is sent to the output, the postfix string contains a bracket. A bracket is not a number or an operator, so the string can no longer be read as postfix.

Missing or extra brackets. The program reports these with a message, and you should read the message as a hint about which bracket is wrong. 2 * (3 + 4 ends with a ( still on the stack, so the program says unmatched '('. 1 + 2) finds a ) with no ( before it, so it says unmatched ')'.

Reading one character at a time. If the tokenizer reads a single character at a time, 12 becomes two tokens, 1 and 2. The expression 12 + 3 would then give the wrong postfix. You can see the effect with list, which splits a string into single characters:

['1', '2', ' ', '+', ' ', '3']
['12', '+', '3']

The while loop in tokenize reads all the digits in a row as one token. Keep that loop.

Comparing a string with a number. The stack holds string tokens, so "3" is text and 3 is a whole number. Python does not stop you when you use == between them. It just answers False:

False

The mistake shows up with < or +. Python raises an error for those:

print("3" < 4)

Traceback (most recent call last):
  ...
TypeError: '<' not supported between instances of 'str' and 'int'

print("3" + 4)

Traceback (most recent call last):
  ...
TypeError: can only concatenate str (not "int") to str

Read the last line of the traceback as a hint. It says which two types were mixed. The lines above it show the file and the line number where the error happened.

Looking at an empty stack. ops[-1] on an empty list has no item to return. Python stops with this error:

ops = []
print(ops[-1])

Traceback (most recent call last):
  ...
IndexError: list index out of range

The program checks if not ops before it reads ops[-1] or calls ops.pop(). Without that check, ops.pop() on an empty list would stop with IndexError: pop from empty list.

Reading the wrong kind of number from text. int turns text into a whole number, and it stops with an error for text that is not one:

print(int("42"))
print(int("abc"))

42
Traceback (most recent call last):
  ...
ValueError: invalid literal for int() with base 10: 'abc'

Practice

Exercise 1. Convert 1 + 2 * 3 to postfix by hand. Use the five rules and write the output after each token.

Show the answer

1 2 3 * +. The * is pushed on top of + because it binds more tightly. At the end, * is popped first and then +.

Exercise 2. Convert (1 + 2) * 3 to postfix by hand.

Show the answer

1 2 + 3 *. The + is popped when the ) arrives, so it goes to the output before the * is pushed.

Exercise 3. Convert 10 - 4 - 3 to postfix. Explain why the first - is popped before the second one is pushed.

Show the answer

10 4 - 3 -. The two - operators have the same precedence. Rule 4 says to pop an operator of equal precedence, so the first - goes to the output before the second - is pushed. This gives (10 - 4) - 3, which is 3.

Exercise 4. Convert 2 * (3 + 4) - 5 / 1 to postfix.

Show the answer

2 3 4 + * 5 1 / -. The brackets make 3 + 4 happen first, so + is popped when ) arrives. When - arrives, the * on the stack is popped first, because it binds more tightly. The / is then pushed on top of -, so it is done before - at the end. Add this expression to the examples list in main to check the answer.

Exercise 5. A student converts 8 - 3 - 2 to 8 3 2 - -. Explain what went wrong and give the correct postfix.

Show the answer

The student did not pop the first - when the second - arrived. That means the student used a rule that pops only higher precedence, not equal precedence. The correct postfix is 8 3 - 2 -. Its value is 3. The student's version has the value 7.

Summary

• Infix puts operators between numbers, and postfix puts them after the numbers they work on.
• A stack holds operators that have not yet been sent to the output. In Python, a list does this job.
• An incoming operator first pops every stacked operator with equal or higher precedence, stopping at (.
• Brackets are handled by pushing ( and popping back to it when ) arrives.
• Trace one token at a time, writing down the output and the stack, to check your answer.