227. Basic Calculator II

问题

Implement a basic calculator to evaluate a simple expression string.

The expression string contains only non-negative integers, +, -, *, / operators and empty spaces . The integer division should truncate toward zero.

You may assume that the given expression is always valid.

例子

"3+2*2" = 7
" 3/2 " = 1
" 3+5 / 2 " = 5

分析

1 使用istringstream，将字符串变成字符流，自动分割字符串并直接转换成数字或字符
2 使用栈，保存表达式中的数字或者两个数字*/的结果
3 遍历栈，将栈元素依次相加即可得到表达式的计算结果

举个例子，对于表达式3-5/2，首先初始化运算符为+号，即表达式变成+3-5/2；将+3压入栈，-5压入栈，发现下一个运算符是/，将-5出栈，将-5/2=-2入栈。

要点

• istringstream可以处理任意多空格分割的字符串
• 用栈来保存上一步的数字
• 用vector模拟栈

时间复杂度

O(n)

空间复杂度

O(n)

代码

class Solution {
public:
    int calculate(string s) {
        vector<int> stk;
        istringstream iss(s);
        char op = '+';
        int res = 0, term;
        while (iss >> term) {
            if (op == '+' || op == '-') {
                stk.push_back(op == '+' ? term : -term);
            }
            else {
                int last = stk.back();
                stk.pop_back();
                stk.push_back(op == '*' ? last * term : last / term);
            }
            iss >> op;
        }
        for (int num : stk)
            res += num;
        return res;
    }
};