import random
import itertools
import re
import math

END_OF_STREAM_TOKEN = "\0"

class Node:
    def __init__(self, name, *args):
        self.name = name
        self.args = args
    def __repr__(self):
        params = "()"
        if len(self.args) > 1:
            params = str(tuple(self.args))
        elif len(self.args) == 1:
            params = f"({self.args[0]})"
        return f"{self.name}Node{params}"

def parse_expr(tokens):
    obj = parse_add_or_sub(tokens)
    if tokens[-1] is END_OF_STREAM_TOKEN:
        tokens.pop()
        return obj
    else:
        raise Exception("Expected end of token stream, got {repr(tokens[-1])} instead")

def parse_add_or_sub(tokens):
    left = parse_mul_or_div(tokens)
    if tokens[-1] in "+-":
        op = tokens.pop()
        right = parse_add_or_sub(tokens)
        return Node("BinOp", op, left, right)
    else:
        return left

def parse_mul_or_div(tokens):
    left = parse_atom(tokens)
    if tokens[-1] in "*/":
        op = tokens.pop()
        right = parse_mul_or_div(tokens)
        return Node("BinOp", op, left, right)
    else:
        return left

def parse_atom(tokens):
    if tokens[-1] == "(":
        tokens.pop()
        node = parse_add_or_sub(tokens)
        if tokens.pop() != ")": raise Exception("unexpected token")
        return node
    elif tokens[-1].isdigit():
        return Node("Int", int(tokens.pop()))
    else:
        raise Exception("Don't know how to parse atom with token {repr(tokens[-1])}")

def evaluate(node):
    if node.name == "BinOp":
        op, *args = node.args
        if len(args) == 1:
            return evaluate(args[0])
        else:
            assert len(args) == 2
            l,r = evaluate(args[0]), evaluate(args[1])
            if op == "+": return l+r
            elif op == "-": return l-r
            elif op == "*": return l*r
            elif op == "/": return l/r
            else: raise Exception(f"Don't know how to evaluate operator {repr(op)}")

    elif node.name == "Int":
        return node.args[0]
    else:
        raise Exception(f"Don't know how to convert node with name {node.name}")

def tokenize(s):
    patterns = [
        re.compile(r"\d+"),
        re.compile(r"'[^']*'"),
        re.compile(r"[+*/-]"),
        re.compile(re.escape("(")),
        re.compile(re.escape(")")),
        re.compile(r"\s")
    ]

    ignored = re.compile(r"\s")

    tokens = []
    i = 0
    while i < len(s):
        for pattern in patterns:
            m = pattern.match(s[i:])
            if m:
                token = m.group()
                i += len(token)
                if not ignored.match(token):
                    tokens.append(token)
                break
        else:
            raise Exception(f"No token pattern found for string {repr(s[i:])}")
    tokens.append(END_OF_STREAM_TOKEN)
    tokens.reverse()
    return tokens

s = "(2 + 2) * (2 + 2) / 23  - 42"
tokens = tokenize(s)

ast = parse_expr(tokens)
assert len(tokens) == 0, f"tokens remaining after parsing: {tokens}"
print(s)
#(2 + 2) * (2 + 2) / 23  - 42

print(ast)
# BinOpNode(
    # '-',
    # BinOpNode(
        # '*',
        # BinOpNode(
            # '+',
            # IntNode(2),
            # IntNode(2)
        # ),
        # BinOpNode(
            # '/',
            # BinOpNode(
                # '+',
                # IntNode(2),
                # IntNode(2)
            # ),
            # IntNode(23)
        # )
    # ),
    # IntNode(42)
# )

print(evaluate(ast))

#-41.30434782608695