Infix, Prefix and Postfix Conversions

Infix: the operator is in between the two operands.

Prefix: operators precede the two operands that they work on.

Postfix: operators come after the corresponding operands.

Infix Expression	Prefix Expression	Postfix Expression
A + B	+ A B	A B +
A + B * C	+ A * B C	A B C * +

Postfix To Prefix Conversion

Example:  7  6  $  5  * 5 - 1  7  /  9  9  +  /  +

Step 1:  Scanned character is a digit '7'.  So, push it into the stack.

|      |

|  7  |

+-----+

Step 2:  Scanned character is a digit '6'.  So, push it into the stack.

|  6  |

|  7  |

+-----+

Step 3:  Scanned character is an operator '$'.  Pop two elements from the stack and form a string containing the scanned operator and two popped elements.

$76

|      |

|      |

+-----+

Push the resultant string "$76" into the stack.

|        |

| $76  |

+------+

Step 4:  Scanned character is a digit '5'.  So, push it into the stack.

|  5    |

| $76  |

+------+

Step 5:  Scanned character is an operator '*'.  So, pop two elements from the stack and form  a string containing the scanned operator and two popped elements.  Then, push the resultant "*$765" string into the stack.

|          |

| *$765 |

+--------+

Step 6:  Scanned character is digit '5'.  Push it into the stack.

|    5     |

| *$765 |

+--------+

Step 7:  Scanned character is an operator '-'.  Pop '5' and "*$765" from the stack.  Form a string containing the scanned operator and two popped elements.  Push the resultant string into the stack

|              |

| -*$7655  |

+-----------+

Step 8:  Scanned character is digit '1'.  Push it into the stack.

|      1      |

| -*$7655  |

+-----------+

Step 9:  Scanned character is digit '7'.  Push it into the stack.

|      7       |

|      1       |

| -*$7655   |

+------------+

Step 10:  Scanned character is an operator '/'.  Pop top two elements from the stack.  Form a string containing the scanned operator and two popped elements, push the resultant string into the stack.

|               |

|    /17      |

| -*$7655  |

+-----------+

Step 11:  Scanned character is a digit '9'.  Push it into the stack.

|      9       | 

|    /17      |

| -*$7655   |

+------------+

Step 12:  Scanned character is a digit '9'.  Push it into the stack.

|      9       |

|      9       | 

|    /17      |

| -*$7655   |

+------------+

Step 13:  Scanned character is an operator '+'.  Pop top two elements from the stack.  Form a string containing the scanned operator and two popped elements, push the resultant string into the stack.

|              |

|   +99      | 

|    /17     |

| -*$7655  |

+-----------+

Step 14:  Scanned character is an operator '/'.

|              | 

| //17+99  |

| -*$7655   |

+------------+

Step 15:  Scanned character is an operator '+'.  Pop top two elements from the stack.  Form a string containing the scanned operator and two popped elements, push the resultant string into the stack.

|      |

|      |

+-----+

+ - * $ 7655//17+99

Resultant Prefix Expression: + - * $ 7655//17+99

How To Evaluate Postfix Expressions

Example:  10 20 * 30 40 10 / - +

Step 1:  Input character is 10.  So, push it into the stack.

| 10 |
 -----

Step 2:  Input character is 20.  So, push it into the stack.

| 20 |
| 10 |
 -----

Step 3:  Input character is '*'.  So, pop two elements from the stack, apply operator to those two operands and push the result into the stack.

|       |
| 200 |
 -------

Step 4:  Input character is 30.  So, push it into the stack.

|      |
| 30  |
| 200|
 ------

Step 5:  Input character is 40.  So, push it into the stack.

| 40  |
| 30  |
| 200|
 ------

Step 6:  Input character is 10, push it into the stack.

| 10  |
| 40  |
| 30  |
| 200|
 ------

Step 7:  Input character is /.  So, pop two operand from the stack and apply operator to those two operands and push the result into the stack.

| 4    |
| 30  |
| 200|
 ------

Step 8:  Input character is -.

| 26   |
| 200 |
 -------

Step 9:  Input character is '+'.  So, pop two operand from the stack and apply operator to those two operands and push the result into the stack.

| 226 |
 -------

Infix To Prefix Conversion

Infix Expression:  (a - b) / (c + d)
Step 1:  Reverse the given Expression: ) d + c (  /  ) b - a (
Step 2:  Input: )
Input is close brace.  So, place it into the stack.

|      |
|  )   |           Output:
 ------

Step 3:  Input: d
Place the operand in output buffer.

|      |
|  )   |          Output:  d
 ------

Step 4:  Input: +
Place the operator into the stack.

|       |
|  +   |
|  )   |          Output:  d
 ------

Step 5:  Input: c
Place the operand in output buffer
|       |
|  +   |
|  )    |         Output:  dc
 ------

Step 6:  Input: (
Pop '+' and ')'

|       |
|       |
|       |         Output:  dc+
 ------

Step 7:  Input: /
Push the operator into the stack.

|       |
|       |
|  /   |         Output:  dc+
 ------

Step 8:  Input: )
Push close brace into the stack.

|       |
|  )    |
|  /   |         Output:  dc+
 ------

Step 9:  Input: b
Place the operand in output buffer.

|       |
|  )    |
|  /    |         Output:  dc+b
 ------

Step 10:  Input: -
Place the operator into the stack.

|  -    |
|  )    |
|  /    |         Output:  dc+b
 -------

Step 11:  Input: a
Place the operand in output buffer.

|  -    |
|  )    |
|  /    |         Output:  dc+ba
 -------

Step 12:  Input: (
Pop all elements until we get close brace.

|       |
|       |
|  /    |         Output:  dc+ba-
 ------

No more input to parse.  So, pop all other elements from the stack

|       |
|       |
|       |         Output:  dc+ba-/
 ------
Step 13:
Reverse the output.
Prefix Notation:  -/ab+cd

Infix To Postfix Conversion

Infix Expression:  (a - b) / (c + d)
Step 1:  Input: (
Input is open brace.  So, place it into the stack.

|      |
|  (   |           Output:
 ------

Step 2:  Input: a
Place the operand in output buffer.

|      |
|  (   |          Output:  a
 ------

Step 3:  Input: -
Place the operator into the stack.

|      |
|  -   |
|  (   |         Output:  a
 ------

Step 4:  Input: b
Place the operand in output buffer
|       |
|  -    |
|  (    |         Output: ab
 -------

Step 5:  Input: )
Pop '-' and '('

|       |
|       |
|       |         Output:  ab-
 -------

Step 6:  Input: /
Push the operator into the stack.

|       |
|       |
|  /    |         Output:  ab-
 -------

Step 7:  Input: (
Push open brace into the stack.

|       |
|  (    |
|  /    |         Output: ab-
 -------

Step 8:  Input: c
Place the operand in output buffer.

|       |
|  (    |
|  /    |         Output:  ab-c
 -------

Step 9:  Input: +
Place the operator into the stack.

|  +   |
|  (    |
|  /    |         Output:  ab-c
 -------

Step 10:  Input: d
Place the operand in output buffer.

|  +    |
|  (    |
|  /    |         Output:  ab-cd
 -------

Step 11:  Input: )
Pop all elements until we get open brace.

|       |
|       |
|  /    |         Output:  ab-cd+
 ------

No more input to parse.  So, pop all other elements from the stack

|       |
|       |
|       |         Output:  ab-cd+/
 ------

Examples Infix to Prefix

Infix : (a–b)/c*(d + e – f / g)

Step 1: (a - b) = (- ab) [ '(' has highest priority ]

step 2: (d + e - f / g) = (d + e - / fg) [ '/' has highest priority ]

                       = (+ de - / fg )

          ['+','-' has same priority but left to right associativity]

                       = (- + de / fg)

Step 3: (-ab )/ c * (- + de / fg) = / - abc * (- + de / fg)

                                 = * / - abc - + de / fg

Prefix: * / - abc - + de / fg

Examples Infix to Postfix

Infix: (a–b)/c*(d + e – f / g)

Step 1: (a - b) = (ab-) [ '(' has highest priority ]

Step 2: (d + e - f / g) = (de+ - fg/) [ '/' has highest priority ]

          ['+','-' has same priority but left to right associativity]

                       = (de+ fg/ -)

Step 3: (ab- )/ c * (de+ fg/ -) = (ab-c/) * (de+ fg/ -)

                                 = ab-c/ de+ fg/-*

Postfix: ab-c/ de+ fg/-*