A-LevelComputer ScienceAlgorithm design and problem-solving9618/31 · May/June 2021 · Q48 Marks

Explain why Reverse Polish Notation (RPN) is used to carry out the evaluation of expressions.

(a)(i)Explain why Reverse Polish Notation (RPN) is used to carry out the evaluation of expressions.[2]
(a)(ii)Identify, with reasons, a data structure that could be used to evaluate an expression in RPN.[2]
(b)Write the infix expression in RPN. (a - b) * (a + c) / 7[1]
(c)Write the RPN expression as an infix expression. a b / 4 * a b + -[1]
(d)Evaluate the RPN expression: a b + c d / / where a = 17, b = 3, c = 48 and d = 12. Show your working.[2]

Mark scheme

Marking points from the official mark scheme (May/June 2021). The mark or mark type is shown in brackets.

[1] (a)(i) Reverse Polish Notation provides an unambiguous method of representing an expression
[1] (a)(i) It is read from left to right // without the need to use brackets // with no need for rules of precedence / BODMAS
[1] (a)(ii) Structure: stack
[1] (a)(ii) Reason for stack: The operands are popped from the stack in the reverse order to how they were pushed
[1] (a)(ii) Structure: Binary tree
[1] (a)(ii) Reason for binary tree: A (binary) tree allows both infix and postfix to be evaluated (tree traversal)
[1] (b) a b - a c + * 7 /
[1] (c) a / b * 4 - (a + b)
[1] (d) Correct structure: (a + b) / (c / d)
[1] (d) Correct substitution and evaluation: (17 + 3) / (48 / 12) = 20 / 4 = 5

On Oracle Prep you can write or photograph your own answer and have it marked by AI against this mark scheme, with feedback on what you missed.