题解 | #四则运算#

使用符号栈和数值栈，在当前符号优先级高于栈顶符号时进栈，优先级等于和小于时出栈执行计算。左括号必须进栈，但优先级设置为最低，右括号必出栈直到对应的左括号出栈。

#include <iostream>
#include <vector>
#include <sstream>
using namespace std;


void pop_and_cal(vector<int> &values, vector<char> &ops) {
    char op = ops.back();
    ops.pop_back();
    int num2 = values.back();
    values.pop_back();
    int num1 = values.back();
    values.pop_back();
    int result = 0;
    switch(op) {
        case '+': result = num1 + num2; break;
        case '-': result = num1 - num2; break;
        case '*': result = num1 * num2; break;
        case '/': result = num1 / num2; break;
    }
    values.push_back(result);
}

// 处理正负号，统一括号
string preprocess(string line) {
    stringstream ss;
    bool last_is_value = false; 

    for(char c : line) {
        // 给正负号前加一个数字0
        if (!last_is_value 
            && (c == '-' || c == '+')) {
            ss << 0;
        }
        // 替换括号
        switch(c) {
            case '[':
            case '{': c = '('; break;
            case ']':
            case '}': c = ')'; break;
        }
        if ((c >= '0' && c <= '9')
           || c == ')') {
            last_is_value = true;
        } else {
            last_is_value = false;
        }
        ss << c;
    }
    return ss.str();
}

int cal(string &raw_exp) {
    int prior[128] = {0};
    vector<int> values;
    vector<char> ops;
    string exp = preprocess(raw_exp);

    prior['('] = 0;
    prior[')'] = 0;
    prior['+'] = 10;
    prior['-'] = 10;
    prior['*'] = 20;
    prior['/'] = 20;

    int state = 0;
    int i = 0;

    while(i < exp.size()) {
        char c = exp[i];
        if ( c >= '0' && c <= '9') {
            int value;
            stringstream ss;
            // 读取数字的所有位
            while(i < exp.size()) {
                c = exp[i];
                if ( c < '0' || c > '9') {
                    break;
                }
                ss << c;
                i++;  
            } 
            ss >> value;
            values.push_back(value);
        }
        if (i >= exp.size()) break;

        if (c == ')') {
            while(ops.back() != '(') {
                pop_and_cal(values, ops);
            }
            ops.pop_back();
        } else if(c == '(') {
            ops.push_back(c);
        } else {
            while (ops.size() > 0 && prior[c] <= prior[ops.back()]) {
                pop_and_cal(values, ops);
            }
            ops.push_back(c);
        }
        i++;
    }
    while(ops.size() > 0) pop_and_cal(values, ops);
    return values.back();
}

int main() {
    string line;

    while(getline(cin, line)) {
        cout << cal(line) << endl;
    }
}