Code School of Analytics
ExpertAlgorithms50 points

Pocket calculator with exact fractions

A tutoring app for school students lets them type arithmetic expressions and shows the exact answer. You must build the engine. Expressions use non-negative whole numbers, the operators + - * /, round brackets, and optional spaces between tokens.

The grammar is:

  • expr = term { (+|-) term }
  • term = unary { (*|/) unary }
  • unary = - unary | primary
  • primary = NUMBER | ( expr )

So --3 is valid (it equals 3) and 2*-3 is valid, but 2++3, (), 2(3), 1 2 (two numbers in a row) and any other character like ^ are syntax errors. Division is exact, never rounded.

Task: line 1 is N; then N expressions, one per line. For each print the exact value: an integer such as -12, or a fraction in lowest terms p/q with a positive denominator and the sign on the numerator, such as -7/2. Print SYNTAX ERROR if the line breaks the grammar. Otherwise, if a division by zero happens anywhere in the evaluation, print DIVISION BY ZERO. Syntax is always checked first, for the whole line.

Sample tests

Input

5
2 + 3 * 4
(2 + 3) * 4
7 / 2
-(1 + 2) * 3
10 / (5 - 5)

Expected output

14
20
7/2
-9
DIVISION BY ZERO

Input

3
2++3
--3
2*-3

Expected output

SYNTAX ERROR
3
-6

Your answer is also checked against 3 hidden tests.

Need a hint?

Write one function per grammar rule (expr, term, unary, primary). Tokenise first, parse the whole line, and only then evaluate.