<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>

INF = float('inf')
EPS = 1e-6
DUMMY = '?'

class Node:
    def __init__(self, val=0, op='', pri=0):
        self.val = val
        self.op = op
        self.pri = pri
        self.left = None
        self.right = None
    def __repr__(self,):
        lstr = f"\nL{self.left}" if self.left else ""
        rstr = f"\nR{self.right}" if self.right else ""
        return f"{self.val},{self.op},{self.pri}{lstr}{rstr}"

class Solution:
    def calculate(self, s: str) -> int:
        c2pri = {"+":1,"-":1, DUMMY:-INF}
        s = s.strip()
        if s[0] == '-': # ex. '-1'
            s = "0"+s
        stack = [] # monotomic inc
        num = 0
        base_pri = 0
        for i in range(len(s)):
            c = s[i]
            
            if c.isdigit():
                num = num*10+int(c)  # don't continue !
            if i == len(s)-1:  # careful !!!
                c = DUMMY  # use dummy to clear stack!
            if c.isdigit():
                continue
            if c==" ":
                continue
            elif c == '(':
                base_pri += 10
            elif c == ')':
                base_pri -= 10
            else:  # + - ? ; // [prev, nd, op]
                nd = Node(val=num, pri=INF)
                num = 0
                stack.append(nd) # mono inc stack !
                op = Node(op=c, pri = base_pri+c2pri[c]-i*EPS)
                # min-tree: max of left-smaller and right-smaller is parent
                while stack and stack[-1].pri >= op.pri:
                    prev = stack.pop() # [-1, prev, op]
                    if stack:
                        if stack[-1].pri >= op.pri:
                             # don't link to op, keep backwards! op could be dummy
                            stack[-1].right = prev
                        else:
                            op.left = prev
                    else:
                        op.left = prev
                stack.append(op)
        root = stack[-1].left
        return self.post(root)
    
    def post(self,node):
        if node.left is None and node.right is None:
            return node.val
        l = self.post(node.left)
        r = self.post(node.right)
        if node.op == "+":
            return l+r
        elif node.op == "-":
            return l-r

"""
https://leetcode.com/problems/basic-calculator/solutions/1456850/python-basic-calculator-i-ii-iii-easy-solution-detailed-explanation/
"""

41606