<p>Given a string <code>s</code> representing a valid expression, implement a basic calculator to evaluate it, and return <em>the result of the evaluation</em>.</p>

<p><strong>Note:</strong> You are <strong>not</strong> allowed to use any built-in function which evaluates strings as mathematical expressions, such as <code>eval()</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;1 + 1&quot;
<strong>Output:</strong> 2
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> s = &quot; 2-1 + 2 &quot;
<strong>Output:</strong> 3
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;(1+(4+5+2)-3)+(6+8)&quot;
<strong>Output:</strong> 23
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= s.length &lt;= 3 * 10<sup>5</sup></code></li>
	<li><code>s</code> consists of digits, <code>&#39;+&#39;</code>, <code>&#39;-&#39;</code>, <code>&#39;(&#39;</code>, <code>&#39;)&#39;</code>, and <code>&#39; &#39;</code>.</li>
	<li><code>s</code> represents a valid expression.</li>
	<li><code>&#39;+&#39;</code> is <strong>not</strong> used as a unary operation (i.e., <code>&quot;+1&quot;</code> and <code>&quot;+(2 + 3)&quot;</code> is invalid).</li>
	<li><code>&#39;-&#39;</code> could be used as a unary operation (i.e., <code>&quot;-1&quot;</code> and <code>&quot;-(2 + 3)&quot;</code> is valid).</li>
	<li>There will be no two consecutive operators in the input.</li>
	<li>Every number and running calculation will fit in a signed 32-bit integer.</li>
</ul>

from typing import Optional


class Number:
    def __init__(self, value):
        self.value = value

    def __repr__(self) -> str:
        return f"N[{self.value}]"

class Operator:
    def __init__(self, operator):
        self.operator = operator

    def __repr__(self) -> str:
        return f"O[{self.operator}]"

class Parenthesis:
    def __init__(self, parenthesis):
        self.parenthesis = parenthesis

    def __repr__(self) -> str:
        return f"P[{self.parenthesis}]"


class Node:
    def __init__(self, operator: Optional[Operator] = None):
        self.operator = operator
        self.operands = []

    def calculate(self):
        if self.operator is None:
            a = self.operands[0]
            return a.calculate() if isinstance(a, Node) else a
        if self.operator.operator == '+':
            a = self.operands[0]
            b = self.operands[1]
            aval = a.calculate() if isinstance(a, Node) else a
            bval = b.calculate() if isinstance(b, Node) else b
            return Number(aval.value + bval.value)
        if self.operator.operator == '-':
            a = self.operands[0]
            aval = a.calculate() if isinstance(a, Node) else a
            if len(self.operands) == 1:
                return Number(-aval.value)
            b = self.operands[1]
            bval = b.calculate() if isinstance(b, Node) else b
            return Number(aval.value - bval.value)
        return None

    def __repr__(self):
        return f"Node[{self.operator} {self.operands}]"


def buildAST(tokens, pos, left_operand=None):
    node = Node()
    if left_operand:
        node.operands.append(left_operand)
    if pos >= len(tokens):
        return node, pos
    token = tokens[pos]
    pos += 1
    if isinstance(token, Parenthesis) and token.parenthesis == ')':
        return left_operand, pos
    if isinstance(token, Parenthesis) and token.parenthesis == '(':
        operand, pos = buildAST(tokens, pos)
        node.operands.append(operand)
    elif isinstance(token, Number):
        node.operands.append(token)
    elif isinstance(token, Operator):
        node.operator = token

    if pos >= len(tokens):
        return node, pos

    if node.operator is None and isinstance(tokens[pos], Operator):
        node.operator = tokens[pos]
        pos += 1

    token = tokens[pos]
    pos += 1

    if isinstance(token, Parenthesis) and token.parenthesis == ')':
        return node, pos
    if isinstance(token, Parenthesis) and token.parenthesis == '(':
        operand, pos = buildAST(tokens, pos)
        node.operands.append(operand)
    elif isinstance(token, Number):
        node.operands.append(token)

    if pos < len(tokens):
        return buildAST(tokens, pos, node)

    return node, pos


def parse_tokens(expr: str):
    number = None
    tokens = []

    for c in expr:
        if c == ' ':
            continue
        if ord(c) >= ord('0') and ord(c) <= ord('9'):
            number = number * 10 + int(c) if number is not None else int(c)
            continue
        if number is not None:
            tokens.append(Number(number))
            number = None
        if c in ('(', ')'):
            tokens.append(Parenthesis(c))
            continue
        if c in ('+', '-'):
            tokens.append(Operator(c))
            continue
    if number is not None:
        tokens.append(Number(number))

    return tokens


class Solution:
    def calculate(self, s: str) -> int:
        tokens = parse_tokens(s)
        node, _ = buildAST(tokens, 0)
        return node.calculate().value
        
47265