Convert Infix to Postfix

In this blog, we go over how to convert the infix notation to postfix notation. The postfix notation is commonly used to evaluate strings, like “2 + 1 – (3 + 5 / 4)”. Questions like 224. Basic Calculator on LeetCode and its variations can be solved easily after converting the input from Infix to Postfix.

0. Infix to Postfix: Why Use Postfix?

Well, isn’t it pretty obvious, what is the answer to “2 + 1 – (3 + 5 / 4)”?

Why have people created a new notation in the first place?

Here’s the thing. While solving, you might implicitly use a rule like Brackets Of Division Multiplication Addition Subtraction, also called BODMAS. It says that (, ) have to be evaluated first, then “of”, then /, *, +, -.

And then the question arose – is there a way in which it is implicitly known what the ordering of the operators is? What if there is no need to have this special rule?

As this Stack Overflow answer explains, it is simply easier for machines to evaluate a string in postfix notation, since there is no need of operator precedence. The precedence is implicitly encoded into the string.

The postfix notation is also called the Reverse Polish Notation, or RPN for short.

1. Infix to Postfix: Observations

1.0. Examples

Ok let’s take a couple of examples and see what it means.

In the cases above, we see that the operator is present after the operands. That is, the + is after both the things that need to be added, a and b

This is a slight bit more complicated example. Since * has as a higher priority, we want to write b * c in postfix notation first as b c *. Then, we need to add a to the mix, so we append + at the end.

Note how the order of the operands, a, b, c has remained the same. The order of operators, + and * have changed!

Note the difference between the first and the second ones. The ordering of a b c remains the same, but in the first case + * reverses to become * + and in the second case, it remains the same!?

This is because it doesn’t matter whether + or * comes before in infix notation. Both end up as * followed by + in the postfix notation, since that is the ordering being implicitly represented now!

Recall that that was the goal of postfix notation!

1.1. Try it yourself!

Try the converting the next one yourself.

And the answer is given below.

2. Infix to Postfix: Logic

Let’s try to formalize the rules. postfix is the string containing our answer.

2.0. Operands

In all the above examples, we see how the ordering of just the operands, like a, b, c remain the same – a comes before b and b comes before c and so on. Thus, we can say the following.

If we get an operand (character like a, b, c) we add it to the postfix string directly

2.1. Operators

This is the more tricky part. Since we already dealt with operands, we can focus on operators only. Now, to implicitly encode operator priority information, we need a way to reorder the operators.

So, the operators are: “+/*-” which become “/*+-“. A couple of things to note:

• When the first + comes, we don’t add it directly. We store it in some temporary data structure.
• When the next / comes, we do the same.
• When the next * comes, however, we see that the priority of * is lower than / this means that * wants to be considered, but before it, / needs to be resolved! So, we kick out / of the data structure, add it to postfix and add * to the temporary data structure. It now has + and *
• When the next – comes, we realize it is of the lowest priority. So, we kick out * and then + (in that order), add it to postfix and add – to the data structure.
• Since we are at the end, we empty out the data structure contents in postfix.

If you realize, the temporary data structure we are using is nothing but a stack! In fact, since we kick out operators of higher priority, when a lower one comes, we have a monotonically increasing stack!

2.2. Dry Run

• c = current element
• op_stack = the monotonically increasing operator stack
• postfix = the final answer

The algorithm we just derived from scratch is called the Shunting Yard Algorithm, developed by Edsger Dijkstra.

3. Infix to Postfix: Code

3.0. Code in Python3

def infix_to_postfix(s):
    # the final postfix string as the answer
    postfix = ""
    # the operator stack
    op_stack = []
    
    for c in s:
        # c is useless, skip
        if c == " ": 
            continue
        # if c is an operand (digit/character)
        elif c not in OPERATORS:
            postfix += c
        # if c is an operator
        elif c in OPERATORS:
            # while the current operator has a lower priority than stack top
            while op_stack and PRIORITY[op_stack[-1]] > PRIORITY[c]:
                # save it to postfix
                postfix += op_stack.pop()
            # finally add the character to the operator stack
            op_stack.append(c)
    
    # clearing out the operator stack, adding the remaining operators to postfix
    while op_stack:
        postfix += op_stack.pop()
    
    return postfix

OPERATORS = "-+*/"
# PRIORITY = {'-': 0, '+': 1, '*': 2, '/': 3}
PRIORITY = {op: i for i, op in enumerate(OPERATORS)} 

s = "a+b/c*d-e"
print(infix_to_postfix(s))

3.1. Complexity Analysis

• Time: O(N) where N is the length of the string. We only look at operands once. And we look at each operator twice (max) to add and remove it each once.
• Space: O(N) For a string of N length, we can have N/2 operators of the same type – meaning the op_stack can grow to O(N/2) = O(N) size.

4. Infix to Postfix: Brackets!

4.0. Introduction

Our discussion till now only relies on operators other than brackets. Let’s try to see how to include brackets into the mix.

• We know that everything inside brackets need to be resolved first.
• So, how about we write those two cases separately?

        if c == " ": 
            continue
        elif c == '(':
            op_stack.append(c)
        elif c == ')':
            # while the current stack top is not an opening bracket, keep popping
            while op_stack[-1] != '(':
                postfix += op_stack.pop()
            # remove the ( bracket, since its use is over
            # and no need to add the current ) bracket
            op_stack.pop()
        # if c is an operand (digit/character)
        ...

What the above code snippet says is:

• if ( comes, add it to the stack, no questions asked
• when ) comes, start popping out the operators, since the bracket era has come to an end and add those guys to postfix
• finally, pop out the first (

This is not all, though. We also need to make sure that an opening bracket never gets kicked out of the stack – since it can only be kicked out by a closing bracket. This means we need to make the opening bracket be the lowest priority.

OPERATORS = “(-+*/”

4.1. Code in Python3

def infix_to_postfix(s):
    # the final postfix string as the answer
    postfix = ""
    # the operator stack
    op_stack = []
    
    for c in s:
        # c is useless, skip
        if c == " ": 
            continue
        elif c == '(':
            op_stack.append(c)
        elif c == ')':
          # while the current stack top is not an opening bracket, keep popping
          while op_stack[-1] != '(':
                postfix += op_stack.pop()
            # remove the ( bracket, since its use is over
            # and no need to add the current ) bracket
            op_stack.pop()
        # if c is an operand (digit/character)
        elif c not in OPERATORS:
            postfix += c
        # if c is an operator
        elif c in OPERATORS:
            # while the current operator has a lower priority than stack top
            while op_stack and PRIORITY[op_stack[-1]] > PRIORITY[c]:
                # save it to postfix
                postfix += op_stack.pop()
            # finally add the character to the operator stack
            op_stack.append(c)
    
    # clearing out the operator stack, adding the remaining operators to postfix
    while op_stack:
        postfix += op_stack.pop()
    
    return postfix

OPERATORS = "(-+*/"
# PRIORITY = {'(': 0, -': 1, '+': 2, '*': 3, '/': 4}
PRIORITY = {op: i for i, op in enumerate(OPERATORS)} 

s = "a+c*(d-e)"
print(infix_to_postfix(s))

And this is it, for the code and the logic! Feel free to experiment and tear the code apart, to truly understand it.

5. Conclusion

Converting infix notation to postfix notation is a helpful function to have by your side, especially when it comes to string parsing questions. To fully understand and implement that, we first started off looking at a couple of examples to understand things better. And, by looking at observations from the basic test cases, we built up a formal logic to handle the operators. Then, we made our solution even account for brackets.

Now, feel free to try out the 224. Basic Calculator question!

Tanishq Chaudhary

Producing high-quality intuitive explanations of interview problems. Currently covering LeetCode and InterviewBit.