Calculator/Source code

From CS 61A Wiki
Revision as of 09:28, 21 July 2014 by Axis (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Jump to: navigation, search
from functools import reduce
 
"""Parser"""
def parse(s):
    return read(tokenize(s))
 
def tokenize(s):
    """Splits string S into a list of tokens.
    >>> tokenize('(* (+ 12 3) 5)')
    ['(', '*', '(', '+', '12', '3', ')', '5', ')']
    """
    return s.replace('(', ' ( ').replace(')', ' ) ').split()
 
def read(tokens):
    """Read an expression from a sequence of tokens.
    >>> exp = read(['(', '+', '2', '3', '6', ')'])
    >>> print_linked_list(exp)
    < '+' 2 3 6 >
    >>> exp = read(['(','*','4','(','-','12','8',')',')','3','2'])
    >>> print_linked_list(exp)
    < '*' 4 < '-' 12 8 > >
    """
    if tokens == []:
        raise SyntaxError('unexpected end of input')
    token = tokens.pop(0)
    if token == '(':
        return read_tail(tokens)
    elif token == ')':
        raise SyntaxError('unexpected )')
    else:
        return atom(token)
 
def read_tail(tokens):
    """Read the rest of a list."""
    if tokens == []:
        raise SyntaxError('unexpected end of input')
    elif tokens[0] == ')':
        tokens.pop(0) # pop off ')'
        return empty
    else:
        return link(read(tokens), read_tail(tokens)) # read the next expression, whether it be a number or a combination, and link it with the rest of the list
 
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:
            return token
 
"""Evaluator"""
def calc_eval(exp):
    """Evaluate EXP."""
    if type(exp) in (int, float): # numbers
        return exp
    else: # call expression
        args = to_list(map_linked_list(calc_eval, rest(exp))) # evaluate each argument and collect them in a list
        return calc_apply(first(exp), args) # apply the operator
 
def calc_apply(operator, args):
    if operator == '+':
        return sum(args)
    elif operator == '-':
        if len(args) == 1:
            return -args[0]
        else:
            return args[0] + sum([-arg for arg in args[1:]]) # args[0] - args[1] - args[2] - ...
    elif operator == '*':
        return reduce(lambda x, y: x * y, args, 1)
    elif operator == '/':
        if len(args) == 1:
            return 1 / args[0]
        else:
            return reduce(lambda x, y: x * y, [1 / arg for arg in args[1:]], args[0]) # args[0] / args[1] / args[2] / ...
 
"""REPL"""
def repl():
    while True:
        try:
            print(calc_eval(parse(input('calc> '))))
        except SyntaxError as e:
            print(e)
 
"""Linked list functions"""
empty = lambda: 42
 
def link(element, lst):
    return element, lst
 
def first(lst):
    return lst[0]
 
def rest(lst):
    return lst[1]
 
def linked_list_to_str(lst):
    s = '< '
    while lst != empty:
        if type(first(lst)) == tuple: # assume that linked lists don't contain tuples as elements
            s += linked_list_to_str(first(lst)) + ' '
        else:
            s += repr(first(lst)) + ' '
        lst = rest(lst)
    return s + '>'
 
def print_linked_list(lst):
    print(linked_list_to_str(lst))
 
def map_linked_list(f, lst):
    if lst == empty:
        return empty
    else:
        return link(f(first(lst)), map_linked_list(f, rest(lst)))
 
def to_list(lst):
    result = []
    while lst != empty:
        result.append(first(lst))
        lst = rest(lst)
    return result
 
# run REPL when script is run
if __name__ == '__main__':
    repl()