题解 | #表达式求值#

#include <cctype>
#include <iostream>

#include <stack>
#include <unordered_map>

using namespace std;

bool isOpeartor(const char c) {
    switch (c) {
        case '+':
        case '-':
        case '*':
        case '/':
        case '(':
        case ')':
            return true;
    }
    return false;
}

int calculate(int lnum, int rnum, char opr) {
    int result;
    switch (opr) {
        case '+':
            result = lnum + rnum;
            break;
        case '-':
            result = lnum - rnum;
            break;
        case '*':
            result = lnum * rnum;
            break;
        case '/':
            result = lnum / rnum;
            break;
        default:
            result = -1;
            break;
    }
    return result;
}

int main() {
    stack<int> val;//操作数栈
    stack<char> op;//运算符栈
    op.push('#');

    unordered_map<char, int> priority =
    {{'#', 0}, {'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}, {'(', 0}};

    string expression;
    getline(cin, expression);

    for (size_t idx = 0; idx != expression.size(); ++idx) {
        char c = expression.at(idx);

        if (isOpeartor(c) && !(c == '-' && (idx == 0 ||
                expression[idx-1] == '('))) { //运算符 特殊处理：-1*(-1-1)
            if ('(' == c) {
                op.push(c); //(运算符直接入栈
            } else if (')' == c) { //)运算符则需要计算括号里面的内容
                char opr = op.top();
                op.pop();
                while ( opr != '(') {
                    int num1 = val.top();
                    val.pop();
                    int num2 = val.top();
                    val.pop();
                    int result = calculate(num2, num1, opr);
                    val.push(result);
                    opr = op.top();
                    op.pop();//(出栈
                }
                

            } else if ( priority[c] > priority[op.top()] ) {
                //不是括号运算符且优先级高于栈顶运算符，直接入栈
                op.push(c);
            } else {
                //优先级低于栈顶运算符，则需要将栈顶运算符和操作数出栈，进行计算
                while(priority[op.top()] >= priority[c]) {
                    char opr = op.top();
                    op.pop();
                    int num1 = val.top();
                    val.pop();
                    int num2 = val.top();
                    val.pop();
                    int result = calculate(num2, num1, opr);
                    val.push(result);
                }
                op.push(c);
            }
           
        } else if(isdigit(c) || c == '-') { //操作数或者负号
            bool positive = true;
            if(c == '-') {
                positive = false;
                ++idx;
            }
            int num = 0;
            while ( idx != expression.size()  && isdigit( c = expression[idx] ) ) {
                num = num * 10 + c - '0';
                ++idx;
            }
            if( !positive ) num = 0 - num;
            val.push(num);
            idx--;
        } else {
            continue;
        }
    }//字符串表达式遍历完成

    //将栈中剩下的元素依次出栈并计算结果
    while(op.top() != '#') {
        char opr = op.top();
        op.pop();
        int rnum = val.top();
        val.pop();
        int lnum = val.top();
        val.pop();
        val.push(calculate(lnum, rnum, opr));
    }

    cout << val.top() << "\n";
}
// 64 位输出请用 printf("%lld")