<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 dataclasses import dataclass

#            -
#       +
#     +   3    (3)
#   1  2

# 1 + 2 + 3 - (3 - (1 + 8)) + 5 + 9

class TreeNode:
    def __init__(self, val=None, left=None, right=None):
        self.left = left
        self.right = right
        self.val = val

    def empty(self):
        return self.val is None and self.left is None and self.right is None

    def eval(self):

        if self.val is None:
            return self.left.eval()

        if isinstance(self.val, int):
            return self.val

        if self.right is None:
            return self.left.eval()
        else:
            if self.val == '+':
                return self.left.eval() + self.right.eval()
            elif self.val == '-':
                if self.right is None:
                    return -self.left.eval()
                return self.left.eval() - self.right.eval()


#              +
#           1   ()
# 1 + 2 + 3
# Support only single digit integers
# do not support unary - operations
class Solution:
    def calculate(self, s: str) -> int:
        curr_node = TreeNode()
        stack = []
        i = 0
        n = len(s)

        while i < n:
            if s[i] == ')':
                # Finished constructing the subnode.
                sub_node = curr_node
                curr_node = stack.pop()

                if curr_node.left is None:
                    curr_node.left = sub_node
                else:
                    curr_node.right = sub_node
            elif s[i] == '(':
                # ( is only valid if we have a fresh node on top, or a - node with right side empty
                new_node = TreeNode()
                stack.append(curr_node)
                curr_node = new_node
            elif s[i] in '+-':
                if s[i] == '-' and curr_node.empty():
                    curr_node.left = TreeNode(0)
                    curr_node.val = '-'
                else:
                    # in all cases we need to fork the current operation to the left, and figure out the right side later.
                    # Stack cannot be empty as +- for now cannot be used as unary)
                    new_node = TreeNode()
                    new_node.left = curr_node
                    new_node.val = s[i]
                    curr_node = new_node
            elif s[i].isdigit():

                j = 0
                while i + j < len(s) and s[i + j].isdigit():
                    j += 1

                # on a number either fill in the value for the current node
                # or if the node is an open node of state
                #            root
                #       LEFT  {{EMTPY}}
                # fill in the number directly to the right side.
                curr_val = int(s[i:i + j])

                if curr_node.val is not None:
                    assert curr_node.right is None
                    new_node = TreeNode()
                    new_node.val = curr_val
                    curr_node.right = new_node
                else:
                    assert curr_node.left is None
                    curr_node.val = curr_val

                i += j - 1

            i += 1

        return curr_node.eval()



37834