题解 | #表达式求值#TOP49

思路:
1.字符串拆成数组，用栈来保存每个运算的数，例如 a + b， 栈中先入 a,再入b,如果a / b，，栈中先入a,然后再取出a,入a/b。
2.先比如是 10 + 20 / 30,栈中存放10，然后再进行 + 20运算，遇到20，则判断符号位是+,则20入栈，然后遍历到30，发现前面是/，则取出20进行除以操作，将20/30入栈
3.遇到(，求与之匹配的)，然后递归就可。

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 返回表达式的值
     * @param s string字符串 待计算的表达式
     * @return int整型
     */
    public int solve (String s) {
        // write code here
        if (s == null || s.length() == 0) {
            return 0;
        }
        char[] data = s.toCharArray();
        int n = data.length;
        //默认是 + 号 第一个数字作为 + a
        char sign = '+';
        //可能连续两个都是数字，只有遇到符号才重置
        int number = 0;
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < n; i++) {
            char item = data[i];
            if (item == ' ') {
                continue;
            }
            if (item >= '0' && item <= '9') {
                //可能是连续的两位数字
                number = number * 10 + item - '0';
            }

            if (item == '(') {
                int j = i + 1;
                int brackets = 1;
                while (brackets > 0) {
                    if (data[j] == ')') {
                        brackets --;
                    } else if (data[j] == '(') {
                        brackets ++;
                    }
                    j++;
                }
                // (xxx） [i+1, j-1) j指向的是)下一个数
                number = solve(s.substring(i + 1, j - 1));
                i = j - 1;
            }
            if (item < '0' || item > '9' || i == n - 1 ) {
                //触发运算条件的控制逻辑
                if (sign == '+') {
                    stack.push(number);
                } else if (sign == '-') {
                    stack.push(-1 * number);
                } else if (sign == '/') {
                    stack.push(stack.pop() / number);
                } else if (sign == '*') {
                    stack.push(stack.pop() * number);
                }
                number = 0;
                sign = item;
            }
        }

        int ans = 0;
        while (!stack.isEmpty()) {
            ans += stack.pop();
        }
        return ans;
    }
}