Conversion of Infix expression to Postfix expression using Stack data structure

After a long time, I’m going to work on Expression Evaluation, so I’m writing this blog post to revisit and explain it to myself.

The expressions we (human beings) write are called infix expressions as the operators come in between the operands to denote the expression’s execution flow.

Let’s consider the following expression.

A + B, this is an infix expression because the operator “+” comes between operands “A” and “B”.

To evaluate expressions manually infix notation is helpful as it is easily understandable by the human brain.

But infix expressions are hard to parse in a computer program hence it will be difficult to evaluate expressions using infix notation. To reduce the complexity of expression evaluation Prefix or Postfix expressions are used in the computer programs.

Let’s see what is Postfix expressions:

In Postfix expressions, operators come after the operands. Below are an infix and respective Postfix expressions.

A + B → A B +

As mentioned in the above example, the Postfix expression has the operator after the operands.

To begin conversion of Infix to Postfix expression, first, we should know about operator precedence.

Operator Precedence:

Precedence of the operators takes a crucial place while evaluating expressions.

The top operator in the table has the highest precedence. As per the precedence, the operators will be pushed to the stack.

Let’s see an example of the infix to Postfix conversion, we will start with a simple one,

Infix expression: A + B

If we encounter an operand we will write in the expression string, if we encounter an operator we will push it to an operator stack.

So we have two elements,

1. An empty expression string
2. An empty operator stack

In the expression first, we are encountering “A”, as it is an operand we will add it to the expression string. So now the two elements look like below,

1. Expression string: A
2. Operator Stack:

The second token we are encountering is an operator “+”, so we will push it to the operator stack.

1. Expression string: A
2. Operator Stack: +

The third token is an operand “B”, so we will add it to the expression string.

1. Expression string: A B
2. Operator Stack: +

Thus we processed all the tokens in the given expression, now we need to pop out the remaining tokens from the stack and have to add it to the expression string.

Pop the operator “+” from the stack and add it to the expression string which already has “A B” in it.

So now the output becomes “A B +” which is the Postfix notation for the given infix expression “A + B”.

Second Example:

Let’s convert a little complex expression with parentheses. Below is the given infix expression,

( ( A + B ) — C * ( D / E ) ) + F

The given expression has parentheses to denote the precedence. So let’s start with the conversion with two empty elements respectively,

1. An empty expression string
2. An empty operator stack

The first token to encounter is an open parenthesis, add it to the operator stack.

1. Expression string:
2. Operator Stack: (
3. Remaining expression: ( A + B ) - C * ( D / E ) ) + F

The second token to encounter is again an open parenthesis, add it to the stack.

1. Expression string:
2. Operator Stack: ( (
3. Remaining expression: A + B ) - C * ( D / E ) ) + F

Next token un the expression is an operand “A”, so add it to the expression string.

1. Expression string: A
2. Operator Stack: ( (
3. Remaining expression: + B ) - C * ( D / E ) ) + F

Afterward, we have an operator “+”, so add it to the stack.

1. Expression string: A
2. Operator Stack: ( ( +
3. Remaining expression: B ) - C * ( D / E ) ) + F

Then we have an operand, so add it to the expression string.

1. Expression string: A B
2. Operator Stack: ( ( +
3. Remaining expression: ) - C * ( D / E ) ) + F

Next token in the given infix expression is a close parenthesis, as we encountered a close parenthesis we should pop the expressions from the stack and add it to the expression string until an open parenthesis popped from the stack.

1. Expression string: A B +
2. Operator Stack: (
3. Remaining expression: - C * ( D / E ) ) + F

Notice here we didn’t push the close parenthesis to the stack, instead, we pooped out the operator “+” and added it to the expression string and pooped out one open parenthesis from the stack as well.

Next, we are encountering with an operator “-”, so push it to the stack.

1. Expression string: A B +
2. Operator Stack: ( -
3. Remaining expression: C * ( D / E ) ) + F

Next is an operand “C”, so add it to the expression string,

1. Expression string: A B + C
2. Operator Stack: ( -
3. Remaining expression: * ( D / E ) ) + F

Next is an operator “*”, so push it to the stack.

1. Expression string: A B + C
2. Operator Stack: ( - *
3. Remaining expression: ( D / E ) ) + F

Next is an open parenthesis, so add it to the stack.

1. Expression string: A B + C
2. Operator Stack: ( - * (
3. Remaining expression: D / E ) ) + F

Next is an operand “D”, so add it to the expression string.

1. Expression string: A B + C D
2. Operator Stack: ( - * (
3. Remaining expression: / E ) ) + F

Next we encounter an operator “/”, so push it to the stack.

1. Expression string: A B + C D
2. Operator Stack: ( - * ( /
3. Remaining expression: E ) ) + F

Then an oprand “E”, add it to the expression string.

1. Expression string: A B + C D E
2. Operator Stack: ( - * ( /
3. Remaining expression: ) ) + F

Then a close parenthesis, as we saw earlier, we should not push it to the stack instead we should pop all the operators from the stack and add it to the expression string until we encounter an open parenthesis. Then pop the open parenthesis from the stack but don’t add it to the expression string.

1. Expression string: A B + C D E /
2. Operator Stack: ( - *
3. Remaining expression: ) + F

Next token is again a close paranthesis, so we will pop all the operators and add them to the expression string until we reach the open parenthesis and we will pop the open parenthesis as well from the operator stack.

1. Expression string: A B + C D E / * -
2. Operator Stack:
3. Remaining expression: + F

Next token is an operator “+”, so push it to the stack.

1. Expression string: A B + C D E / * -
2. Operator Stack: +
3. Remaining expression: F

Next token is an operand, “F”. Add it to the expression string.

1. Expression string: A B + C D E / * - F
2. Operator Stack: +
3. Remaining expression:

As we processed the whole infix expression, now the operator stack has to be cleared by popping out each remaining operator and adding them to the expression string.

Here we have the operator “+” on the stack, so we will pop out the operator “+” from the stack and will add it to the expression string. So the resultant Postfix expression would look like below,

Final Postfix expression: A B + C D E / * - F +

Hope you would understand, if not please let me know by comment.

✉️ Subscribe to CodeBurst’s once-weekly Email Blast, 🐦 Follow CodeBurst on Twitter, view 🗺️ The 2018 Web Developer Roadmap, and 🕸️ Learn Full Stack Web Development.