Assignment
Q1. Convert the following infix expression into postfix
Infix Postfix
A + B-C*D
12 + 60 – 23
(A + B) ¬ (C ¬ D )
A ¬ B * C – D + E/F
12 + 60 + 23*35-2 AB + CD * -
1260 + 23 -
AB + CD - -
AB-CD- * EF / +
1260 + 2335 * + 2 -
Q2. Evaluate the following postfix expression using stack.
1 2 3 1 – 4 5 6 * + 7 * -
Write each step of this conversion using the following table.
Input Operator 1 Operator 2 value stack
1 1
2 2
1
3 3
2
1
1 1
3
2
1
3 1 3 3
2
1
2 3 8 8
1
- 1 8 7 7
4 1 8 7 4
7
5 1 8 7 5
4
7
6 1 8 7 6
5
4
7
* 5 6 30 30
4
7
+ 4 30 34 34
7
7 4 30 34 7
34
7
* 34 7 238 238
7
- 7 238 231 231
Evaluation of expression
1 2 3 1 – 4 5 6 * + 7 * -
1. Our first number is 1 , as 1 is operand so we will push it on the stack
2. The next element is 2 , which will be pushed on stack also. Now the recent most element is 2 in stack.
3. The next element is 3 , which will be pushed on stack also. Now the recent most element is 3 in stack.
4. The next element is 1 , which will be pushed on stack also. Now the recent most element is 1 in stack.
5. Now the next element is , which is operator . Now we will pop two operands from stack which are 1 & 3 . The operator () will be applied to 1 and 3 and result (3) is written in value and pushed in stack also.
6. Now the next element is , which is operator . Now we will pop two operands from stack which are 3 & 2 . The operator () will be applied to 3 and 2 and result (8) is written in value and pushed in stack also.
7. Now the next element is ( - ) which is operator . The operand 8 & 1 from stack will be popped out and (-) is applied to them. The most recent will be written in Operator 2 column and 1 in operator 1 column. The result ( 7) will be written in value column and pushed to stack also.
8. At this stage the most recent element is 7 , the next element in expression is 4.
As this is operand so it will be pushed to stack. Now the most recent is 4.
9. Now the next element is 5 , since it is also operand so it will be also pushed to
stack. Now the most recent is 5 in the stack and are placed like ( 5 , 4 & 7 ) respectively.
10. Now the next element is 6 , since it is also operand so it will be also pushed to
stack. Now the most recent is 6 in the stack and are placed like ( 6, 5 , 4 & 7 ) respectively.
11. Now in turn comes the operator ( * ) , the two most recent element is 6 & 5 .
Element 6 in Op2 column and 5 in Op1 column , the result (30) will be written in value and also pushed to stack.
12. Next element of expression is operator ( + ) , the two most recent element is
30 & 4 , so the result (34) is written in value column and also pushed to stack.
13. The next element in expression is 7 which is operand so it will be pushed to
top of stack and shown as ( 7 , 34 & 7 ) respectively. The 7 been the most
recent element in stack.
13. Now in turn comes the operator ( * ) , the two most recent element is 7 & 34 .
Element 7 in Op2 column and 34 in Op1 column , the result (238) will be written in value and also pushed to stack.
14. The last element in expression is operator (-) , the most recent element from the stack 238 and 7 are subtracted and the result ( 231) is written to the value and also in stack also.
231 = Answer
Q1. Convert the following infix expression into postfix
Infix Postfix
A + B-C*D
12 + 60 – 23
(A + B) ¬ (C ¬ D )
A ¬ B * C – D + E/F
12 + 60 + 23*35-2 AB + CD * -
1260 + 23 -
AB + CD - -
AB-CD- * EF / +
1260 + 2335 * + 2 -
Q2. Evaluate the following postfix expression using stack.
1 2 3 1 – 4 5 6 * + 7 * -
Write each step of this conversion using the following table.
Input Operator 1 Operator 2 value stack
1 1
2 2
1
3 3
2
1
1 1
3
2
1
3 1 3 3
2
1
2 3 8 8
1
- 1 8 7 7
4 1 8 7 4
7
5 1 8 7 5
4
7
6 1 8 7 6
5
4
7
* 5 6 30 30
4
7
+ 4 30 34 34
7
7 4 30 34 7
34
7
* 34 7 238 238
7
- 7 238 231 231
Evaluation of expression
1 2 3 1 – 4 5 6 * + 7 * -
1. Our first number is 1 , as 1 is operand so we will push it on the stack
2. The next element is 2 , which will be pushed on stack also. Now the recent most element is 2 in stack.
3. The next element is 3 , which will be pushed on stack also. Now the recent most element is 3 in stack.
4. The next element is 1 , which will be pushed on stack also. Now the recent most element is 1 in stack.
5. Now the next element is , which is operator . Now we will pop two operands from stack which are 1 & 3 . The operator () will be applied to 1 and 3 and result (3) is written in value and pushed in stack also.
6. Now the next element is , which is operator . Now we will pop two operands from stack which are 3 & 2 . The operator () will be applied to 3 and 2 and result (8) is written in value and pushed in stack also.
7. Now the next element is ( - ) which is operator . The operand 8 & 1 from stack will be popped out and (-) is applied to them. The most recent will be written in Operator 2 column and 1 in operator 1 column. The result ( 7) will be written in value column and pushed to stack also.
8. At this stage the most recent element is 7 , the next element in expression is 4.
As this is operand so it will be pushed to stack. Now the most recent is 4.
9. Now the next element is 5 , since it is also operand so it will be also pushed to
stack. Now the most recent is 5 in the stack and are placed like ( 5 , 4 & 7 ) respectively.
10. Now the next element is 6 , since it is also operand so it will be also pushed to
stack. Now the most recent is 6 in the stack and are placed like ( 6, 5 , 4 & 7 ) respectively.
11. Now in turn comes the operator ( * ) , the two most recent element is 6 & 5 .
Element 6 in Op2 column and 5 in Op1 column , the result (30) will be written in value and also pushed to stack.
12. Next element of expression is operator ( + ) , the two most recent element is
30 & 4 , so the result (34) is written in value column and also pushed to stack.
13. The next element in expression is 7 which is operand so it will be pushed to
top of stack and shown as ( 7 , 34 & 7 ) respectively. The 7 been the most
recent element in stack.
13. Now in turn comes the operator ( * ) , the two most recent element is 7 & 34 .
Element 7 in Op2 column and 34 in Op1 column , the result (238) will be written in value and also pushed to stack.
14. The last element in expression is operator (-) , the most recent element from the stack 238 and 7 are subtracted and the result ( 231) is written to the value and also in stack also.
231 = Answer
Post a Comment