creativcoder · August 29, 2015 14:27 · Aug 26, 2013
diff --git a/calc.py b/calc.py
@@ -0,0 +1,243 @@
+#this program uses the Shunting Yard algorithm to transform infix expressions
+# into postfix, and then an AST, which can then be easily evaluated.
+#just run `python calc.py` and enjoy. enjoyment is optional and not included
+# with the standard calc.py package, but for an extra $99.99 we can have a
+# calc.py Premium Deluxe sent to you over the next 6-8 weeks, which may or may
+# not increase your enjoyment of our calc.py product.
+#for a list of operators supported and not supported (for isntance, the unary -
+# is a ~) look below.
+#TODO: handle parentheses.
+
+from __future__ import print_function
+
+#operator table: operator => { precedence, associativity=left, arity=2, calc }
+
+#but first, a note from our sponsor, the infamous factorial (yes, I know it can
+# be optimised to great extents)
+def factorial (n):
+    if n < 2:
+        return 1
+    return n * factorial(n-1)
+
+operators = {
+    # addition
+    '+' : {
+        'prec' : 1,
+        'calc' : lambda a,b: a + b },
+    # subtraction
+    '-' : {
+        'prec' : 1,
+        'calc' : lambda a,b: a - b },
+    # multiplication
+    '*' : {
+        'prec' : 2,
+        'calc' : lambda a,b: a * b },
+    # division
+    '/' : {
+        'prec' : 2,
+        'calc' : lambda a,b: a / b },
+    # exponentiation
+    '^' : {
+        'prec' : 3,
+        'assoc' : 'right',
+        'calc' : lambda a,b: a ** b },
+    # negation
+    '~' : {
+        'prec' : 6,
+        'assoc' : 'right',
+        'arity' : 1,
+        'calc' : lambda a: -a },
+    # modulus
+    '%' : {
+        'prec' : 4,
+        'calc' : lambda a,b: a % b },
+    # factorial
+    '!' : {
+        'prec' : 4,
+        'assoc' : 'right',
+        'arity' : 1,
+        'calc' : lambda a: factorial(a) },
+    # average
+    '@' : {
+        'prec' : 5,
+        'calc' : lambda a,b: (a + b) / 2 },
+    # max
+    '$' : {
+        'prec' : 5,
+        'calc' : lambda a,b: max(a,b) },
+    # min
+    '&' : {
+        'prec' : 5,
+        'calc' : lambda a,b: min(a,b) } }
+
+for key in operators:
+    operators[key]['symbol'] = key
+
+class Calculator:
+    def __init__ (self):
+        self.operators = operators
+
+    def calc (self, inp):
+        self.parse(inp)
+        self.ast = self.to_ast()
+        return self.ast.calc() if self.ast is not None else None
+
+    def parse (self, inp):
+        tokens = list(inp.replace(' ', ''))
+        self.opstack = []
+        self.out = []
+
+        while tokens:
+            self.parse_token(tokens.pop(0))
+
+        while self.opstack:
+            self.out.append(self.opstack.pop())
+            #check for mismatched parens
+
+        #awesome, we jut finished converting into postfix
+
+    def to_ast (self):
+        if not self.out:
+            return None
+
+        #we go from the right. on each operator, we grab `arity` tokens ahead
+        # and add them as the op's children
+        stack = self.out[::]
+        root = self.build_ast(stack.pop(), stack)
+        return root
+
+    def build_ast (self, tok, stack):
+        if not stack:
+            return tok
+
+        for i in xrange(0, tok.arity):
+            if not stack:
+                msg = 'Improper expression: {0} expected {1} operands, but only got {2}'.format(tok.symbol, tok.arity, i)
+                raise SyntaxError(msg)
+
+
+            child = stack.pop()
+            print('popped token %s' % (child))
+
+            #recurse if we're on an operator
+            if isinstance(child, OperatorToken):
+                self.build_ast(child, stack)
+            tok.add_child(child)
+
+        return tok
+
+
+    def parse_token (self, tok):
+        if is_number(tok):
+            self.out.append(NumberToken(tok))
+        elif self.operators.has_key(tok):
+            actual_tok = OperatorToken(self.operators[tok])
+            self.parse_op(actual_tok)
+        #add parentheses handling
+        else:
+            raise SyntaxError('Unrecognized token ' + str(tok));
+
+    def parse_op (self, tok):
+        #an operator `left` is weaker than (should be placed after) `right` if
+        # it's left-associative and they have equal precedence, or if `left`
+        # just has lower precedence than `right`
+        def weaker (left, right):
+            if left.assoc == 'left' and left.prec == right.prec:
+                return True
+            return left.prec < right.prec
+
+        while self.opstack and weaker(tok, self.opstack[-1]):
+            self.out.append(self.opstack.pop())
+
+        self.opstack.append(tok)
+
+
+class Token:
+    pass
+
+class OperatorToken(Token):
+    prec = 1
+    assoc = 'left'
+    arity = 2
+    cb = lambda a,b: None
+
+    def __init__ (self, op):
+        self.children = []
+
+        self.symbol = op['symbol']
+        self.prec   = op['prec']
+        self.assoc  = op['assoc'] if op.has_key('assoc') else 'left'
+        self.arity  = op['arity'] if op.has_key('arity') else 2
+        self.cb     = op['calc']
+
+    def calc (self):
+        args = [child.calc() for child in self.children]
+        print('args to ', self.symbol, ' '.join([str(x) for x in args]))
+        return self.cb(*args)
+
+
+    def add_child (self, child):
+        print('Adding child %s to %s' % (child, self))
+        self.children.insert(0, child)
+
+    def add_children (self, *children):
+        for child in children:
+            self.add_child(child)
+
+    def humane_str (self):
+        if self.arity == 1 and self.assoc == 'right':
+            return self.symbol + str(self.children[0])
+        elif self.arity == 2:
+            return ' '.join(
+                [self.children[0].humane_str(),
+                 self.symbol,
+                 self.children[1].humane_str()])
+
+        strung_children = [str(x) for x in self.children]
+        return '{0} => [{1}]'.format(self.symbol, ', '.join(strung_children))
+
+    def __str__ (self):
+        return self.symbol
+
+
+class NumberToken(Token):
+    def __init__ (self, val):
+        self.value = float(val) if '.' in str(val) else int(val)
+
+    def calc (self):
+        return self.value
+
+    def humane_str (self):
+        return str(self)
+
+    def __str__ (self):
+        return str(self.value)
+
+def is_number (string):
+    try:
+        float(string)
+        return True
+    except ValueError:
+        return False
+
+if __name__ == '__main__':
+    calc = Calculator()
+
+    while True:
+        try:
+            inp = raw_input('> ')
+        except EOFError:
+            inp = ''
+        if not inp:
+            print('Goodbye!')
+            break
+
+        res = None
+        try:
+            res = calc.calc(inp)
+        except SyntaxError as ex:
+            print('Syntax error: {0}'.format(str(ex)))
+        else:
+            if res is not None:
+                print(calc.ast.humane_str(), end=' = ')
+            print(res)
No results found