<p>Given a string <code>s</code> which represents an expression, <em>evaluate this expression and return its value</em>.&nbsp;</p>

<p>The integer division should truncate toward zero.</p>

<p>You may assume that the given expression is always valid. All intermediate results will be in the range of <code>[-2<sup>31</sup>, 2<sup>31</sup> - 1]</code>.</p>

<p><strong>Note:</strong> You are not 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 = "3+2*2"
<strong>Output:</strong> 7
</pre><p><strong class="example">Example 2:</strong></p>
<pre><strong>Input:</strong> s = " 3/2 "
<strong>Output:</strong> 1
</pre><p><strong class="example">Example 3:</strong></p>
<pre><strong>Input:</strong> s = " 3+5 / 2 "
<strong>Output:</strong> 5
</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 integers and operators <code>(&#39;+&#39;, &#39;-&#39;, &#39;*&#39;, &#39;/&#39;)</code> separated by some number of spaces.</li>
	<li><code>s</code> represents <strong>a valid expression</strong>.</li>
	<li>All the integers in the expression are non-negative integers in the range <code>[0, 2<sup>31</sup> - 1]</code>.</li>
	<li>The answer is <strong>guaranteed</strong> to fit in a <strong>32-bit integer</strong>.</li>
</ul>

class Expression {
public:
    virtual ~Expression() {};
    virtual long long Operate(long long left = 0, long long right = 0) {
        return 0;
    };
    virtual bool IsBinaryOperator() {
        return false;
    };
    virtual char Name() {
        return ' ';
    };
};

class Number : public Expression {
public:    
    Number(long long num) : num(num) {
    }

    ~Number() override {
    }

    bool IsBinaryOperator() override {
        return false;
    }

    long long Operate(long long left = 0, long long right = 0) override {
        return num;
    }

    char Name() override {
        return '_';
    }
private:
    long long num;
};

class Operand : public Expression {
public:
    Operand(char operation) : operation(operation) {
    }

    ~Operand()  override  {
    };

    bool IsBinaryOperator() override {
        return true;
    }

    long long Operate(long long left = 0, long long right = 0) override {
        switch (operation)
        {
        case '-':
            return left - right;
            break;
        case '+':
            return left + right;
            break;
        case '*':
            return left * right;
            break;
        case '/':
            return left / right;
            break;
        default:
            return 0;
            break;
        }
    }

    char Name() override {
        return operation;
    }
private:
    char operation;
};


class Solution {
public:
    
    int calculate(string s) {
        int idx = 0;
        int n = s.size();

        std::vector<Expression*> vec;

        while (idx < n) {
            if (s[idx] == ' ') {
                ++idx;
                continue;
            }
            if (!isdigit(s[idx])) {
                vec.push_back(new Operand(s[idx]));
                ++idx;
                continue;
            }

            long long curr = 0;
            while (idx < n && isdigit(s[idx])) {
                curr = curr * 10 + (s[idx] - '0');
                ++idx;
            }

            if (!vec.empty() && vec.back()->IsBinaryOperator() && (vec.back()->Name() == '*' || vec.back()->Name() == '/')) {
                int size = vec.size() - 1;
                curr = vec.back()->Operate(vec[size - 1]->Operate(), curr);
                vec.pop_back();
                vec.pop_back();
            }

            vec.push_back(new Number(curr));
        }

        long long res = vec[0]->Operate();
        for (int i = 1; i < vec.size(); i += 2) {
            res = vec[i]->Operate(res, vec[i + 1]->Operate());
        }
        return res;
    }
};
37714