Question 2
(a) Write an algorithm to convert infix expression to postfix expression. Given an input string INFIX representing an infix expression whose single character
symbols have precedence values and ranks as given in table. A vector S representing a
Stack. A string function NEXTCHAR which, when invoked, returns the next character
of the input string. This algorithm converts the string INFIX to its reverse Polish string
equivalent, POLISH. RANK contains the value of rank of the reverse Polish string.
NEXT contains the symbol being examined. TEMP is a temporary variable which
contains the unstacked element. We assume that the given input string is padded on the
right with the special symbol ‘)’. Algorithms PUSH and POP are used for stack
manipulations.
Step-1: [Initialize the stack]
TOP 1
S[TOP] ‘(’
Step-2: [Initialize output string and rank count]
POLISH ‘’
RANK 0
Step-3: [Get first input symbol]
NEXT NEXTCHAR(INFIX)
Step-4: [Translate the infix expression]
Repeat thru Step-7 while NEXT ‘’
Step-5: [Remove symbols with greater precedence from stack]
If TOP < 1
then Write(‘INVALID’)
Exit
Repeat while f(NEXT) < g(S[TOP])
TEMP POP(S, TOP)
POLISH POLISH O TEMP
RANK RANK + r(TEMP)
If RANK < 1
then Write(‘INVALID’)
Exit
Step-6: [Are there matching parenthesis?]
If f(NEXT) g(S[TOP])
then Call PUSH(S, TOP, NEXT)
else POP(S,TOP)
Step-7: [Get next input symbol]
NEXT NEXTCHAR(INFIX)
Step-8: [Is the expression valid?]
If TOP 0 or RANK 1
then Write(‘INVALID’)
else Write(‘VALID’)
Exit
(b)Write an algorithm for evaluation of postfix expression and evaluation the followingexpression showing every status of stack in tabular form.
(i) 5 4 6 + * 4 9 3 / + *
(ii) 7 5 2 + * 4 1 1 + / -
(i) 5 4 6 + * 4 9 3 / + *
| Character Scanned | Contents of Stack | Intermediate Result |
|---|---|---|
| 5 | 5 | |
| 5 | 5 4 | |
| 6 | 5 4 6 | 4 + 6 = 10 |
| + | 5 10 | 5 * 10 = 50 |
| * | 50 | |
| 4 | 50 4 | |
| 9 | 50 4 9 | |
| 3 | 50 4 9 3 | 9 / 3 = 3 |
| / | 50 4 3 | 4 + 3 = 7 |
| + | 50 7 | 50 * 7 = 350 |
| * | 350 |
| Character Scanned | Contents of Stack | Intermediate Result |
|---|---|---|
| 7 | 7 | |
| 5 | 7 5 | |
| 2 | 7 5 2 | 5 + 2 = 7 |
| + | 7 7 | 7 * 7 = 49 |
| * | 49 | |
| 4 | 49 4 | |
| 1 | 49 4 1 | |
| 1 | 49 4 1 1 | 1 + 1 = 2 |
| + | 49 4 2 | 4 / 2 =2 |
| / | 49 2 | 49 – 2 = 47 |
| - | 47 |
(i) ( A + B * C / D - E + F / G / ( H + I ) )
(ii) ( A + B ) * C + D / ( B + A * C ) + D
(i) ( A + B * C / D - E + F / G / ( H + I ) ) )
| Character Scanned | Contents of Stack | Reverse Polish Expression | Rank |
|---|---|---|---|
| ( | |||
| ( | ( ( | ||
| A | ( ( A | ||
| + | ( ( + | A | 1 |
| B | ( ( + B | A | 1 |
| * | ( ( + * | AB | 2 |
| C | ( ( + * C | AB | 2 |
| / | ( ( + / | ABC* | 2 |
| D | ( ( + / D | ABC* | 2 |
| - | ( ( - | ABC*D/+ | 1 |
| E | ( ( - E | ABC*D/+ | 1 |
| + | ( ( + | ABC*D/+E- | 1 |
| F | ( ( + F | ABC*D/+E- | 1 |
| / | ( ( + / | ABC*D/+E-F | 2 |
| G | ( ( + / G | ABC*D/+E-F | 2 |
| / | ( ( + / | ABC*D/+E-FG/ | 2 |
| ( | ( ( + / ( | ABC*D/+E-FG/ | 2 |
| H | ( ( + / ( H | ABC*D/+E-FG/ | 2 |
| + | ( ( + / ( + | ABC*D/+E-FG/H | 3 |
| I | ( ( + / ( + I | ABC*D/+E-FG/H | 3 |
| ) | ( ( + / | ABC*D/+E-FG/HI+ | 3 |
| ) | ( | ABC*D/+E-FG/HI+/+ | 1 |
| ) | ABC*D/+E-FG/HI+/+ | 1 |
| Character Scanned | Contents of Stack | Reverse Polish Expression | Rank |
|---|---|---|---|
| ( | |||
| ( | ( ( | ||
| A | ( ( A | ||
| + | ( ( + | A | 1 |
| B | ( ( + B | A | 1 |
| ) | ( | AB+ | 1 |
| * | ( * | AB+ | 1 |
| C | ( * C | AB+ | 1 |
| + | ( + | AB+C* | 1 |
| D | ( + D | AB+C* | 1 |
| / | ( + / | AB+C*D | 2 |
| ( | ( + / ( | AB+C*D | 2 |
| B | ( + / ( B | AB+C*D | 2 |
| + | ( + / ( + | AB+C*DB | 3 |
| A | ( + / ( + A | AB+C*DB | 3 |
| * | ( + / ( + * | AB+C*DBA | 4 |
| C | ( + / ( + * C | AB+C*DBA | 4 |
| ) | ( + / | AB+C*DBAC*+ | 3 |
| + | ( + | AB+C*DBAC*+/+ | 1 |
| D | ( + D | AB+C*DBAC*+/+ | 1 |
| ) | AB+C*DBAC*+/+D+ | 1 |
Make Comments..!!
