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/-*

0 Comments:

Post a Comment