<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 enum import Enum


class Token:
    class TokenType(Enum):
        NUM = 0
        LEFT_PAR = 1
        RIGHT_PAR = 2
        NEG = 3
        PLUS = 4

    def __init__(self, token_type, val):
        self.token_type = token_type
        self.val = val

    def __repr__(self):
        # return "[{}:{}]".format(self.token_type.name, str(self.val))
        return str(self.val)

class Solution:
    def genToken(self, s) -> List[Token]:
        tokens =  []

        i = 0
        while i < len(s):
            c = s[i]
            if c == '(':
                tokens.append(Token(Token.TokenType.LEFT_PAR, c))
                i += 1
            elif c == ')':
                tokens.append(Token(Token.TokenType.RIGHT_PAR, c))
                i += 1
            elif c == '-':
                if len(tokens) == 0 or tokens[-1].token_type == Token.TokenType.LEFT_PAR:
                    tokens.append(Token(Token.TokenType.NUM, 0))

                tokens.append(Token(Token.TokenType.NEG, c))
                i += 1
            elif c == ' ':
                i += 1
                pass
            elif c.isdigit():
                end_i = i+1
                while end_i < len(s) and s[end_i].isdigit():
                    end_i += 1
                val = int(s[i : end_i])
                i = end_i
                tokens.append(Token(Token.TokenType.NUM, val))
            elif c == '+':
                tokens.append(Token(Token.TokenType.PLUS, c))
                i += 1
            else:
                print("Unknown char: ", c)
                i += 1

        return tokens
    
    def toPostPrefix(self, tokens):
        pass
        queue = []
        stack = []

        for token in tokens:
            if token.token_type == Token.TokenType.NUM:
                queue.append(token)
            elif token.token_type == Token.TokenType.LEFT_PAR:
                stack.append(token)
            elif token.token_type == Token.TokenType.RIGHT_PAR:
                while stack[-1].token_type != Token.TokenType.LEFT_PAR:
                    queue.append(stack.pop())

                # Pop "("
                stack.pop()
            elif token.token_type in [Token.TokenType.NEG, Token.TokenType.PLUS]:
                if stack and (stack[-1].token_type in [Token.TokenType.NEG, Token.TokenType.PLUS] ):
                    queue.append(stack.pop())
                stack.append(token)

        while stack:
            queue.append(stack.pop())

        return queue

    def evalPost(self, tokens):
        stack = []

        for token in tokens:
            if token.token_type == Token.TokenType.NUM:
                stack.append(token.val)
            elif token.token_type in [Token.TokenType.NEG, Token.TokenType.PLUS]:
                
                right = stack.pop()
                left = stack.pop()
                val = 0
                if token.token_type == Token.TokenType.NEG:
                    val = left - right
                else:
                    val = left + right
                stack.append(val)
            else:
                print("Unknown token in evalPost", token)

        return stack[-1]
            


    def calculate(self, s: str) -> int:
        tokens = self.genToken(s)
        # print(tokens)

        tokens = self.toPostPrefix(tokens)
        # print(tokens)
        
        num = 0
        num = self.evalPost(tokens)
        

        return num
37205