题解 | #简单表达式计算# 经典双栈法

#include <iostream>
#include <stack>
#include <string>
using namespace std;

// 计算两个数的运算结果
int calculate(int a, int b, char op) {
    switch (op) {
        case '+':
            return a + b;
        case '-':
            return a - b;
        case '*':
            return a * b;
    }
    return 0;
}

// 比较两个运算符的优先级
int priority(char op) {
    switch (op) {
        case '+':
            return 1;
        case '-':
            return 1;
        case '*':
            return 2;
    }
    return 0;
}

int main() {
    string str;
    while (cin >> str) {
        if (str == "END") {
            break;
        }
        stack<int> stk_num; // 数字栈
        stack<char> stk_op; // 符号栈
        for (int i = 0; i < str.size(); i++) {
            if (isdigit(str[i])) {
                int num = str[i] - '0';
                while (i + 1 < str.size() && isdigit(str[i + 1])) {
                    num = num * 10 + (str[i + 1] - '0');
                    i++;
                }
                stk_num.push(num);
            } else if (str[i] == '+' || str[i] == '-' || str[i] == '*') {
                // 当符号栈非空 且 当前读到的符号优先级比栈顶的优先级低时
                // 依次取出数字栈的两个数进行运算 直到符号栈空了或者优先级低了
                while (!stk_op.empty() && priority(stk_op.top()) >= priority(str[i])) {
                    int b = stk_num.top();
                    stk_num.pop();
                    int a = stk_num.top();
                    stk_num.pop();
                    stk_num.push(calculate(a, b, stk_op.top()));
                    stk_op.pop();
                }
                // 符号栈压入当前符号
                stk_op.push(str[i]);
            }
        }
        // 最后栈里还剩有未计算的数
        while (!stk_op.empty()) {
            int b = stk_num.top();
            stk_num.pop();
            int a = stk_num.top();
            stk_num.pop();
            stk_num.push(calculate(a, b, stk_op.top()));
            stk_op.pop();
        }
        cout << stk_num.top() << endl;
    }
    return 0;
}

时间复杂度：假设输入字符串的长度为n

1、遍历输入字符串的时间复杂度为O(n)。

2、在遍历过程中，对于每个字符，最坏情况下需要进行多次操作（如将连续数字字符转换为整数、进行运算等），但总体来说每个字符只会被处理一次，因此总体时间复杂度仍为O(n)。

空间复杂度：使用了两个栈stk_num和stk_op来存储数字和运算符，其空间复杂度取决于输入字符串中数字和运算符的数量，最坏情况下为O(n)。