Mercurial > lbo > hg > arith

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/README.md	Fri May 17 22:28:13 2019 +0200
@@ -0,0 +1,11 @@
+# arith: Toy arithmetic parser in Python
+
+This is not really useful except for playing around with recursive parsers and
+possible applications of computer algebra.
+
+Ideas list:
+
+* Vector calculations
+* Matrix calculations
+* Automatic symbolic differentiation (and integration)
+* Graphing (with matplotlib)
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/arith/eval.py	Fri May 17 22:28:13 2019 +0200
@@ -0,0 +1,56 @@
+#!/usr/bin/env python3
+# -*- coding: utf-8 -*-
+"""
+Created on Fri May 17 21:55:20 2019
+
+@author: lbo
+"""
+
+from tree import Product, Term, Power, Value, Symbol
+
+class NotBoundError(Exception):
+
+    def __init__(self, symbol):
+        super(Exception, self).__init__('Symbol {} not bound!'.format(symbol))
+
+
+class Bindings:
+    _bindings = {}
+
+    def __init__(self, bind={}):
+        self._bindings = bind
+
+    def set(self, sym, val):
+        self._bindings[sym] = val
+
+    def unset(self, sym):
+        self._bindings.pop(sym)
+
+    def get(self, sym):
+        sym = sym.c
+        if sym in self._bindings:
+            return self._bindings[sym]
+        raise NotBoundError(sym)
+
+def evaluate(node, bindings=None):
+    bindings = Bindings() if not bindings else bindings
+    assert isinstance(node, Symbol) or isinstance(node, Value) or (node.left and node.right)
+    if isinstance(node, Symbol):
+        return bindings.get(node)
+    elif isinstance(node, Value):
+        return node.v
+    elif isinstance(node, Product):
+        if node.typ == Product.PROD:
+            return evaluate(node.left, bindings) * evaluate(node.right, bindings)
+        elif node.typ == Product.QUOT:
+            right = evaluate(node.right, bindings)
+            assert right != 0
+            return evaluate(node.left, bindings) / right
+    elif isinstance(node, Term):
+        if node.typ == Term.PLUS:
+            return evaluate(node.left, bindings) + evaluate(node.right, bindings)
+        elif node.typ == Term.MINUS:
+            return evaluate(node.left, bindings) - evaluate(node.right, bindings)
+    elif isinstance(node, Power):
+        if node.typ == Power.POWER:
+            return evaluate(node.left, bindings) ** evaluate(node.right, bindings)
\ No newline at end of file
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/arith/parse.py	Fri May 17 22:28:13 2019 +0200
@@ -0,0 +1,124 @@
+#!/usr/bin/env python3
+# -*- coding: utf-8 -*-
+"""
+Created on Sun May 12 19:23:08 2019
+
+@author: lbo
+"""
+
+"""
+Parse arithmetic terms.
+
+Terms are structured like this:
+
+    Sum (consists of) products (consist of) factors
+"""
+
+from tree import Value, Symbol, Product, Term, Power
+
+class ParseState:
+    """Encapsulates state as the parser goes through input."""
+
+    _input = ''
+    _index = 0
+
+    def __init__(self, s):
+        self._input = s
+
+    def repr(self):
+        return 'ParseState({} < {} > {}'.format(
+                self._input[0:self._index], self._input[self._index], self._input[self._index:])
+
+    def next(self):
+        current = self.peek()
+        self._index += 1
+        while not self.finished() and self.peek().isspace():
+            self._index += 1
+        return current
+
+    def peek(self):
+        return self._input[self._index]
+
+    def index(self):
+        return self._index
+
+    def reset(self, ix):
+        self._index = ix
+
+    def __iter__(self):
+        return self
+
+    def __next__(self):
+        return self.next()
+
+    def finished(self):
+        return self._index == len(self._input)
+
+def parse(s):
+    st = ParseState(s)
+    return parse_term(st)
+
+def parse_term(st):
+    left = parse_product(st)
+    result = left
+    if st.finished():
+        return result
+    op = st.peek()
+    while op in [Term.PLUS, Term.MINUS]:
+        st.next()
+        right = parse_product(st)
+        result = Term(result, right)
+        result.typ = op
+        if st.finished():
+            break
+        op = st.peek()
+    return result
+
+def parse_product(st):
+    left = parse_power(st)
+    result = left
+    if st.finished():
+        return result
+    op = st.peek()
+    while not st.finished() and op in [Product.PROD, Product.QUOT]:
+        st.next()
+        right = parse_product(st)
+        result = Product(result, right)
+        result.typ = op
+        if st.finished():
+            break
+        op = st.peek()
+    return result
+
+def parse_power(st):
+    left = parse_atom(st)
+    result = left
+    if st.finished():
+        return result
+    next = st.peek()
+    if next == '^':
+        st.next()
+        right = parse_atom(st)
+        result = Power(left, right)
+    return result
+
+
+def parse_atom(st):
+    next = st.next()
+    if next == '(':
+        term = parse_term(st)
+        st.next() # Consume closing paren
+        return term
+
+    full = next
+
+    def is_number(s):
+        return all([a.isnumeric() or a == '.' for a in s])
+
+    while not st.finished() and (st.peek().isalpha() or is_number(st.peek())):
+        full += st.next()
+
+    if is_number(full):
+        return Value(float(full))
+    if full.isalnum():
+        return Symbol(full)
\ No newline at end of file
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/arith/tree.py	Fri May 17 22:28:13 2019 +0200
@@ -0,0 +1,83 @@
+#!/usr/bin/env python3
+# -*- coding: utf-8 -*-
+"""
+Created on Fri May 17 21:53:30 2019
+
+@author: lbo
+"""
+
+class Node:
+    left = None
+    right = None
+    typ = ''
+
+    def __init__(self, left=None, right=None):
+        self.left = left
+        self.right = right
+
+    def traverse(self):
+        if not self:
+            return ''
+        return (self.left.traverse() + ' ' if self.left else '') + self.repr() + (' ' + self.right.traverse() if self.right else '')
+
+    def __repr__(self):
+        return self.repr()
+
+class Symbol(Node):
+    SYMBOL = '<symbol>'
+    typ = SYMBOL
+
+    c = ''
+
+    def __init__(self, sym):
+        self.c = sym
+
+    def repr(self):
+        return self.c
+
+class Value(Node):
+    VALUE = '<value>'
+    typ = VALUE
+
+    v = None
+
+    def __init__(self, v):
+        self.v = v
+
+    def repr(self):
+        return str(self.v)
+
+class Term(Node):
+    MINUS = '-'
+    PLUS = '+'
+
+    typ = PLUS
+
+    def __init__(self, *args):
+        Node.__init__(self, *args)
+
+    def repr(self):
+        return '(' + self.left.repr() + self.typ + self.right.repr() + ')'
+
+class Product(Node):
+    PROD = '*'
+    QUOT = '/'
+
+    typ = PROD
+
+    def __init__(self, *args):
+        Node.__init__(self, *args)
+
+    def repr(self):
+        return '(' + self.left.repr() + self.typ + self.right.repr() + ')'
+
+class Power(Node):
+    POWER = '^'
+
+    typ = POWER
+
+    def __init__(self, *args):
+        Node.__init__(self, *args)
+
+    def repr(self):
+        return '(' + self.left.repr() + '^' + self.right.repr() + ')'
\ No newline at end of file