表达式求值

分为三块，一块处理数字，一块处理括号，一块处理符号。最后将数字加起来放入list即可。

对于上述两个要求，我们要考虑的是两点，一是处理运算优先级的问题，二是处理括号的问题。

处理优先级问题，那必定是乘号有着优先运算的权利，加号减号先一边看，我们甚至可以把减号看成加一个数的相反数，则这里只有乘法和加法，那我们优先处理乘法，遇到乘法，把前一个数和后一个数乘起来，遇到加法就把这些数字都暂时存起来，最后乘法处理完了，就剩余加法，把之前存起来的数字都相加就好了。

处理括号的问题，我们可以将括号中的部分看成一个新的表达式，即一个子问题，因此可以将新的表达式递归地求解，得到一个数字，再运算。

step 1：使用栈辅助处理优先级，默认符号为加号。 step 2：遍历字符串，遇到数字，则将连续的数字字符部分转化为int型数字。 step 3：遇到左括号，则将括号后的部分送入递归，处理子问题；遇到右括号代表已经到了这个子问题的结尾，结束继续遍历字符串，将子问题的加法部分相加为一个数字，返回。 step 4：当遇到符号的时候如果是+，得到的数字正常入栈，如果是-，则将其相反数入栈，如果是*，则将栈中内容弹出与后一个元素相乘再入栈。 step 5：最后将栈中剩余的所有元素，进行一次全部相加。

 public ArrayList<Integer> function(String s,int index){
        Stack<Integer> stack=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=function(s,i+1);
                num=res.get(0);
                i= res.get(1);
                if(i!=s.length()-1) continue;

            }

            switch (op){

                case '+':
                    stack.push(num);
                    break;
                case '-':
                    stack.push(-num);
                    break;
                case '*':
                    int temp= stack.pop();
                    stack.push(temp*num);
                    break;
            }
            num=0;
            if(s.charAt(i)==')') break;
            else op=s.charAt(i);
        }

        int sum=0;
        while (!stack.isEmpty()) sum+=stack.pop();
        ArrayList<Integer> temp=new ArrayList<Integer>();
        temp.add(sum);
        temp.add(i);
        return temp;

    }

    public int solve (String s) {
        // write code here
        ArrayList<Integer> list=function(s,0);
        return list.get(0);
    }