Understanding infix to postfix conversion

Any expression written in the postfix notation can be easily parsed and evaluated by a computer as opposed to the infix notation. However, for us humans, writing postfix expressions is very difficult and error-prone as we are not used to it. However, we can convert an expression written in the infix notation to postfix using the infix to postfix conversion algorithm.

To keep things simple, consider the example of an infix notation without parentheses given below.

To convert the expression to postfix, we create a stack stack to hold all operators seen so far in the increasing order of precedence. We also create an empty string postfix to hold the postfix notation. We then iterate in the infix string from start to end and, in each iteration, check if the current character is an operator or an operand. If it is an operand, we append it to the postfix string. Otherwise, we check the precedence value of the current operator.

If it is greater than the precedence of the operator at the top of the stack (or the stack is empty), we push it to the top of the stack. Otherwise, we repeatedly pop operators from the stack and append them to the postfix string until the precedence of the operator at the top of the stack becomes less than the current operator or the stack becomes empty, and finally push the current operator to the stack.

At the end of the traversal, we repeatedly pop all operators from the stack and append them to the postfix string until the stack becomes empty. The postfix string will then have the postfix notation of the given string.