<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 Solution {
public:
    unordered_map<char, int> prec;

    Solution() {
        prec['/'] = 2;
        prec['*'] = 2;
        prec['+'] = 1;
        prec['-'] = 1;
    }

    int calculate(string s) {
        string postfixExp = postfix(s);
        return evaluatePostfix(postfixExp);
    }

private:
    string postfix(string s) {
        stack<char> st;
        string res = "";
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == ' ') continue;  // Skip spaces
            if ('0' <= s[i] && s[i] <= '9') {
                string temp = "";
                while (i < s.size() && '0' <= s[i] && s[i] <= '9') {
                    temp += s[i++];
                }
                res += temp + ' ';  // Add space to separate numbers
                i--;  // Correct the increment
            } else {
                while (!st.empty() && prec[st.top()] >= prec[s[i]]) {
                    res += st.top();
                    res += ' ';  // Add space to separate operators
                    st.pop();
                }
                st.push(s[i]);
            }
        }
        while (!st.empty()) {
            res += st.top();
            res += ' ';  // Add space to separate operators
            st.pop();
        }
        return res;
    }

    int evaluatePostfix(string post) {
        stack<int> st;
        for (int i = 0; i < post.size(); i++) {
            if (post[i] == ' ') continue;  // Skip spaces
            if ('0' <= post[i] && post[i] <= '9') {
                int num = 0;
                while (i < post.size() && '0' <= post[i] && post[i] <= '9') {
                    num = num * 10 + (post[i++] - '0');
                }
                st.push(num);
                i--;  // Correct the increment
            } else {
                int b = st.top(); st.pop();
                int a = st.top(); st.pop();
                switch (post[i]) {
                    case '+': st.push(a + b); break;
                    case '-': st.push(a - b); break;
                    case '*': st.push(a * b); break;
                    case '/': st.push(a / b); break;
                }
            }
        }
        return st.top();
    }
};
18268