ref: https://blog.nowcoder.net/n/65fcad0be1a543359effef1228ae5d2e

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 返回表达式的值
     * @param s string字符串 待计算的表达式
     * @return int整型
     */
    public int solve (String s) {
        // write code here
        s = s.trim();
        // 用栈保存各部分计算的和
        Stack<Integer> stack=new Stack<>();
        int sum=0,number=0;// 使用 number 变量记录字符串中的数字部分的数字值是多少
        // 使用 sign 变量记录运算符(前面的)
        char sign='+';
        char[] cs=s.toCharArray();
        for(int i=0;i<cs.length;i++){
            char c=cs[i];

            //遇到左括号时递归求这个括号里面的表达式的值
            //先遍历找到对应的右括号，因为可能里面还嵌有多对括号，
            //使用一个变量 counterPartition 统计括号对数直到变量为 0
            if(c=='('){
                int j=i+1;
                int cntPar=1;
                while(cntPar>0){
                    if(cs[j]=='('){
                        cntPar++;
                    }
                    if(cs[j]==')'){
                        cntPar--;
                    }
                    j++;
                }
                // (3-4)    
                // i    j
                number=solve(s.substring(i+1,j-1));
                i=j-1;
            }
            // 遇到数字时继续遍历求这个完整的数字的值，保存到 number 中 
            if(Character.isDigit(c)){
                number=number*10+c-'0';
            }

            // 遇到运算符时或者到表达式末尾时，就去计算上一个运算符
            // 并把计算结果 push 进栈，然后保存新的运算符到 sign
            if(!Character.isDigit(c)||i==cs.length-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=c;
            }
        }

        // 最后把栈中的结果求和即可
        while(!stack.isEmpty()){
            sum+=stack.pop();
        }
        return sum;
    }
}