Difference between revisions of "Calculator/Source code"

From CS 61A Wiki
Jump to: navigation, search
[checked revision][checked revision]
(created)
 
(use OOP version)
 
Line 16: Line 16:
 
     """Read an expression from a sequence of tokens.
 
     """Read an expression from a sequence of tokens.
 
     >>> exp = read(['(', '+', '2', '3', '6', ')'])
 
     >>> exp = read(['(', '+', '2', '3', '6', ')'])
     >>> print_linked_list(exp)
+
     >>> print(exp)
 
     < '+' 2 3 6 >
 
     < '+' 2 3 6 >
 
     >>> exp = read(['(','*','4','(','-','12','8',')',')','3','2'])
 
     >>> exp = read(['(','*','4','(','-','12','8',')',')','3','2'])
     >>> print_linked_list(exp)
+
     >>> print(exp)
 
     < '*' 4 < '-' 12 8 > >
 
     < '*' 4 < '-' 12 8 > >
 
     """
 
     """
Line 38: Line 38:
 
     elif tokens[0] == ')':
 
     elif tokens[0] == ')':
 
         tokens.pop(0) # pop off ')'
 
         tokens.pop(0) # pop off ')'
         return empty
+
         return Link.empty
 
     else:
 
     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
+
         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):
 
def atom(token):
Line 57: Line 57:
 
     if type(exp) in (int, float): # numbers
 
     if type(exp) in (int, float): # numbers
 
         return exp
 
         return exp
     else: # call expression
+
     elif isinstance(exp, Link): # call expression
         args = to_list(map_linked_list(calc_eval, rest(exp))) # evaluate each argument and collect them in a list
+
         args = exp.rest.map(calc_eval).to_list() # evaluate each argument and collect them in a list
         return calc_apply(first(exp), args) # apply the operator
+
         return calc_apply(exp.first, args) # apply the operator
 +
    else:
 +
        raise SyntaxError('unknown expression')
 
          
 
          
 
def calc_apply(operator, args):
 
def calc_apply(operator, args):
Line 82: Line 84:
 
         try:
 
         try:
 
             print(calc_eval(parse(input('calc> '))))
 
             print(calc_eval(parse(input('calc> '))))
         except SyntaxError as e:
+
         except (SyntaxError, ZeroDivisionError) as e:
             print(e)
+
             print(type(e).__name__ + ':', e)
  
"""Linked list functions"""
+
"""Linked list class"""
empty = lambda: 42
+
class Link:
 +
    def __init__(self, elem, lst):
 +
        self.first = elem
 +
        self.rest = lst
  
def link(element, lst):
+
    def map(self, f):
    return element, lst
+
        if self != Link.empty:
 +
            self.first = f(self.first)
 +
            self.rest.map(f)
 +
        return self
  
def first(lst):
+
    def to_list(self):
    return lst[0]
+
        result = []
 +
        lst = self
 +
        while lst != Link.empty:
 +
            result.append(lst.first)
 +
            lst = lst.rest
 +
        return result
  
def rest(lst):
+
    def __str__(self):
    return lst[1]
+
        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 + '>'
  
def linked_list_to_str(lst):
+
class EmptyList(Link):
     s = '< '
+
     def __init__(self):
    while lst != empty:
+
         pass
        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):
+
Link.empty = EmptyList()
    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
 
# run REPL when script is run
 
if __name__ == '__main__':
 
if __name__ == '__main__':
 +
    try:
 +
        import readline
 +
    except ImportError:
 +
        pass
 
     repl()
 
     repl()
 
</syntaxhighlight>
 
</syntaxhighlight>

Latest revision as of 10:08, 21 July 2014

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()