Expression Evaluation and Polish Notation
Cambridge Computer Science Tripos Part IA -- 2025 -- Paper 1, Question 2
The following type definition allows the representation of some mathematical expressions as an OCaml value:
type expr =
| Add of expr * expr
| Mul of expr * expr
| Number of intPart (a): Encoding an expression
Write the OCaml value that corresponds to the expression (1+4)*(10+2).
let example : expr = failwith "TODO"let () =
match example with
| Mul (Add (Number 1, Number 4), Add (Number 10, Number 2)) ->
print_endline "Correct!"
| _ ->
print_endline "Not quite -- check the structure of your expression."Part (b): Evaluating expressions
Write a function that will evaluate the numerical result of an expr argument.
let rec eval (e : expr) : int = failwith "TODO"let () =
let tests = [
(Number 42, 42);
(Add (Number 1, Number 2), 3);
(Mul (Number 3, Number 4), 12);
(Mul (Add (Number 1, Number 4), Add (Number 10, Number 2)), 60);
] in
List.iter (fun (e, expected) ->
let got = eval e in
if got = expected then
Printf.printf "eval => %d (correct)\n" got
else
Printf.printf "eval => %d (expected %d)\n" got expected
) testsPart (c): Polish notation tokens
Another way to represent these expressions is to use "Polish notation". In this notation, the operator precedes its operands, and unlike the usual infix notation there is no need for parentheses. For example, the expression in part (a) would be written:
* + 1 4 + 10 2
Define a type t that could be used in a list to represent any expression that can be described with type expr above.
(* Define your type t here *)
type t = TODOHint
You need three kinds of token: one for each operator, and one for numbers. A t list should be able to represent any Polish notation expression.
Part (d): One step of reduction
The Polish notation expression above can be reduced step by step:
* + 1 4 + 10 2
* 5 + 10 2
* 5 12
60
Once you have defined your type t, write a function reduce that performs one step of reduction. It should find the leftmost operator that is followed by two numbers and replace all three tokens with a single number.
Here is one possible type definition for t and a framework for reduce:
(* A possible type definition -- adjust to match your own *)
type t = Plus | Times | Num of intlet rec reduce (tokens : t list) : t list = failwith "TODO"Try it out:
let show ts =
String.concat " " (List.map (function
| Plus -> "+"
| Times -> "*"
| Num n -> string_of_int n
) ts)
let () =
let start = [Times; Plus; Num 1; Num 4; Plus; Num 10; Num 2] in
Printf.printf "Step 0: %s\n" (show start);
let step1 = reduce start in
Printf.printf "Step 1: %s\n" (show step1);
let step2 = reduce step1 in
Printf.printf "Step 2: %s\n" (show step2);
let step3 = reduce step2 in
Printf.printf "Step 3: %s\n" (show step3)Part (e): Full reduction
Write a function reduce_all that reduces a t list until it cannot be simplified any further, and returns the simplest value.
let rec reduce_all (tokens : t list) : t list = failwith "TODO"let () =
let tests = [
([Num 42], "42 (single number)");
([Plus; Num 3; Num 4], "3 + 4");
([Times; Plus; Num 1; Num 4; Plus; Num 10; Num 2], "(1+4) * (10+2)");
([Plus; Times; Num 2; Num 3; Times; Num 4; Num 5], "(2*3) + (4*5)");
] in
List.iter (fun (tokens, desc) ->
let result = reduce_all tokens in
Printf.printf "%s => %s\n" desc (show result)
) tests