Understanding infix to prefix conversion

Any expression written in the prefix notation can be easily parsed and evaluated by a computer as opposed to the infix notation. However, for us humans, writing prefix 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 a prefix using the infix-to-prefix conversion algorithm.

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

Convert the infix notation to prefix.

We use a stack and operator precedence rules to convert an infix notation to prefix. We will learn more about the proof of correctness of this technique later in this lesson.

To convert the expression to prefix, we create a stack stack to hold all operators seen so far in the increasing order of precedence. We also create an empty string prefix to hold the prefix notation. We then iterate in the infix string in reverse, i.e., from end to start, 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 prefix 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 prefix 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 prefix string until the stack becomes empty.

At the end of all iterations the prefix string will have the prefix notation in reverse, and so we will reverse it to get the correct prefix notation.

Note that ideally we should be prepending characters to the prefix string instead of appending them as we are moving from right to left in the infix string. However, since in most programming languages, appending to the end of a string is a constant time operation while preceding is not, we chose to append, which will create a prefix string in reverse.