Calculator/Source code

From CS 61A Wiki
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(exp)
    < '+' 2 3 6 >
    >>> exp = read(['(','*','4','(','-','12','8',')',')','3','2'])
    >>> print(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 Link.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
    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')
 
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, ZeroDivisionError) as e:
            print(type(e).__name__ + ':', e)
 
"""Linked list class"""
class Link:
    def __init__(self, elem, lst):
        self.first = elem
        self.rest = lst
 
    def map(self, f):
        if self != Link.empty:
            self.first = f(self.first)
            self.rest.map(f)
        return self
 
    def to_list(self):
        result = []
        lst = self
        while lst != Link.empty:
            result.append(lst.first)
            lst = lst.rest
        return result
 
    def __str__(self):
        s = '< '
        lst = self
        while lst != Link.empty:
            if isinstance(lst.first, Link): 
                s += lst.first.__str__() + ' '
            else:
                s += repr(lst.first) + ' '
            lst = lst.rest
        return s + '>'
 
class EmptyList(Link):
    def __init__(self):
        pass
 
Link.empty = EmptyList()
 
# run REPL when script is run
if __name__ == '__main__':
    try:
        import readline
    except ImportError:
        pass
    repl()