Related Tags

notation
postfix
infix

# How to convert infix expressions to postfix expressions

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

Conventional notation, such as $A + B$, is equivalent to infix notation. Postfix notation, also known as Reverse Polish notation, is a notation where the operands appear before their operators such as in the expression $AB+$. The advantage of postfix notation is the unambiguity of the sequence of operations. In fact, parentheses are redundant in the notation.

## Converting from infix to postfix

Stacks are ideal data structures for converting infix to postfix expressions. We scan the infix expression from left to right and make decisions based on if the scanned symbol (generally called a ‘token’) is an operand or an operator. Operands are pushed to the output and operators are pushed to the stack; so, our decision is based on the precedence of the operator.

1. Set the precedence of operations (a typical precedence set is shown in the illustration above).
2. If the token is an operand, then do not push it to stack. Instead, pass it to the output.
3. If the token is an operator or parenthesis, do the following:
• Before you can push the operator onto the stack, you have to pop the stack until you find an operator with a lower priority than the current operator. The popped stack elements are written to output.
• When you’ve found the appropriate position, stack the current operator.
• If your current token is a right parenthesis, pop the stack until after the first left parenthesis. Output all the symbols except the parentheses.

A left parenthesis on the stack is only removed if an incoming right parenthesis is found (unlike other operators such as + - ? *, that only follow precedence rules).

• After the entire expression is scanned, pop the rest of the stack and write the operators in the stack to the output.

## Example

In the example below, we will look at how to convert the infix expression $4^2 + 5 * ( 2 + 1) / 2$ to postfix:

1 of 15

RELATED TAGS

notation
postfix
infix

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

Keep Exploring

Learn in-demand tech skills in half the time