- 2069 Poush · 6 marks
Convert expression to prefix and postfix
Short answer
Postfix: ABC*DE/F-G*-H*+. Prefix: +A*-*BC*-/DEFGH.
Convert the given infix expression (A+(B*C-(D/E-F)*G)*H) into equivalent prefix and postfix expressions showing each step in tabular form.
Infix: A + ( B * C − ( D / E − F ) * G ) * H.
Postfix (left to right)
| Step | Symbol | Stack (bottom → top) | Postfix output |
|---|---|---|---|
| 1 | A | (empty) | A |
| 2 | + | + | A |
| 3 | ( | +( | A |
| 4 | B | +( | AB |
| 5 | * | +(* | AB |
| 6 | C | +(* | ABC |
| 7 | - | +(- | ABC* |
| 8 | ( | +(-( | ABC* |
| 9 | D | +(-( | ABC*D |
| 10 | / | +(-(/ | ABC*D |
| 11 | E | +(-(/ | ABC*DE |
| 12 | - | +(-(- | ABC*DE/ |
| 13 | F | +(-(- | ABC*DE/F |
| 14 | ) | +(- | ABC*DE/F- |
| 15 | * | +(-* | ABC*DE/F- |
| 16 | G | +(-* | ABC*DE/F-G |
| 17 | ) | + | ABC*DE/F-G*- |
| 18 | * | +* | ABC*DE/F-G*- |
| 19 | H | +* | ABC*DE/F-G*-H |
| end | (pop all) | (empty) | ABC*DE/F-G*-H*+ |
Postfix: ABC*DE/F-G*-H*+
Prefix
Reverse the infix string, swap ( and ), convert it like postfix (an incoming operator pops only operators of strictly higher precedence), then reverse the result.
Reversed with swapped brackets: H * ( G * ( F − E / D ) − C * B ) + A.
| Step | Symbol (reversed) | Stack | Output (before reversing) |
|---|---|---|---|
| 1 | H | (empty) | H |
| 2 | * | * | H |
| 3 | ( | *( | H |
| 4 | G | *( | HG |
| 5 | * | *(* | HG |
| 6 | ( | *(*( | HG |
| 7 | F | *(*( | HGF |
| 8 | - | *(*(- | HGF |
| 9 | E | *(*(- | HGFE |
| 10 | / | *(*(-/ | HGFE |
| 11 | D | *(*(-/ | HGFED |
| 12 | ) | *(* | HGFED/- |
| 13 | - | *(- | HGFED/-* |
| 14 | C | *(- | HGFED/-*C |
| 15 | * | *(-* | HGFED/-*C |
| 16 | B | *(-* | HGFED/-*CB |
| 17 | ) | * | HGFED/-*CB*- |
| 18 | + | + | HGFED/-*CB*-* |
| 19 | A | + | HGFED/-*CB*-*A |
| end | (pop all) | (empty) | HGFED/-*CB*-*A+ |
Reversing the output gives Prefix: +A*-*BC*-/DEFGH
Check: +A*-*BC*-/DEFGH read from the right with a stack gives the same expression tree as the postfix ABC*DE/F-G*-H*+.
✓ Answer checked by Claude Opus 5.5 (high effort)
Related questions
- Convert expression to prefix and postfix · Data Structure and Algorithm, chapter 2
- Importance of postfix; convert expression · Data Structure and Algorithm, chapter 2
- Algorithm for infix to postfix conversion · Data Structure and Algorithm, chapter 2 · asked 3×
- Evaluate postfix expression 574-*8/4+ · Data Structure and Algorithm, chapter 2
- Infix to postfix and evaluation · Data Structure and Algorithm, chapter 2
- Convert and evaluate A/B-(C+D)*E · Data Structure and Algorithm, chapter 2 · asked 2×