题解 | #表达式求值#

思路：

1. 将表达式转为逆波兰式；
2. 计算逆波兰式的值。
   PS:默认表达式中不含空格。

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

// 通过一个单调栈（存储操作符）将表达式转为逆波兰式
string trans(string exp) {
    stack<char> opt_stk;
    int idx = 0, len = exp.length();
    string ans;
    char num_sign = '#';
    while (idx < len) {
        switch (exp[idx]) {
            case '(':
                opt_stk.push('(');
                idx++;
                break;
            case ')':
                while (opt_stk.top() != '(') {
                    ans += opt_stk.top();
                    opt_stk.pop();
                }
                opt_stk.pop();
                idx++;
                break;
            case '+':
            case '-':
                // 以下两种情况将负号视作符号位，不将其入栈
                // 1. 负号在第一位
                // 2. 负号前一位字符不是数字，也不是反括号
                if (exp[idx] == '-' && (idx == 0 || (idx > 0 && exp[idx-1] != ')' && !isdigit(exp[idx-1])))) {
                    num_sign = '@';
                    idx++;    
                } else {
                    while (!opt_stk.empty() && opt_stk.top() != '(') {
                    ans += opt_stk.top();
                    opt_stk.pop();
                    }
                    opt_stk.push(exp[idx++]);
                }
                break;
            case '*':
            case '/':
                while (!opt_stk.empty()) {
                    char c = opt_stk.top();
                    if (c == '*' || c == '/') {
                        ans += c;
                        opt_stk.pop();
                    } else 
                        break;
                }
                opt_stk.push(exp[idx++]);
                break;
            default:
                while (idx < len && exp[idx] <= '9' && exp[idx] >= '0') 
                    ans += exp[idx++];
                ans += num_sign;
                if (num_sign == '@') num_sign = '#';
        }
    }
    while (!opt_stk.empty()) {
        ans += opt_stk.top();
        opt_stk.pop();
    }
    return ans;
}

// 也只用一个栈，栈中存放的是操作数
double compute_value(string exp) {
    stack<double> stk;
    int idx = 0, len = exp.length();
    while (idx < len) {
        char c = exp[idx];
        if (c == '+') {
            double a = stk.top(); 
            stk.pop();
            double b = stk.top();
            stk.pop();
            stk.push(a + b);
        } else if (c == '-') {
            double a = stk.top(); 
            stk.pop();
            double b = stk.top();
            stk.pop();
            stk.push(b - a);
        } else if (c == '*') {
            double a = stk.top(); 
            stk.pop();
            double b = stk.top();
            stk.pop();
            stk.push(a * b);
        } else if (c == '/') {
            double a = stk.top(); 
            stk.pop();
            double b = stk.top();
            stk.pop();
            stk.push(b / a);
        } else {
            double num = 0;
            while (exp[idx] <= '9' && exp[idx] >= '0') 
                num = num * 10 + exp[idx++] - '0';
            if (exp[idx] == '@') num = -num;
            stk.push(num);
        }
        idx++;
    }
    return stk.top();
}

int main() {
    string exp;
    cin >> exp;
//     cout << trans(exp) << endl;
    cout << compute_value(trans(exp));

    return 0;
}