Expression is combination of operand and operator. Three type of expression that are these
Prefix expression.(+ab).
Infix expression(a+b).
Postfix expression.(ab+).
To evaluate expression if expression in infix form than convert into postfix form and than postfix expression is solved using stack.
Steps to evaluate postfix expression using stack
P is an postfix expression to solve this postfix expression stack is used to hold operands and RESULT hold the result of arithmetic expression.
Step 1. Add right parenthesis ")" at the end of P.
Step 2. Scan postfix expression P from left to right and repeat step 3 and 4 until the ")" is encountered.
Step 3. If an operand is encountered put it on STACK.
Step 4. If an operator "op" is encountered then
Remove the top two element from the stack and evaluate A op B and place the result on the stack.
Step 5. Set RESULT equal to the top element on STACK.
Step 6. Exit.
Example
Evaluate postfix expression P using stack
P: 3, 2, 1,+,*,13,3 ,/,-
Solution
First add right parentheses at the end of the P.
3,2,1,+,*,12,3,/,- ,)
element of P scanned left to right and store in stack if operand
Symbol scanned STACK
3 3
2 3,2
1 3,2,1
+ 3,3
* 9
12 9,12
3 9,12,3
/ 9,4
- 5
)
So Result=5 after solving postfix expression using stack .
First 3,2,1, is operand simply push on STACK.
Operand "+" encountered remove top two element of stack and evaluate and again store result in stack.
2+1=3
Operand "*" encountered remove top two element of stack and evaluate and again store result in stack.
3*3=9.
12,3 is operand simply push on stack.
Operand "/" encountered remove top two element of stack and evaluate and again store result in stack.
12/3=4
Operand "-" encountered remove top two element of stack and evaluate and again store result in stack.
9-4=5
sentinel element ")" encountered then exit.
0 Comments