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.

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.

- Set the precedence of operations (a typical precedence set is shown in the illustration above).
- If the token is an operand, then do not push it to stack. Instead, pass it to the output.
- 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.

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

Copyright Â©2024 Educative, Inc. All rights reserved

TRENDING TOPICS