题解 | 表达式求值

import java.util.*;

// 参考：https://blog.nowcoder.net/n/b825074c53dc4d178e7f6bde8b8bbbf3
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回表达式的值
     * @param s string字符串 待计算的表达式
     * @return int整型
     */
    public int solve (String s) {
        // write code here
        return calc(s,0).get(0);
    }

    // 123*(456+789)*1
    ArrayList<Integer> calc(String s,int index){
        // 栈来存计算后的结果
        Stack<Integer> st = new Stack<Integer>();
        int num = 0;
        char op = '+';
        int i;
        for(i = index;i<s.length();i++){
            // 依次读取数字
            if(s.charAt(i) >= '0' && s.charAt(i) <= '9'){
                num = num*10 + s.charAt(i) - '0';
                if(i != s.length()-1){
                    continue;
                }
            }

            // 处理括号
            if(s.charAt(i) == '('){
                // 递归处理括号内的内容
                ArrayList<Integer> res = calc(s,i+1);// 传入当前索引的下一个位置（即i+1）
                num = res.get(0);
                i = res.get(1);// 更新i的位置
                if(i != s.length()-1){
                    continue;
                }
            }

            // 处理操作符 + - *
            switch(op){
                case '+':
                    st.push(num);
                    break;
                case '-':
                    // 负数，取num的相反数
                    st.push(-num);
                    break;
                case '*':
                    int temp = st.pop();
                    st.push(temp * num);
                    break;
            }

            num = 0; // 重置
            // 递归的结束条件
            if(s.charAt(i) == ')'){
                break;
            }else{
                op = s.charAt(i);
            }
        }
        int sum = 0;
        // 栈中元素相加
        while(!st.isEmpty()){
            sum += st.pop();
        }
        ArrayList<Integer> temp = new ArrayList<>();
        temp.add(sum);
        temp.add(i);
        return temp;
    }
}