Postfix to Infix Algorithm

I have come across one very interesting query about Postfix to Infix conversion.

Let’s understand first the importance of having Postfix notation:-

·         To reduce computer memory access.

                     The automatic stack permits the automatic storage of intermediate results for use later: this key
               feature is what permits RPN calculators to easily evaluate expressions of arbitrary complexity: they
               do not have limits on the complexity of expression they can evaluate.

·         To utilize the stack to evaluate expressions.

·         To reduce the complexity of expression while evaluation.

·         Postfix notation is often used in stack-based and concatenative programming languages.

Postfix to Infix Algorithm Let’s look out for the algorithm for converting postfix to infix expression:- §  While there are input symbol left §  Read the next symbol from input. §  If the symbol is an operand (i.e. value) §  Push it onto the stack. §  Otherwise, the symbol is an operator. §  If there are fewer than 2 values on the stack §  (Error) The user has not input sufficient values in the expression. §  Else, Pop the top 2 values from the stack (operand1 & operand 2). §  Put the operator, with the values as arguments and form a string (like : operand1 operator operand2). §  Encapsulate the resulted string with parenthesis. (like: (a+b)  if operand1 =’a’, operand2 =’b’, operator = ‘+’ ) §  Push the resulted string back to stack. §  If there is only one value in the stack §  That value in the stack is the desired infix string. §  If there are more values in the stack §  (Error) The user input has too many values.

Postfix to infix will not give you exact expression in terms of parenthesis, though it will give you same result on evaluation.

e.g. (a+b+c)*2
Postfix will be :- ab+c+2*
And postfix to infix will give :- (((a+b)+c)*2)

Posted in: Algorithms