Infix to Prefix Expression

Conversion an infix into Prefix Expression: For converting infix expression to prefix expression. An Infix expression is converted into Prefix using two stacks, one for operator and another for operands. 

The infix sting is read in an array, from which symbols/characters are fetched one by one and the following checks are performed:

1. If symbol is an operand, push it in operand’s stack.
2.  Initialize operator stack with a dummy operator with the least precedence (say #).
3. If the symbol is an operator, then do the following:
4. Pop an operator from the operator stack.
5. Check its precedence with the symbol.
6. If the precedence of the symbol is higher, then simply push the popped operator and then the symbol.
7. Else if the precedence of symbol is lower (or equal to) than the popped operator, pop two operands, (opnd2 and opnd1) and perform concatenation operation (optr, opnd1, opnd2).
8. Push the result in operand’s stack.
9. Repeat the above steps until the symbol becomes less than the popped operator.
10. After the string ends, start popping an operator from the operator stack and two operands from operand stack.
11. Repeat step (d) until dummy operator (#) is found.
12. Pop the expression from the operand stack and return it, which is the desired Prefix equivalent of given Infix string.

Example: Let’s trace the following infix expression A+B*C+D/E

Reverse of ED/CB*A++ is ++A*BC/DE

The prefix expression of A+B*C+D/E is ++A*BC/DE.

Evaluation of Prefix expression

The algorithm for evaluating a prefix expression is as follows:

• Accept a prefix string from the user. As the input prefix string.

• Start scanning the string from the right one character at a time.

• If it is an operand, push it in stack.

• If it is an operator, pop opnd1, opnd2 and perform the operation, specified by the operator.  Push the result in the stack.

• Repeat these steps until array of input prefix strings ends.

This algorithm works fine, if given prefix expressions are evaluated from left to right without considering precedence of operators, which will not give correct result in all the cases, where precedence rules of operators must be followed to get correct result.

For example:  Consider the following two prefix notations:

(a)    +*435  and  (b)  *+435

Infix equivalent of a is 4*3+5 and that of b is 4+3*5.  Result of a is 12+5=17 and that of b is 7*5=35, which is not the desired result since the precedence of * operator is higher as compared to +.  Result should be 4+3*5=4+15 = 19 or if the expression is (4+3)*5, then (7)*5=7*5=35.

Thus precedence of operators and availability of brackets must be kept in mind for evaluating a given prefix string to result in a correct output.

• Therefore, correct result may only be achieved from a prefix string, if while converting from infix to prefix, due consideration is kept in mind for precedence of operators and that of brackets.