题解 | 四则运算

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

void cal(stack<char>& op, stack<int>& nums) {
    char operate = op.top();
    op.pop();
    int right = nums.top();
    nums.pop();
    int left = nums.top();
    int result;
    nums.pop();
    switch (operate) {
        case '+':
            result = left + right;
            break;
        case '-':
            result = left - right;
            break;
        case '*':
            result = left * right;
            break;
        case '/':
            result = left / right;
            break;
    }
    nums.push(result);
}

int priority(const char& op) {
    switch (op) {
        case '+':
            return 1;
            break;
        case '-':
            return 1;
            break;
        case '*':
            return 2;
            break;
        case '/':
            return 2;
            break;
        default:
            return 0;
            break;
    }
}

void dispaly_stack(stack<int> nums, stack<char> ops) {
    cout << "栈情况：\n";
    while (nums.size()) {
        cout << nums.top() << " ";
        nums.pop();
    }
    cout << endl;
    while (ops.size()) {
        cout << ops.top() << " ";
        ops.pop();
    }
    cout << endl;
}

int main() {
    string tmp;
    cin >> tmp;
    string exp('(' + tmp + ')');
    stack<int> nums;
    stack<char> ops;
    for (int i = 0; i < exp.size();) {
        if ((exp[i] == '-' && (exp[i - 1] == '(' || exp[i - 1] == '[' ||
                               exp[i - 1] == '{'))
                || isdigit(exp[i])) {
            int j = i;
            while (isdigit(exp[++j])) {
            }
            nums.push(stoi(exp.substr(i, j - i)));
            i = j;
        } else if (exp[i] == '(' || exp[i] == '[' || exp[i] == '{'
                   || priority(exp[i]) > priority(ops.top())) {
            //下一个运算符优先级比栈顶运算符还高,或者左括号，先入栈
            ops.push(exp[i++]);
        } else if (exp[i] == ')' || exp[i] == ']' || exp[i] == '}') {
            //遇到反括号，一路计算清空直到左括号
            while (!ops.empty() && ops.top() != '(' && ops.top() != '[' &&
                    ops.top() != '{') {
                cal(ops, nums);
            }
            ops.pop();  // 弹出左括号
            ++i;
        } else {
            //遇到优先级比栈顶低，先进行栈运算,再将运算符进栈
            while (!ops.empty() && priority(exp[i]) <= priority(ops.top())) {
                cal(ops, nums);
            };
            ops.push(exp[i++]);
        }
    }
    cout<<nums.top()<<endl;
}

双栈法，一个数字栈（包含负数的情况），一个符号栈（包含括号情况）。遍历待处理字符串的每一个字符，根据字符情况分以下四种情况分类讨论：

1.数字（包含负数和多位数）：数字一定是连续存在的，我们只要定位到第一个数字位置和下一个非数字位置，中间的子串一定是数字部分，使用stoi()函数对目标子串进行处理然后弹入数字栈。注意如果是负数，第一个识别到的字符是‘-’，这个情况需要区别减号‘-’，我是通过查看‘-’负号前面那一位是否是括号类字符来判定是不是负号。所以我在初始字符串的首尾加入了左右括号，以便处理字符串第一个字符就是符号的情况。

2.左括号或者高级别运算符（‘*’和‘/’）：此时栈中顶部位置不能直接计算（优先级高的要先算，但是还没入栈），直接弹入符号栈

3.右括号：碰到右括号说明栈中保存有可计算表达式，直接执行cal()函数直到符号栈栈顶为左括号，计算完后弹出左括号。

4.低级别运算符（‘+’和‘-’）:此时栈中顶部位置可以直接计算，一直算直到符号栈的左括号为止。