Computer Science · May / June 2022 · Paper 1 HL · Question 15

15. Reverse Polish notation (RPN) is a method used to represent mathematical expressions so they can be evaluated without the need for parentheses. An expression written in this form is known as postfix notation, whereas an expression written the traditional way is known as infix notation. For example: Infix notation: (8 – 5) * 7 Postfix notation: 8 5 – 7 * Both the infix and postfix expressions have the same result: 21 RPN expressions are evaluated from left to right as follows: y Each character is checked, ◦ if it is a digit, it is pushed onto a stack. ◦ if it is a mathematical operator, the last two digits are popped from the stack and evaluated as though the current operator was between them. The result of this operation is then pushed back onto the stack. y The process is repeated until all the characters in the RPN expression have been used. y The value left in the stack is the result of the expression. A collection named RPN already stores an expression formatted in Reverse Polish notation. The algorithm reads the values from the collection and, using a stack data structure, evaluates it. RPN.resetNext() loop while RPN.hasNext() VALUE = RPN.getNext() loop while not (VALUE = "+" or VALUE = "-" or VALUE = "*" or VALUE = "/") stack.push(VALUE) VALUE = RPN.getNext() end loop OPERAND2 = stack.pop() OPERAND1 = stack.pop() if VALUE = "+" then NEW_VAL = OPERAND1 + OPERAND2 stack.push(NEW_VAL) end if if VALUE = "-" then NEW_VAL = OPERAND1 - OPERAND2 stack.push(NEW_VAL) end if if VALUE = "*" then NEW_VAL = OPERAND1 * OPERAND2 stack.push(NEW_VAL) end if if VALUE = "/" then NEW_VAL = OPERAND1 / OPERAND2 stack.push(NEW_VAL) end if end loop RESULT = stack.pop() output "The result is: ", RESULT (This question continues on the following page) (Question 15 continued)

Read automatically from the paper; the printed page above is exact.