The Gateway to Computer Science Excellence
+3 votes
2.4k views

How many PUSH and POP operations will be needed to evaluate the following expression by reverse polish notation in a stack machine $(A ∗ B) + (C ∗ D/E)$? 

  1. $4$ PUSH and $3$ POP instructions
  2. $5$ PUSH and $4$ POP instructions 
  3. $6$ PUSH and $2$ POP instructions
  4. $5$ PUSH and $3$ POP instructions
in DS by Boss (30.8k points)
recategorized | 2.4k views
–1

..........?

0
WHY PUSH AB IS TREATED AS SINGLE PUSH PUSH A PUSH B ARE 2 SEPERATE PUSH OPERATIONS
0

@sanjay they have asked operation not operand, in postfix evaluation algo we generally  push operand onto the stack I have considered then operation thats why 6 push . if i would have considered them seperate and as a operand then push of operand onto the stack would be even more.

0

 two push operands in single operation is not possible . doesn't matter whether push operation increases or not we can not leave basic thing behind .something else in missing in the question 

0
@sanjay this is what i told in the answer ....just by doing some manupulation on it i tried to make the sol as close  as possible to the given options .if i would do it with proper postfix evaluation method then ans would be entierly different..So either i did not understand the question what exactly they meant by operation or no option is correct.
0
are all the options wrong?

mine is coming different...

4 Answers

+3 votes
ab* cde /* +

push a push b

encounter *

pop b  pop a push a*b

push c push d push e

encounter /

pop d pop e push d/e

encounter *

pop c pop d/e push c*d/e

enounter +

pop a*b pop c*d/e push a*b + c*d/e

9 push 8 pop

 

theres no option
by Active (3.8k points)
0
Even I am getting 9 Push and 8 Pop operations. But, shouldn't the postfix be :

(AB*)(CD*E/)+

Since * and / operators have equal precedence and left associativity, so

(C*D/E) => ((C*D)/E) => ((CD*)/E) => (CD*E/)
0
i think it is only talking about operator stack
for that
6 push ( * + ( + /
2 pop second * and +
+1

I thing you have written wrong postfix expression it should be  AB*CD*E/+ not AB* CDE /* +  

Though your procedure is right

+1 vote
Reverse polish notation is a system of formula notation without brackets or special punctuation. To evaluate (A ∗ B) + (C ∗ D / E): First avoid brackets and punctuation and convert it into postfix form i.e. AB+CDE/*+ Now push AB On * pop AB and perform A * B. Now push back the result(say it X). Push CDE. On / pop DE and push back the result(say it Y). On * Pop CY and perform * operation and push the result(say it z). On + pop XZ and perform + opeeration and and push back the final answer. Above computation include 5 PUSH and 4 POP instructions. So, option (B) is correct.
by (27 points)
0 votes

The algorithm for evaluating any postfix expression is fairly straightforward:

  • While there are input tokens left
    • Read the next token from input.
    • If the token is a value
      • Push it onto the stack.
    • Otherwise, the token is an operator (operator here includes both operators and functions).
      • It is already known that the operator takes n arguments.
      • If there are fewer than n values on the stack
        • (Error) The user has not input sufficient values in the expression.
      • Else, Pop the top n values from the stack.
      • Evaluate the operator, with the values as arguments.
      • Push the returned results, if any, back onto the stack.
  • If there is only one value in the stack
    • That value is the result of the calculation.
  • Otherwise, there are more values in the stack
    • (Error) The user input has too many values Here

 

5 push and 4 pop (B)

by Loyal (8.5k points)
0
How u got 5 push and 4 pops... With the same algorithm u mentioned I am getting 9 push and 8 pops
0 votes
It is B

5 variable so 5 Pushes

4 operators so 4 pops
by (59 points)
0
What is the logic behind this. I am getting 9 push and 8 pops with the algorithm specified in the various textbooks
Answer:

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,362 answers
198,492 comments
105,260 users