<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 {
public:
    typedef variant<int, char> token;

    enum class op {
        add,
        sub,
        mul,
        div
    };

    op char_to_op(char c) {
        switch(c) {
            case '+':
                return op::add;
            case '-':
                return op::sub;
            case '*':
                return op::mul;
            case '/':
                return op::div;
            default:
                assert(false);
        };
    }

    int priority(op t) {
        switch(t) {
            case op::add:
            case op::sub:
                return 0;
            case op::mul:
            case op::div:
                return 1;
        };
    }

    bool compare(op a, op b) {
        return priority(a) < priority(b);
    }

    struct binop;
    typedef variant<int,binop> ast;
    struct binop {
        op op;
        unique_ptr<ast> left;
        unique_ptr<ast> right;
    };

    int eval(ast& ast) {
        if(holds_alternative<int>(ast)) {
            return get<int>(ast);
        } else {
            binop b = get<binop>(std::move(ast));
            int left = eval(*b.left);
            int right = eval(*b.right);
            switch(b.op) {
                case op::add:
                    return left + right;
                case op::sub:
                    return left - right;
                case op::mul:
                    return left * right;
                case op::div:
                    return left / right;
            }
        }
    }

    void print(ast& ast) {
        if(holds_alternative<int>(ast)) {
            cout << get<int>(ast) << " ";
        } else {
            binop& b = get<binop>(ast);
            cout << "(";
            print(*b.left);
            switch(b.op) {
                case op::add:
                    cout << "+ ";
                    break;
                case op::sub:
                    cout << "- ";
                    break;
                case op::mul:
                    cout << "* ";
                    break;
                case op::div:
                    cout << "/ ";
                    break;
            }
            print(*b.right);
            cout << ")";
        }
    }

    optional<ast> after_expr(int& i, const vector<token>& tokens, optional<tuple<op, unique_ptr<ast>>>& on_reserve, ast expr) {
        if(i == tokens.size() || get<char>(tokens[i]) == ')') {
            if(on_reserve.has_value()) {
                auto [ op, left ] = std::move(on_reserve.value());
                return binop(op, std::move(left), make_unique<ast>(std::move(expr)));
            } else {
                return expr;
            }
        } else {
            op new_op = char_to_op(get<char>(tokens[i]));
            if(on_reserve.has_value()) {
                auto [ reserve_op, left ] = std::move(on_reserve.value());
                if(compare(reserve_op, new_op)) {
                    i-=2;
                    return after_expr(i, tokens, on_reserve, parse(i, tokens));
                } else {
                    on_reserve = make_optional(
                        make_tuple(new_op,
                        make_unique<ast>(
                            binop(reserve_op,std::move(left),make_unique<ast>(std::move(expr))))));
                }
            } else {
                on_reserve = make_optional(make_tuple(new_op, make_unique<ast>(std::move(expr))));
            }
            return nullopt;
        }
    }

    ast parse(int& i, const vector<token>& tokens) {
        // 1 + 2 + 3 * 2 / 3 + 1
        
        // ((1 + 2) + 3)
        // (((1 + 2) + ((3 * 2) / 3))) + 1)        

        // eat number, eat op, parse(rest)
        // (1 + (2 + (3 + 4)))
        // loop eat number, eat op, eat number
        // ((1 + 2) + ((3 * 2) / 3) + 1)

        // check if next thing is number+binop, if it's a higher precedence binop than previous, recurse on number+binop

        // unary minus for first thing 
        // maybe parse unary minus as 0 - ...

        optional<tuple<op, unique_ptr<ast>>> on_reserve;
        if(holds_alternative<char>(tokens[i])) {
            char c = get<char>(tokens[i]);
            if(c == '-') {
                on_reserve = make_optional(make_tuple(op::sub, make_unique<ast>(0)));
                ++i;
            } else if(c == '(') {}
            else {
                assert(false);
            }
        }        
        for(; i < tokens.size(); ++i) {
            ast v;
            if(holds_alternative<char>(tokens[i])) {
                char c = get<char>(tokens[i]);
                assert(c == '(');
                ++i;
                v = parse(i, tokens);
            } else {
                v = get<int>(tokens[i]);
            }
            ++i;
            optional<ast> ret = after_expr(i, tokens, on_reserve, std::move(v));
            if(ret.has_value()) {
                return std::move(ret.value());
            }
        }
        assert(false);
    }

    int calculate(string s) {
        vector<token> tokens;
        for(int i = 0; i < s.size();) {
            if(s[i] == ' ') { ++i; continue; }
            if(isdigit(s[i])) {
                int start = i;
                while(i < s.size() && isdigit(s[i])) {
                    ++i;
                }
                int len = i-start;
                int val = stoi(s.substr(start,len));
                tokens.push_back(val);
            } else {
                tokens.push_back(s[i]);
                ++i;
            }
        }
        int i = 0;
        ast tree = parse(i, tokens);
        //print(tree);
        return eval(tree);
    }
};
42181