IB Questionbank

User interface language: English | Español

Date	May 2022	Marks available	3	Reference code	22M.1.HL.TZ0.15
Level	HL	Paper	1	Time zone	no time zone
Command term	Explain	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 5: Abstract data structures » 5.1 Abstract data structures

Show 80 related questions

17N.1.HL.TZ0.13c:

Show the output produced by the following algorithm.

loop while (NOT FRUITS.isEmpty()) AND (NOT FLOWERS.isEmpty())
  X = FRUITS.pop()
  Y = FLOWERS.pop()
  if X < Y then
    output X
  else
    output Y
  end if
end loop

Hide related questions

Topic 5: Abstract data structures

Question

Markscheme

Examiners report

Syllabus sections

View options