题目分析

计算器这个题目是经典的栈问题，在学习数据结构时，堆栈的重要应用场景就是实现复杂的数学运算。

栈

在本题没有括号的情况下，出现符号时记录运算操作，出现数字时，查看运算操作，如果是乘除法，则优先级最高，需要立即运算，因此从栈中弹出栈顶元素，与该数字进行操作，并将运算的结果作为新数字压入栈中。如果是加法则直接入栈，如果是减法则取相反数后入栈。最后按照顺序将栈中的所有元素相加即可。

算法的**时间复杂度为$O(n)$，空间复杂度为$O(n)$**。

#include<iostream>
#include<vector>

using namespace std;

class Solution {
public:
    int calculate(string s) {
        vector<int> stack;
        int length = s.size(), idx = 0, sign = 0, res = 0;
        while (idx < length) {
            if (s[idx] >= '0' && s[idx] <= '9') {
                int tmp = s[idx] - '0';
                while (idx + 1 < length && s[idx + 1] >= '0' && s[idx + 1] <= '9') tmp = tmp * 10 + (s[++idx] - '0');
                if (sign == 0) stack.push_back(tmp);
                else if (sign == 1) stack.push_back(-tmp);
                else if (sign == 2) stack[stack.size() - 1] *= tmp;
                else stack[stack.size() - 1] /= tmp;
            }
            else if (s[idx] != ' ') {
                if (s[idx] == '+') sign = 0;
                else if (s[idx] == '-') sign = 1;
                else if (s[idx] == '*') sign = 2;
                else sign = 3;
            }
            idx++;
        }
        for (auto x : stack) res += x;
        return res;
    }
};

刷题总结

栈类型的题目是非常经典的，栈也是应用非常广泛的数据结构，在笔试面试中都经常出现，希望大家能够注意类似的题目。