## Tuesday, September 10, 2013

### Pre-requisite - What is infix, postfix and prefix?

Infix, Postfix and Prefix notations are three different but equivalent ways of writing expressions.
Postfix is also known as Reverse Polish Notation or RPN , and prefix expression is also known as Polish notation.

Infix - Operators are written in-between their operands. eg.  A+B
Postfix -  Operators are written after their operands.      eg.  AB+
Prefix - Operators are written before their operands.      eg.  +AB

Here are more examples:
InfixPostfixPrefixNotes
`A * B + C / D` `A B * C D / +` `+ * A B / C D` multiply A and B,
divide C by D,
`A * (B + C) / D` `A B C + * D /` `/ * A + B C D` add B and C,
multiply by A,
divide by D
`A * (B + C / D)` `A B C D / + *` `* A + B / C D` divide C by D,
multiply by A

### Converting infix to postfix expression

Converting and infix expression to postfix or Reverse Polish notation.
I have used a stack ADT developed using a linked list. I prefer linked lists as memory can be allocated dynamically.
Precedence values of stack and input characters

```Symbols Input Precedence Stack precedence

+,-          1                 2
*,/          3                 4
\$,^          6                 5
operands     7                 8
(            9                 0
)            0                 -
#            -                 -1
```

Pseduocode
To do so, we have to add the operator to the stack, and operands to the string expression, and whenever we find a lower priority operator, we pop out the operator with higher precedence and append to the expression. When whole string expression finishes, we get the postfix expression.

There is an algorithm to convert an infix expression into a postfix expression. It uses a stack; but in this case, the stack is used to hold operators rather than numbers. The purpose of the stack is to reverse the order of the operators in the expression. It also serves as a storage structure, since no operator can be printed until both of its operands have appeared.

### Examples of Pseudocode

Example 1 -  A * B + C
Lets take a simple example - A * B + C , which should evaluate to A B * C  +
 current symbol operator stack postfix string 1 A A 2 * * A 3 B * A B 4 + + A B * {pop and print the '*' before pushing the '+'} 5 C + A B * C 6 A B * C +

Example 2 - A + B * C
A + B * C becomes A B C * +
>
 current symbol operator stack postfix string 1 A A 2 + + A 3 B + A B 4 * + * A B 5 C + * A B C 6 A B C * +

Above examples were taken from http://csis.pace.edu/~wolf/CS122/infix-postfix.htm.
Example 3 - a/b*(c+(d-e))
Consider the following expression -a/b*(c+(d-e))

Suppose a=2, b = 4

Now we do further

Once the conversion, we can evaluate the expression using the stack again.

Implementation in java
Here is java program of the above:
```import java.io.*;

class InfPos
{
private String input;
private String output = "";
public InfPos(String in)
{
input = in;
}
public String convert()
{

for(int j=0; j inpPrec(ch))
{
}
if(stackPrec(symbol) != inpPrec(ch))
else
}

{
}
return output;
}
public int stackPrec(char ch)
{
switch(ch)
{
case '+':
case '-': return 2;
case '*':
case '/': return 4;
case '^':
case '\$': return 5;
case '(': return 0;
case '#': return -1;
default: return 8;
}
}
public int inpPrec(char ch)
{
switch(ch)
{
case '+':
case '-': return 1;
case '*':
case '/': return 3;
case '^':
case '\$': return 6;
case '(': return 9;
case ')': return 0;
default: return 7;
}
}

}
class InfixToPostfix
{
public static void main(String[] args) throws IOException
{
String input, output;
while(true)
{
System.out.print("Enter infix: ");
System.out.flush();
if( input.equals("") )
break;
InfPos theTrans = new InfPos(input);
output = theTrans.convert();
System.out.println("Postfix: " + output + '\n');
}
}

}
```

Source