# Calculator

Calculator is a Scheme-like language that supports basic arithmetic operations.

## Syntax

Calculator has primitive expressions and call expressions:

• a primitive expression is number: `2` or `3.14`
• a call expression is a Scheme list that begins with an operator, followed by 0 or more expressions: `(+)`, `(* 1 2 3)`, `(/ 3 (+ 4 5))`

The legal operators are:

• `+`: sum of the arguments
• `*`: product of the arguments
• `-`: if one argument, negate it; else subtract the rest from the first
• `/`: if one argument, invert it; else divide the rest from the first

Here are some examples of Calculator in action:

```calc> (+ 2 2)
4
calc> (- 5)
-5
calc> (* (+ 1 2) (+ 2 3))
15```

## Building an interpreter

Given a Calculator expression, an interpreter evaluates its meaning. An interpreter consists of a parser and an evaluator.

### Parser

A parser analyzes an input string and describes the structure. It performs lexical analysis and syntactic analysis:

• lexical analysis (tokenization) divides the input string into meaningful tokens, such as punctuation marks and numbers
• syntactic analysis interprets a token sequence as an expression tree

#### Tokenization

In Calculator, the tokens are parentheses, numbers, and operators. The following `tokenize` function surrounds parentheses with spaces and invokes `split` (which splits a string into words using spaces as delimiters):

```def tokenize(s):
"""Splits string S into a list of tokens.
>>> tokenize('(* (+ 12 3) 5)')
['(', '*', '(', '+', '12', '3', ')', '5', ')']
"""
return s.replace('(', ' ( ').replace(')', ' ) ').split()```

#### Syntactic analysis

In our Calculator interpreter, we will represent expression trees as deep linked lists. We organize this stage into two mutually recursive functions: one for expressions (`read`) and one for operand lists (`read_tail`). Here they are:

```def read(tokens):
"""Read an expression from a sequence of tokens.
>>> exp = read(['(', '+', '2', '3', '6', ')'])
>>> print(exp)
< '+' 2 3 6 >
>>> print(exp)
< '*' 4 < '-' 12 8 > >
"""
if tokens == []:
raise SyntaxError('unexpected end of input')
token = tokens.pop(0)
if token == '(':
elif token == ')':
raise SyntaxError('unexpected )')
else:
return atom(token)

"""Read the rest of a list."""
if tokens == []:
raise SyntaxError('unexpected end of input')
elif tokens == ')':
tokens.pop(0) # pop off ')'
else:

def atom(token):
"""Try to coerce TOKEN into an int or a float; otherwise return TOKEN."""
try:
return int(token)
except ValueError:
try:
return float(token)
except ValueError:

`read` checks for various base cases, including empty input (error) and primitive expressions (which are converted from strings to their correct type through `atom`). A recursive call to `read_tail` is invoked whenever a `(` token indicates the beginning of a list.

`read_tail` continues to read from the same `tokens`, but expects to be called after a list has begun. Its base cases are an empty input (error) or a `)` token that terminates the list. Its recursive call reads the first element of the list with `read`, reads the rest of the list with `read_tail`, and then returns a list represented as a linked list.

Now we can write a function that represents the parsing stage:

```def parse(s):

### Evaluator

An evaluator discovers the form of an expression and executes the corresponding evaluation rule.

Primitive expressions evaluate to themselves. Call expressions are evaluated recursively:

• evaluate each operand expression
• collect their values as a list of arguments
• apply the operator to the argument list

`calc_eval` computes the value of an expression `exp`, which is either a number or a call expression:

```def calc_eval(exp):
"""Evaluate EXP."""
if type(exp) in (int, float): # number
return exp
elif isinstance(exp, Link): # call expression
args = exp.rest.map(calc_eval).to_list() # evaluate each argument and collect them in a list
return calc_apply(exp.first, args) # apply the operator
else:
raise SyntaxError('unknown expression')```

Assume that the linked list class supports `map` and `to_list`.

`calc_apply` applies an operator to a list of arguments:

```def calc_apply(operator, args):
if operator == '+':
return sum(args)
elif operator == '-':
if len(args) == 1:
return -args
else:
return args + sum([-arg for arg in args[1:]]) # args - args - args - ...
elif operator == '*':
return reduce(lambda x, y: x * y, args, 1)
elif operator == '/':
if len(args) == 1:
return 1 / args
else:
return reduce(lambda x, y: x * y, [1 / arg for arg in args[1:]], args) # args / args / args / ...```

Depending on what `operator` is, we decide how to treat the arguments.

An interactive session is supported by a read-eval-print loop (REPL): read an expression, evaluate it, print the result, and repeat.

For Calculator, the REPL looks like this:

```def repl():
while True:
try:
print(calc_eval(parse(input('calc> '))))
except (SyntaxError, ZeroDivisionError) as e:
print(type(e).__name__ + ':', e)```

### Final product

The entire source code can be viewed at Calculator/Source code.