IB Questionbank

User interface language: English | Español

Date	May 2022	Marks available	6	Reference code	22M.1.HL.TZ0.15
Level	HL	Paper	1	Time zone	no time zone
Command term	Copy and Complete	Question number	15	Adapted from	N/A

Question

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:

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.
The process is repeated until all the characters in the RPN expression have been used.
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

An alternative data structure in which the expression used in part (a) may be stored is a binary tree. If the tree is traversed using postorder tree traversal, the output is formatted in RPN.

Copy and complete the trace table for the algorithm using the RPN collection data:

5 2 + 25 16 − * 3 /

[6]

Explain why a stack is used in the process of evaluating the expression in the algorithm.

[3]

Outline the steps involved in traversing the given tree using postorder tree traversal.

[4]

State the output from the given tree using inorder tree traversal.

[2]

Markscheme

Award [6 max]
Award [1] for correct values in VALUE column;
Award [1] for correct values of OPERAND2, OPERAND1 and NEW_VAL when VALUE is ‘+’;
Award [1] for correct values of OPERAND2, OPERAND1 and NEW_VAL when VALUE is ‘-’;
Award [1] for correct values of OPERAND2, OPERAND1 and NEW_VAL when VALUE is ‘*’;
Award [1] for correct values of OPERAND2, OPERAND1 and NEW_VAL when VALUE is ‘/’;
Award [1] correct output: ‘The result is: 21’;

Note: The trace table may be differently presented.

Note: Allow Follow Through.

Award [3 max]
A stack is a last in first out (LIFO) / first in last out (FILO) data structure;
…which means data is popped off the stack in the reverse order to which it was pushed;
In the expression, it is important to evaluate some of the values in a certain order(to obtain the correct result);
For example, 25 − 16 would give the wrong value if it was evaluated as 16 − 25;

Pushing items onto a stack and then popping them off reverses the order;
To evaluate e.g. “10 2 /” we must treat it as “do the operation on the operands 10 and 2”/ i.e. we have to access the operator before we can apply it to the operands;
A stack achieves the reversing of the order of the operators and their operands as a group (but it also reverses the operands which must be fixed);

Award [4 max]
Start from the root node;
If the root is null, return immediately;
Traverse left subtree;
Traverse right subtree;
Visit root;

start from the root node (for example traverse (root)) ;
terminate traversal (and backtrack) when/if root equals null;
(before visiting the root node) traverse (and visit/process/output) each node in the left subtree (i.e., traverse(root.left));
(before visiting the root node) traverse (and visit/process/output) each node in the right subtree (i.e., traverse(root.right));
visit/output/process root (for example, output(root));

Award [2 max]
Award [1] if the answer contains no more than one error.

(5+2)*(25−16)/3

Note to examiners: Ignore the brackets – these represent the completely correct mathematical expression, but they are not read from the tree. Some candidates might include them because they realise that they may be needed so the expression works correctly.

Examiners report

Most candidates had difficulty tracing the algorithm in Part (a).

There were some candidates who did not attempt question 15.

Part (b) was reasonably well answered with many gaining at least 1 or 2 of the marking points.

Only a few candidates earned full marks in Part (c).

[N/A]

Syllabus sections

Topic 4: Computational thinking, problem-solving and programming » 4.2 Connecting computational thinking and program design

Show 59 related questions

18M.1.SL.TZ0.12a:

The collection DATA contains the following data:

2, 4, 1, −2, −4, 1, 0

Consider the following pseudocode:

COUNTER = 0
SUM = 0
DATA.resetNext()
loop for X from 0 to 6
  if DATA.getNext() > 0
    ARRAY[X] = DATA.getNext()
    COUNTER = COUNTER + 1
    SUM = SUM + ARRAY[X]
  end if
end loop
output SUM/COUNTER

Trace the pseudocode using the table below:

18N.1.SL.TZ0.7:

Construct a trace table for the following algorithm

A = 3
B = 7
loop while B >= A
  A = A + 1
  output(B − A)
  B = B − 1
end loop

19N.1.SL.TZ0.7:

Construct a trace table for the following algorithm.

K = 1
N = 1
M = 2
loop while K < 5
   output(N,M)
   K = K + 1
   N = N + 2
   M = M * 2
end loop

21M.1.SL.TZ0.8:

List the output from the given algorithm for the following input.

2, 6, 8, 9, 12, 15, 18, 20

loop for Count from 0 to 7
    input NUMBER
    if NUMBER div 2 = NUMBER / 2 then
        if NUMBER div 3 = NUMBER / 3 then
        output NUMBER
        end if
    end if
end loop

19N.1.SL.TZ0.10a:

Consider the following algorithm.

N = 372
X = N DIV 100
Y = X + 10 * (N MOD 100 DIV 10)
Z = Y + (N MOD 10) * 100

Determine the values of variables X, Y, and Z after execution of this algorithm. Show your working.

19M.2.SL.TZ0.4b:
Using the rules and initial values above, construct the pseudocode that would enable the area of the sea ice and the sea level rise to be calculated if there was an increase of 0.04 °C in the ocean surface temperature.

Hide related questions

Topic 4: Computational thinking, problem-solving and programming

Question

Markscheme

Examiners report

Syllabus sections

View options