题目：

Basic Calculator的升级版，这次要求加括号了。分析：在Basic Calculator I里，做法是用stack存储整数，如果是乘除操作就先执行运算再存储，如果是加减的话就直接存储数据。这么做的实质其实是统一运算符的优先级——把优先级高的操作先执行掉，stack里存的数据都是优先级统一的加减操作，于是最后直接累加就可以了。在这里也可以采取类似的思路，用stack来维护数据的运算顺序，但是需要先解决两个问题：(1)如何给不同位置的运算符赋值？我们假设值越大的运算符优先级越高，比如说1+(2+34)-5这个表达式。初始的时候‘+’，‘-’的优先值是1， ‘’，‘/'的优先值是2，每一重左括号后的运算符优先值加3,每一个右括号后的优先值减3.因此上面表达式的四个运算符优先值是1,4,5,1。剩下的就是怎样找到一个数据结构，让优先级高的运算符两边的表达式先计算。(注意，这里是分支的策略，运算符两边的是表达式，不一定是数字)。(2)另一个问题是如何利用运算符的优先值进行计算。很直观的想法是要不要按照优先值排序，最高的最早参与计算？这是不对的。比如说表达式：(0 +（1 + 2）) -（3 + （4 * 5 - （6 + 7）））很明显，优先级最低的是中间的减号，把整个表达式分成了两个区间。这两个子区间之间的运算符需要按整体排序的顺序操作吗？肯定是不能这么做的。这里需要的不是整体有序，而是需要两个子区间内局部有序——在每个子区间里找到运算优先值最低的继续分治下去。所以这里就很适合用最小树(Cartersian tree)。即一个序列里的最小值为根节点，最小值把序列分为左右两个子系列，分别为左子树和右子树，子树仍然是最小树。叶子节点是数字，非叶子节点是运算符。接下来就很直观啦，运算顺序就是树的postorder，每个运算符操作它的左右两个子树(对应的就是左右两个表达式)。code:

import java.util.*;class Solution{    static class TreeNode{        int val;        String s;        TreeNode left;        TreeNode right;        public TreeNode(int val, String s){            this.val = val;            this.s = s;        }    }        static int getPrioriyValue(String s, int base){        if(s.equals("+") || s.equals("-")) return base + 1;        else if(s.equals("*") || s.equals("/")) return base + 2;        else return Integer.MAX_VALUE;    }        static TreeNode BuildMinTree(String[] expression){        int val = 0;        int base = 0;        Stack
    
      stack = new Stack
     
      ();        for(int i = 0; i < expression.length; i++){            if(expression[i].equals("(")){                base += 10;                continue;            }            if(expression[i].equals(")")){                base -= 10;                continue;            }            val = getPrioriyValue(expression[i], base);            TreeNode cur = new TreeNode(val, expression[i]);            //build tree O(n) time complexity            while(!stack.isEmpty() && cur.val <= stack.peek().val) cur.left = stack.pop();            if(!stack.isEmpty()) stack.peek().right = cur;            stack.push(cur);        }        TreeNode node = new TreeNode(0,"");        while(!stack.isEmpty()) node = stack.pop();        return node;    }        static ArrayList
      
        reorder(String[] expression){        TreeNode node = BuildMinTree(expression);        ArrayList
       
         list = new ArrayList
        
         ();        postOrder(node, list);        return list;    }        static void postOrder(TreeNode node, ArrayList
         
           list){ if(node == null) return; postOrder(node.left, list); postOrder(node.right, list); list.add(node.s); } static int calculate(ArrayList
          
            list){ Stack
           
             stack = new Stack
            
             (); for(String s : list){ if(s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/")){ int op2 = stack.pop(); int op1 = stack.pop(); if(s.equals("+")) stack.push(op1 + op2); if(s.equals("-")) stack.push(op1 - op2); if(s.equals("*")) stack.push(op1 * op2); if(s.equals("/")) stack.push(op1 / op2); } else stack.push(Integer.valueOf(s)); } if(stack.isEmpty()) return 0; else return stack.peek(); } public static void main(String[] args){ String[] expression ={"3", "*", "6", "-", "(", "23", "+", "7", ")", "/", "(", "1", "+", "2", ")"} ; ArrayList
             
               list = reorder(expression); for(String s : list) System.out.print(s + " "); System.out.println(""); int result = calculate(list); System.out.println(result); }}