题解 | 表达式求值

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

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回表达式的值
     * @param s string字符串 待计算的表达式
     * @return int整型
     */
    int solve(string s) {
        stack<int> nums;
        stack<char> ops;
        
        for (int i = 0; i < s.length(); i++) {
            char c = s[i];
            
            if (c == ' ') {
                continue; // 跳过空格
            }
            
            if (isdigit(c)) {
                // 解析完整数字
                int num = 0;
                while (i < s.length() && isdigit(s[i])) {
                    num = num * 10 + (s[i] - '0');
                    i++;
                }
                nums.push(num);
                i--; // 回退一位
            }
            else if (c == '(') {
                ops.push(c);
            }
            else if (c == ')') {
                // 计算括号内的所有运算
                while (!ops.empty() && ops.top() != '(') {
                    calculate(nums, ops);
                }
                ops.pop(); // 弹出左括号
            }
            else if (c == '+' || c == '-' || c == '*') {
                // 处理运算符优先级
                while (!ops.empty() && getPriority(ops.top()) >= getPriority(c)) {
                    calculate(nums, ops);
                }
                ops.push(c);
            }
        }
        
        // 处理剩余的运算
        while (!ops.empty()) {
            calculate(nums, ops);
        }
        
        return nums.top();
    }
    
private:
    // 获取运算符优先级
    int getPriority(char op) {
        if (op == '+' || op == '-') {
            return 1;
        } else if (op == '*') {
            return 2;
        }
        return 0; // 括号或其他
    }
    
    // 执行计算
    void calculate(stack<int>& nums, stack<char>& ops) {
        if (nums.size() < 2 || ops.empty()) return;
        
        char op = ops.top();
        ops.pop();
        int b = nums.top();
        nums.pop();
        int a = nums.top();
        nums.pop();
        int result = 0;
        
        switch (op) {
            case '+':
                result = a + b;
                break;
            case '-':
                result = a - b;
                break;
            case '*':
                result = a * b;
                break;
        }
        
        nums.push(result);
    }
};

这个解决方案的关键点：

1.双栈设计：
numbers栈：存储数字
operators栈：存储运算符和括号

2.运算符优先级：
* 的优先级最高（级别2）
+ 和 - 优先级相同（级别1）
( 优先级最低（级别0）

3.处理逻辑：
数字：直接压入数字栈
左括号：直接压入运算符栈
右括号：计算括号内的所有运算，直到遇到左括号
运算符：比较优先级，如果栈顶运算符优先级更高或相等，先计算栈顶运算

时间复杂度：O(n)，每个字符只处理一次
空间复杂度：O(n)，使用两个栈存储中间结果