"""
 parse_tree.py

 An example of a parsing (with recursive descent) and recursively evaluating
 a simple algebraic parse tree.

 The context free grammar for this tiny calculator language is (using BNF) :

   expression :== number | "(" expression operator expression ")"
   operator   :== "+" | "*"
   number     :== "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"

 See
   * https://en.wikipedia.org/wiki/Backus-Naur_form
   * https://en.wikipedia.org/wiki/Parse_tree
   * https://runestone.academy/ns/books/published/pythonds/Trees/ParseTree.html


 $ python parse_tree.py
 text is (1+0)
 tree is <Node op=+ left=1 right=0>
 value is 1

 text is ((1+2)*(3+4))
 tree is <Node op=* left=<Node op=+ left=1 right=2> right=<Node op=+ left=3 right=4>>
 value is 21

 text is (((1+2)*(3+4))*(8+9))
 tree is <Node op=* left=<Node op=* left=<Node op=+ left=1 right=2>
                    right=<Node op=+ left=3 right=4>> right=<Node op=+ left=8 right=9>>
 value is 357

Jim Mahoney | cs.bennington.college | April 2022 | MIT License
"""

class Node:
    def __init__(self, left, operator, right):
        self.left = left
        self.op = operator
        self.right = right
    def __str__(self):
        return f"<Node op={str(self.op)} left={str(self.left)} right={str(self.right)}>"

def expression(text, index):
    #print(f" in expression(text='{text}', index={index})")
    if text[index] == '(':
        (left, index) = expression(text, index+1)
        #print(f"  left={left}, index={index}")
        operator = text[index]
        #print(f"  op={operator}")
        (right, index) = expression(text, index+1)
        #print(f"  left={left}, index={index}")        
        if text[index] != ')': raise Exception("OOPS - expected ')'")
        return (Node(left, operator, right), index+1)
    if text[index] in ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']:
        return (int(text[index]), index+1)
    raise Exception(f"OOPs - unexpected input '{text[index]}'")

def eval(node):
    """ evaluate a tree, i.e. convert a node to its algebraic value """
    if type(node) == type(0):  # number?
        return node
    elif node.op == '+':
        return eval(node.left) + eval(node.right)
    elif node.op == '*':
        return eval(node.left) * eval(node.right)
    else:
        Exception(f"Oops - unexpected node in eval")

def main():
    for text in ("(1+0)",
                 "((1+2)*(3+4))",
                 "(((1+2)*(3+4))*(8+9))"):
    
        (tree, index) = expression(text, 0)
        print(f"text is {text}")
        print(f"tree is {tree}")
        print(f"value is {eval(tree)}")
        print()
        
main()