Question

Show the steps undertaken by a stack architecture machine to evaluate, [3 * 4 + 5 * 6] operation.

Answer 1

For solving infix notation expression like this , we can use stack architecture as follows: -

1. First convert the infix expression to postfix expression by follows: -

a) Scan the expression from left to right and for each token follow below steps. : -

if it is operand then print it, if it is operator(A) then

i) if there is already one operator(B) in stack and the operator A is having more precedence then operator B, then push operator A in stack.

ii) if the stack was initially empty, then print the operator A.

iii) if A is having less precedence than B , then pop B from stack and then push A when , the stack is empty of the element on top of stack is having less precedence than A.

eg .. 3 * 4 + 5 * 6 for this one,

we print 3, then push * to stack.

then we print 4, so we have expression 34 now and stack has *.

now we get +, as + is having less precedence than *,so we pop out * and push + .. So out current expression is 34* and stack has +.

Similarly we can have the complete expression converted to postfix as below: -

3 4 * 5 6 * +

2) now for solving this expression, we will push operands to stack and whenever any operator comes, we'll pop out two latest operands i.e. two operands from top of stack and solve the expression and push it again to stack. It is shown as below: -

1. Stack : - 3

2. Stack: - 3,4

3: Stack : - 12 ( as we got * so we pop out 3 and 4 and solved it and pushed the result to stack )

4. Stack 12,5

5. Stack: 12,5,6

6: Stack: 12.30 (Similary to step 3, we solved 5*6 = 30)

7: Stack: 42 ( As we encountered + operator and last two operands were 12 and 30)

So Ans is 42