<< Prev : Describe the memory map of a C program?Next : >> What are models and meta models?

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

Replies:

Replies:

Login

Register

There are three different ways in which an expression like a+b can be represented.

Prefix (Polish)

Postfix (Suffix or reverse polish)

Infix

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

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

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

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:

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

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.

Convert from postfix expression to infix

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

December 26th, 2010 15:34

## To reply to this discussion, please Login.