题解 | 表达式求值

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

void compute(stack<int>& st_num, stack<char>& st_op){
    int num_b = st_num.top();
    st_num.pop();
    int num_a = st_num.top();
    st_num.pop();
    char op = st_op.top();
    st_op.pop();

    switch (op) {
    case '+':
        num_a = num_a + num_b;
        break;
    case '-':
        num_a = num_a - num_b;
        break;
    case '*':
        num_a = num_a * num_b;
        break;
    case '/':
        num_a = num_a / num_b;
        break;
    default:
        break;
    }

    st_num.push(num_a);
}

bool priority(const char& m, const char& n){
    if (m == '(') {
        return false;
    } else if ((m == '+' || m == '-') && (n == '*' || n == '/')) {
        return false;
    }

    return true;
}

int main() {
    string str;
    cin >> str;

    stack<int> st_num;
    stack<char> st_op;

    st_op.push('(');
    str += ')';
    bool flag = false; // 判断是否是运算符还是正负号

    for (int i = 0; i < str.size(); i ++) {
        if (str[i] == '(') {
            st_op.push('(');
        } else if (str[i] == ')') {
            while (st_op.top() != '(') {
                compute(st_num, st_op);
            }
            st_op.pop(); // 弹出左括号
        } else if (flag) { // 运算符
            while (priority(st_op.top(), str[i])) {
                compute(st_num, st_op);
            }
            st_op.push(str[i]);
            flag = false;
        } else { //数字
            // 类比双指针的思想，截取数字
            int right = i;
            if (str[right] == '-' || str[right] == '+') {
                right ++;
            }
            while (isdigit(str[right])) {
                right ++;
            }
            string temp_num = str.substr(i, right - i);
            st_num.push(stoi(temp_num));
            i = right - 1;
            flag = true;
        }
    }

    cout << st_num.top() << endl;

    return 0;
}
// 64 位输出请用 printf("%lld")