题解 | #表达式求值#

#include<bits/stdc++.h>#include <cctype> // 用于isdigit函数#include <memory> // 用于unique_ptr#include <queue> // 用于优先队列using namespace std;

class Solution {public:/*** solve函数接收一个字符串形式的数学表达式，并返回其计算结果* @param s string字符串 待计算的表达式* @return int整型 计算结果*/int solve(string s) {stack<int> numbers; // 用于存储数字的栈stack<char> operators; // 用于存储操作符的栈

    // 遍历表达式字符串
    for (int i = 0; i < s.size(); ++i) {
        // 如果当前字符是数字，则解析整个数字
        if (isdigit(s[i])) {
            int num = 0;
            // 解析多位数
            while (i < s.size() && isdigit(s[i])) {
                num = num * 10 + (s[i++] - '0');
            }
            --i; // 因为在循环结束时i会自增，所以这里要减一
            numbers.push(num); // 将解析出的数字压入数字栈
        } else if (s[i] == '(') {
            // 如果当前字符是左括号，则将其压入操作符栈
            operators.push(s[i]);
        } else if (s[i] == ')') {
            // 如果当前字符是右括号，则计算括号内的表达式
            while (operators.top() != '(' && !operators.empty()) {
                // 弹出操作符和操作数，计算结果并压入数字栈
                int op2 = numbers.top(); numbers.pop();
                int op1 = numbers.top(); numbers.pop();
                char op = operators.top(); operators.pop();
                numbers.push(Operation(op1, op2, op));
            }
            operators.pop(); // 弹出左括号
        } else {
            // 如果当前字符是操作符，则处理栈中的操作符
            if (!operators.empty() && Priority(operators.top()) >= Priority(s[i])) {
                // 如果栈顶操作符的优先级大于或等于当前操作符，则进行计算
                int op2 = numbers.top(); numbers.pop();
                int op1 = numbers.top(); numbers.pop();
                char op = operators.top(); operators.pop();
                numbers.push(Operation(op1, op2, op));
            }
            operators.push(s[i]); // 将当前操作符压入操作符栈
        }
    }

    // 处理栈中剩余的操作符
    while (!operators.empty()) {
        int op2 = numbers.top(); numbers.pop();
        int op1 = numbers.top(); numbers.pop();
        char op = operators.top(); operators.pop();
        numbers.push(Operation(op1, op2, op));
    }

    // 数字栈的栈顶元素即为最终的计算结果
    return numbers.top();
}

private:// Operation函数根据操作符计算两个操作数的运算结果int Operation(int a, int b, char op) {switch (op) {case '+': return a + b;case '-': return a - b;case '*': return a * b;}return 0;}

// Priority函数返回操作符的优先级
int Priority(char op) {
    if (op == '*') return 2;
    if (op == '+' || op == '-') return 1;
    return 0;
}

};

int main() {Solution solution;string expression = "3 + 5 * (2 - 8)"; // 定义一个表达式cout << "The result is: " << solution.solve(expression) << endl; // 输出计算结果return 0;}