3. (2 pts) An RPN expression can be stored in a list as follows rpn Recall the a

Question

3. (2 pts) An RPN expression can be stored in a list as follows rpn Recall the algorithm to compute the value of a valid RPN expression using a stack [23, 3, "-", 4, 6, "+", "1"] = 1. Set i equal to O 2. Set x equal to rpnlij 3. Set s equal to an empty stack. 4. While i is not equal to the length of the rpn list, do the following a. If x is a number, then push x on stack s b. If x is a string (i.e. operator), then do the following i. Pop stack s and store number in b ii. Pop stack s and store number in a ii. If operator is"+", push a b on stack s iv. If operator is"-", push a -b on stack s. v. If operator is"*", push a b on stack s vi. If operator is"/", push a Ib on stack s c. Add 1 to i 5. Pop stack s and return this number as the final result. Trace how this algorithm computes the value of the following RPN expression stored as a list rpn [9, 3, "+", 7, 5, "-", "*", 6, 2, "1", 1, "+", "1"] = Complete a new stack trace whenever a number is pushed or popped to show how the stack progresses throughout the computation. The first three stack traces are shown for you. Use Courier 12 pt font to make the spacing easier to handle if you type answers 3 99 12 Final result returned: (@INvilao10233542

Explanation / Answer

Given rpn = [9,3,”+”,7,5,”-”,”*”,6,2,”/”,1,”+”,”/”]

According to the given algorithm the stack contents are shown here:

The stack traces are given below:

Stack 1: new number 9 is pushhed

  

9

Stack 2: new number 3 is pushhed

3

9

Stack 3:+ is operator so 9+3=12 is pushed

12

Stack 4: new number 7 is pushhed

7

12

Stack 5: new number 5 is pushhed

5

7

12

Stack 6:- is operator so 7-5=2 is pushed

2

12

Stack 7: * is operator so 12*2=24 is pushed

24

Stack 8: new number 6 is pushhed

6

24

Stack 9: new number 2 is pushhed

2

6

24

Stack 10: / is operator so 6/2=3 is pushed

3

24

Stack 11: new number 1 is pushhed

1

3

24

Stack 12: + is operator so 3+1=4 is pushed

4

24

Stack 13: / is operator so 24/4=6 is pushed

6

RPN Expression is ended here; the stack top element is 6; hence

Final result returned : 6

/*If this helps you, please let me know by giving a positive thumbs up. In case you have any queries, do let me know. I will revert back to you. Thank you!!*/

  

9

Related Questions

Navigate

• Browse (All)
• Browse 3
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.