What is infix, prefix, postfix? How can you convert from one representation to another? How do you evaluate these expressions?

Postfix (Suffix or reverse polish)

ab+

Infix

a+b

Note than an infix expression can have parathesis, but postfix and prefix expressions are paranthesis free expressions.

Conversion from infix to postfix

Suppose this is the infix expresssion

((A + (B - C) * D) ^ E + F)

To convert it to postfix, we add an extra special value ] at the end of the infix string and push [ onto the stack.

((A + (B - C) * D) ^ E + F)]

--------->

We move from left to right in the infix expression. We keep on pushing elements onto the stack till we reach a operand. Once we reach an operand, we add it to the output. If we reach a ) symbol, we pop elements off the stack till we reach a corresponding { symbol. If we reach an operator, we pop off any operators on the stack which are of higher precedence than this one and push this operator onto the stack.

As an example

Expresssion                          Stack                    Output
----------------------------------------------------------------------------
((A + (B - C) * D) ^ E + F)]      [
^

((A + (B - C) * D) ^ E + F)]      [((                         A
  ^

((A + (B - C) * D) ^ E + F)]      [((+                        A
    ^

((A + (B - C) * D) ^ E + F)]      [((+(-                      ABC       
            ^

((A + (B - C) * D) ^ E + F)]      [(                          ABC-D*+
                 ^

((A + (B - C) * D) ^ E + F)]      [(                          ABC-D*+E^F+
                          ^

((A + (B - C) * D) ^ E + F)]      [                           ABC-D*+E^F+
                           ^

Is there a way to find out if the converted postfix expression is valid or not

Yes. We need to associate a rank for each symbol of the expression. The rank of an operator is -1 and the rank of an operand is +1. The total rank of an expression can be determined as follows:

- If an operand is placed in the post fix expression, increment the rank by 1.
- If an operator is placed in the post fix expression, decrement the rank by 1.

At any point of time, while converting an infix expression to a postfix expression, the rank of the expression can be greater than or equal to one. If the rank is anytime less than one, the expression is invalid. Once the entire expression is converted, the rank must be equal to 1. Else the expression is invalid.

Conversion from infix to prefix

This is very similar to the method mentioned above, except the fact that we add the special value [ at the start of the expression and ] to the stack and we move through the infix expression from right to left. Also at the end, reverse the output expression got to get the prefix expression.

Evaluation of a postfix expression

Here is the pseudocode. As we scan from left to right

If we encounter an operand, push it onto the stack.

If we encounter an operator, pop 2 operand from the stack. The first one popped is called operand2 and the second one is called operand1.

Perform Result=operand1 operator operand2.

Push the result onto the stack.

Repeat the above steps till the end of the input.

Convert from postfix expression to infix

This is the same as postfix evaluation, the only difference being that we wont evaluate the expression, but just present the answer. The scanning is done from left to right.

ABC-D*+

A(B-C)D*+

A((B-C)*D)+

A+((B-C)*D)

Convert from postfix expression to infix

The scanning is done from right to left and is similar to what we did above.

+A*-BCD

Reverse it

DCB-*A+

D(B-C)*A+

((B-C)*D)A+

A+((B-C)*D)