难度medium
给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。

整数除法仅保留整数部分。

示例 1：

输入：s = "3+2*2"
输出：7
示例 2：

输入：s = " 3/2 "
输出：1
示例 3：

输入：s = " 3+5 / 2 "
输出：5

提示：

1 <= s.length <= 3 * 105
s 由整数和算符 ('+', '-', '*', '/') 组成，中间由一些空格隔开
s 表示一个 有效表达式
表达式中的所有整数都是非负整数，且在范围 [0, 231 - 1] 内
题目数据保证答案是一个 32-bit 整数

解题思路：
我们采取的措施是使用一个栈保存遍历至今的数字，用一个char型变量op来保留上一个遍历到的运算符，并初始化为'+'，如果该数字之前的符号是加或减，那么把当前数字压入栈中，注意如果是减号，则加入当前数字的相反数，因为减法相当于加上一个相反数。如果之前的符号op是乘或除，那么从栈顶取出一个数字和当前数字进行乘或除的运算，再把结果压入栈中，需要注意的一点是，我们是根据遍历到的字符为运算符来决定进行运算和入栈操作的，可以看看代码，入栈的操作都发生在当前遍历符号为运算符时，而不是数字时，因此有一个需要注意的地方，就是当字符串已经遍历完的时候，后面没有再多的运算符来提示我们这一步应该进行入栈操作了，因此在遍历到字符串最后一个字符的时候，也要进行运算符类型的判别并进行入栈操作。完成遍历后，所有的乘或除都运算完了，再把栈中所有的数字都加起来就是最终结果了。

代码 t69 s100 java

class Solution {
    public int calculate(String s) {
        Stack<Integer> st = new Stack<>();
        int res = 0, num = 0, len = s.length();
        char op = '+';
        for(int i=0; i<len; i++){
            if(s.charAt(i)>='0'){
                num = num * 10 + (s.charAt(i) - '0');
            }
            if((s.charAt(i)<'0' && s.charAt(i)!=' ') || i==len-1){
                if(op=='+') st.push(num);
                if(op=='-') st.push(-num);
                if(op=='*' || op=='/'){
                    int t = op=='*' ? num * st.peek() : st.peek()/num;
                    st.pop();
                    st.push(t);
                }
                op = s.charAt(i);
                num = 0;
            }
        }
        while(!st.isEmpty()){
            res += st.pop();
        }
        return res;
    }
}

代码 t75 s62 cpp

class Solution {
public:
    int calculate(string s) {
        stack<int> st;
        long res = 0, n = s.size(), num = 0;
        char op = '+';
        for(int i=0; i<n; i++){
            if(s[i]>='0'){
                num = num * 10 + s[i] - '0';
            }
            if((s[i]<'0' && s[i]!=' ') || i==n-1){
                if(op=='+') st.push(num);
                if(op=='-') st.push(-num);
                if(op=='*' || op=='/'){
                    int t = op=='*' ? num * st.top() : st.top()/num;
                    st.pop();
                    st.push(t);
                }
                op = s[i];
                num = 0;
            }
        }
        while(!st.empty()){
            res += st.top();
            st.pop();
        }
        return res;
    }
};

参考资料：
http://www.cnblogs.com/grandyang/p/4601208.html