题解 | #表达式求值#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 返回表达式的值
     * @param s string字符串 待计算的表达式
     * @return int整型
     */
    public int solve (String s) {
        // write code here
        // 有括号匹配问题，用栈来解决
        // 思路：遇到括号，记录左括号起点，遇到跟它匹配的括号，递归计算这个内容
        // stack里面装的全部都是处理过的数据，最后把数据加起来即可。
        // 遇到 -，把数据变成-num再入栈；遇到+，直接入栈
        // 遇到*，弹出当前元素，乘上再入栈，遇到÷，弹出当前元素，再除以之后入栈
        Stack<Integer> stack = new Stack<>();
        // 从左到右，把字符转换为数字
        int num = 0;
        // 加减乘除，四种符号，遇到它，不同处理，默认为+，因为第一个数字可以看作前面有一个加号
        char sign = '+';
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            // 遇到的是数字
            if (Character.isDigit(ch)) {
                num = num * 10 + (ch - '0');
            }
            if (ch == '(') {
                // 记录此时出现的左括号的起点，之后找到与它对应的右括号，再来算一遍这中间的
                // 还需要一个变量来记录括号情况，出现左括号一次，+1，出现一次右括号，-1，计数为0说明是匹配的
                int j = i, count = 0;
                for (; i < s.length(); i++) {
                    if (s.charAt(i) == '(') {
                        count++;
                    }
                    if (s.charAt(i) == ')') {
                        count--;
                    }
                    if (count == 0) {
                        //说明此刻的左右括号是匹配的，开始进行递归，退出这层for循环
                        break;
                    }
                }
                // 从左括号下一位开始，到右括号之前，因为substring不包含右端点
                // 递归计算的结果，要把它重新给num
                num = solve(s.substring(j + 1, i));
            }
            // 遇到的是符号，或者到了最后一位，也要把数字压入栈
            if (ch == '+' || ch == '-' || ch == '*' || ch == '/' || i == s.length() - 1) {
                if (sign == '+') {
                    stack.push(num);
                } else if (sign == '-') {
                    stack.push(-num);
                } else if (sign == '*') {
                    stack.push(stack.pop() * num);
                } else if (sign == '/') {
                    stack.push(stack.pop() / num);
                }
                sign = ch;
                // 这个容易掉了，要把数字清零，重新计算
                num = 0;
            }
        }
        int res = 0;
        while (!stack.isEmpty()) {
            res = res + stack.pop();
        }
        return res;

    }

}

这里面有很多小细节。首先需要先对sign进行赋值，这样第一个数字，在没有符号的情况下，默认是加号的。

我一开始把判断括号的if语句放在最后面，这是有问题的，比如我执行，"(1+2)+(3+4)+(5+7)"，对于后面的一个括号，i的值已经到最后了，此时通过递归刚好把5+7算出来等于12，就退出循环了，这样12就不能加进去。所以把判断符号以及是否是结尾改成放在了最后。这样即使执行到最后的括号，也会再次检查是否执行到了结尾，如果到了结尾，也会再把数字加进去。