Infix: the operator is in between the two operands.
Prefix: operators precede the two operands that they
work on.
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 |
-------
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
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+/
------
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