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

typedef struct {
    int value;
    char symbol;
} Item;

class Solution {
public:
    int calculate(string s) {
        vector<Item> stack;
        int i = 0;
        while (i < s.size()) {
            if (s[i] == '+' || s[i] == '-' || s[i] == '*' || s[i] == '/') {
                stack.push_back(Item{.symbol=s[i]});
                i ++;
                continue;
            }
            if (s[i] == ' ') {
                i += 1;
                continue;
            }
            int j = i;
            long v = 0;
            while ( j < s.size() && s[j] >= '0' && s[j] <= '9') {
                v = v * 10 + s[j] - '0';
                j++;
            }
            i = j;
            Item item;
            item.value = v;
            stack.push_back(item);
        }

        deque<Item> q;
        i = 0;
        while (i < stack.size()) {
            Item item = stack[i];
            if (item.symbol == '*' || item.symbol == '/') {
                Item pre = stack[i-1];
                Item next = stack[i+1];
                int v1 = q.back().value;
                int v2 = next.value;
                int res;
                if (item.symbol == '*') res = v1 * v2;
                else res = v1 / v2;
                Item n;
                n.value = res;
                q.pop_back();
                q.push_back(n);
                // cout <<"push abck q: " << n.value;
                i = i + 2;
            } else {
                q.push_back(item);
                i ++;
            }
        }
        int ans = 0;
        while (!q.empty()) {
            Item item = q.front();
            // cout <<"item: " << item.symbol << "; " << item.value << endl;
            q.pop_front();
            if (item.symbol == '+') {
                Item next = q.front();
                // cout <<"next: " << next.symbol << "; " << next.value << endl;
                q.pop_front();
                ans = ans + next.value;
            }
            else if (item.symbol == '-') {
                Item next = q.front();
                q.pop_front();
                ans = ans - next.value;
            } else {
                ans = item.value;
            }
        }
        return ans;
    }
};
27370