How to convert infix expressions to postfix expressions

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.

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: