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

class Solution:
    def calculate(self, s: str) -> int:
        def parseOps(s):
            ops = []
            num = ""
            for i, c in enumerate(s):
                if c.isdigit():
                    num += c
                elif c in ("+", "-", "*", "/", "(", ")"):
                    # isMinus = False
                    # if c == '-':
                    #     for j in range(i-1, -2, -1):
                    #         if j == -1:
                    #             isMinus = True
                    #         elif s[j].isdigit() or s[j] == ")":
                    #             break
                    #         elif s[j] in ("+", "-", "*", "/", "("):
                    #             isMinus = True
                    #     if isMinus:
                    #         num = "-" + num
                    # if not isMinus:
                    if num != "":
                        ops.append(num)
                        num = ""
                    ops.append(c)    
                elif c == " ":
                    if num != "":
                        ops.append(num)
                        num = ""
            if num != "":
                ops.append(num)
            ops_new = []
            
            for i, op in enumerate(ops):
                # print(i, op)
                if op == '-' and (i == 0 or not(ops[i-1].isdigit() or len(ops[i-1]) > 1 or ops[i-1] == ')')):
                    # print("go heer")
                    ops_new.append("0")
                    ops_new.append("-")
                else:
                    ops_new.append(op)

            return ops_new
        def priority(op):
            if op in ("+", '-'):
                return 1
            if op in ("*", '/'):
                return 2
            if op in (")"):
                return 3
            if op in ("("):
                return 0
        def toPreString(s):
            ops = parseOps(s)
            # print(ops)
            numstack = []
            opstack = []
            ops_new = []
            for op in ops:
                # print("\ncurrent op:", op)
                # print("numstack:", numstack)
                # print("opstack:" ,opstack)
                # print("ops_new:", ops_new)
                if op.isdigit() or len(op) > 1:
                    numstack.append(op)
                elif op == "(":
                    opstack.append(op)
                elif op == ")":
                    tmpstack = []
                    while len(opstack)>0 and opstack[-1] != '(':
                        tmpstack.append(opstack.pop())
                        tmpstack.append(numstack.pop())
                    assert opstack.pop() == '('
                    tmpstack.append(numstack.pop())
                    numstack.append(' '.join(tmpstack[::-1]))
                    # ops_new += tmpstack[::-1]
                else:
                    tmpstack = []
                    while len(opstack)>0 and priority(op) < priority(opstack[-1]):
                        tmpstack.append(numstack.pop())
                        tmpstack.append(numstack.pop())
                        tmpstack.append(opstack.pop())
                    if len(tmpstack) > 0:
                        numstack.append(' '.join(tmpstack[::-1]))
                    opstack.append(op)
            
            # print("\nnumstack:", numstack)
            # print("opstack:" ,opstack)
            # print("ops_new:", ops_new)
            if len(opstack) > 0:
                tmpstack = []
                while len(opstack)>0:
                    tmpstack.append(opstack.pop())
                    tmpstack.append(numstack.pop())
                tmpstack.append(numstack.pop())
                numstack.append(' '.join(tmpstack[::-1]))
            ret = numstack.pop()
            assert len(numstack) == len(opstack) == 0, "numstack: %r, opstack: %r" % (numstack, opstack)
            return ret

        def calcPreString(s):
            ops = s.split(' ')
            numstack = []
            opstack = []
            for op in ops:
                if op.isdigit() or len(op) > 1:
                    numstack.append(int(op))
                else:
                    if op == "+":
                        numstack.append(numstack.pop() + numstack.pop())
                    elif op == "-":
                        numstack.append(-numstack.pop() + numstack.pop())
                    elif op == "*":
                        numstack.append(numstack.pop() * numstack.pop())
                    elif op == "/":
                        numstack.append(1/numstack.pop() * numstack.pop())
            return numstack.pop()
        s = toPreString(s)
        return calcPreString(s)
22115