Stack application of in Expression evaluation
Expression: Combination of operator and operands
Operands: A to Z (or) a to z (or) 1 to ..
Operator: ( ), { }. ^,*,/,+,-
1. Prefix: in the stack notation, prefix means operator exists before the operands
Eg: a+b +ab
Here, a+b mathematical notation converted into prefix notation +ab
2. Infix: in the stack notation, infix means the operator between the operands
Eg: a+b a+b
Here, a+b mathematical notation converted into infix notation a+b
3. Postfix: in the stack notation, postfix means operator exists after the operands
Eg: a+b ab+
Here, a+b mathematical notation converted into postfix notation ab+
Application of stack:
1. Evaluation of postfix expression
2. Converting infix to postfix expression
3. Converting infix to prefix expression
Evaluation of postfix expression
Algorithm:
1. Read postfix expression from left to right
2. If reading character is an operand, then push the operand on to a stack
3. If reading character is an operator, then pop top most 2 elements, consider them as op2,
op1. Perform one operation on op1 and op2 based on operator and push the result on the
stack
4. After procession entire postfix expression, the result is available on top of stack
Example problems:
231*+9-
Steps:
In the expression, first character is ‘2’ operand, then push(2)
In the expression, second character is ‘3’ operand, then push(3)
3
2
In the expression, third character is ‘1’ operand, then push(1)
1
3
2
In the expression, 4th character is ‘*’ operator, then pop top most 2 elements, consider op2 = 1,
op1 =3, Perform op1 * op2 1 *3 = 3, push the result on the stack [push (3)]
3
2
In the expression, 5th character is ‘+’ operator, then pop top most 2 elements, consider op2 = 3,
op1 =2, Perform op1 + op2 3 + 2 = 5, push the result on the stack [push (5)]
In the expression, 6th character is ‘9’ operand, then push(9)
9
5
In the expression, 7th character is ‘-’ operator, then pop top most 2 elements, consider op2 = 9,
op1 =5, Perform op1 + op2 5 - 9 = -4 , push the result on the stack [push (-4)]
-4
Final answer is: -4
Example problems for Postfix expression:
1. 13 - 4*
2. 4 3 15 / -
3. 100 200 + 2 / 5 * 7 +
4. 6523+8*+3+*
5. 723+-382/+2^3+
6. AB+CD-*
7. ABC+*D/
Converting Infix to postfix expression
Algorithm:
1. Read infix expression from left to right
2. If symbol is left parenthesis ‘(‘ then push it on to the stack
3. If symbol is operand, then add it to the postfix expression
4. If symbol is operator, then check push operator on to the stack
a. If stack is empty then push operator on the stack
b. If stack is not empty then check priority of operator
i. If reading operator has higher propriety then priority of stack’s top
most operator them push it on the stack
ii. If priority of reading operator <= priority of operator presents at top of
stack then pop the operator & add it the postfix expression
5. If symbol is right parenthesis ‘)’ then pop all the symbols from the stack and places
then in postfix expression until we get ‘(‘ which is popped it shouldn’t place in postfix
expression
6. After completion of reading infix expression, if stack is not empty then pop all the
symbols from stack & add to postfix expression
Rules table:
Naming Symbolic Priority Flow of execute
Brackets ( ) Highest Left
Cap / power ^ High Right
Division / /* Medium left
Multiplication
Addition / +- Low Left
substractions
Example:1
INFIX NOTATION : (A + B / C * D -)
Infix (Read character) Stack Postfix (output)
( (
A
(
+ + A
(
B AB
+
(
/ / AB
+
(
C ABC
/
+
(
* * ABC/
+
(
D * ABC/D
+
(
- - ABC/D*+
(
) ) ABC/D*+-
-
(
Example:2
INFIX NOTATION :((A + B) – C * (D / E)) + F
INFIX (READ CHARACTER) STACK POSTFIX (OUTPUT)
( (
( (
(
A ( A
(
+ + A
(
(
B + AB
(
(
) ) AB+
+
(
(
- - AB+
(
C - AB+C
(
* * AB+C
-
(
( ( AB+C
*
-
(
D ( AB+CD
*
-
(
/ / AB+CD
(
*
-
(
E / AB+CDE
(
*
-
(
) ) AB+CDE
/
(
*
-
(
) ) AB+CDE/
*
-
(
+ + AB+CDE/*-
F + AB+CDE/*-F+
OUTPUT POSTFIX IS: AB+CDE/*-F+
Example problems on infix to postfix conversion
Infix notation:
1. A+B*C+D
2. (p+q)*(m-n)
3. a+b*(c^d-e)^(f+g*h)-i
4. x^y/(5*z)+2
5. K + L - M*N + (O^P) * W/U/V * T + Q
6. (7+5*3/5^1+(3-2))
Converting Infix to prefix expression
Algorithm:
Step -1: reverse the given infix notation
Step -2: apply postfix
Step-3: reverse postfix
Example:1
Infix notation: a+b*c/d^f
Sol: step 1: reverse the given infix notation
F^d/c*b+a
INFIX (READ CHARACTER) STACK POSTFIX (OUTPUT)
F F
^ ^ F
D ^ FD
/ / FD^
C / FD^C
* * FD^C/
B * FD^C/B
+ + FD^C/B*
A + FD^C/B*A
FD^C/B*A+
Step 2: postfix FD^C/B*A+
Step 3: reverse postfix expression
+A*B/C^DF
prefix expression(output): +A*B/C^DF
Example problems on infix to prefix conversion
Infix notation:
1. a*b+c/d
2. x+y*z/w+u
3. a * ( b + c + d)
4. (a-b/c)*(a/k-l)
5. 3+5*(5/5)-2^2
6. K + L - M * N + (O^P) * W/U/V * T + Q
