下面将练习大量的树操作

package 乒乒乓乓;

import java.io.ObjectInputStream.GetField;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.Stack;
/*
 * http://blog.csdn.net/yhhazr/article/details/7947962
 * */
public class 表达式求值 {
    private static int res=0;
public static ArrayList<String> getPostOrder(ArrayList<String> inOrderList){
        
        ArrayList<String> result = new ArrayList<String>();
        Stack<String> stack = new Stack<String>();
        for (int i = 0; i < inOrderList.size(); i++) {
            if(Character.isDigit(inOrderList.get(i).charAt(0))){
                result.add(inOrderList.get(i));
            }else{
                switch (inOrderList.get(i).charAt(0)) {
                case ‘(‘:
                    stack.push(inOrderList.get(i));
                    break;
                case ‘)‘:
                    while (!stack.peek().equals("(")) {
                        result.add(stack.pop());
                    }
                    stack.pop();
                    break;
                default:
                    while (!stack.isEmpty() && compare(stack.peek(), inOrderList.get(i))){
                        result.add(stack.pop());
                    }
                    stack.push(inOrderList.get(i));
                    break;
                }
            }
        }
        while(!stack.isEmpty()){
            result.add(stack.pop());
        }
        return result;
    }
    //将字符串中数字和符号分开,传到arraylist中
    public static ArrayList<String> getStringList(String str){
        ArrayList<String> result = new ArrayList<String>();
        String num = "";
        for (int i = 0; i < str.length(); i++) {
            if(Character.isDigit(str.charAt(i))){
                num = num + str.charAt(i);
            }else{
                if(num != ""){
                    result.add(num);
                }
                result.add(str.charAt(i) + "");
                num = "";
            }
        }
        if(num != ""){
            result.add(num);
        }
        return result;
    }
    public static ArrayList<String> getExpress(String s)
    {
        
        ArrayList<String> array=new ArrayList<String>();
        String num="";
                for(int i=0;i<s.length();i++)
                {
                    if(Character.isDigit(s.charAt(i)))
                    {
                        num+=s.charAt(i);
                        
                        
                    }
                    else
                    {
                        array.add(num);
                        num="";
                        array.add(s.charAt(i)+"");
                        
                        
                    }
                    
                    
                    
                    
                    
                    
                }
                if(num!="")
                {
                    array.add(num);
                }
        return array;
        
        
        
        
        
    }
    public static boolean compare(String peek, String cur){
        if("*".equals(peek) && ("/".equals(cur) || "*".equals(cur) ||"+".equals(cur) ||"-".equals(cur))){
            return true;
        }else if("/".equals(peek) && ("/".equals(cur) || "*".equals(cur) ||"+".equals(cur) ||"-".equals(cur))){
            return true;
        }else if("+".equals(peek) && ("+".equals(cur) || "-".equals(cur))){
            return true;
        }else if("-".equals(peek) && ("+".equals(cur) || "-".equals(cur))){
            return true;
        }
        return false;
    }
    
    
    //转化成后缀表达式
public static ArrayList<String> getPost(ArrayList<String> s)
    {
        
        ArrayList<String> res=new ArrayList<String>();
        Stack<String> oper=new Stack<String>();
        for(int i=0;i<s.size();i++)
        {
            if(Character.isDigit(s.get(i).charAt(0)))
            {
                res.add(s.get(i));
                //System.out.println(s.get(i));
            
                
                
            }
            else
            {
                //System.out.println(s.get(i));
                switch(s.get(i).charAt(0))
                {
                case ‘(‘:
                    
                    oper.push(s.get(i));
                    //System.out.println("(");
                    
                    break;
                case ‘)‘:
                    while(!oper.isEmpty()&&!oper.peek().equals("(") )
                    {
                        //System.out.println(oper.peek());
                        res.add(oper.pop());
                        
                        
                    }
                    oper.pop();
                    break;
                default:
                    //System.out.println(s.get(i));
                    while(!oper.isEmpty()&&compare(oper.peek(),s.get(i)))
                    {//System.out.println(oper.peek());
                        res.add(oper.pop());
                        
                        
                    }
                    oper.push(s.get(i));
                
                break;
                
                
                
                
                }
                
                
            
                
                
                
                
            }
            
            
            
            
        }
         while (!oper.isEmpty())
        {
            res.add(oper.pop());
        }
    
        return res;
        
        
        
        
    }
//后缀表达式计算
//遇到数字入栈，符号就取栈内数据，结果放入栈中
public static void calcute(ArrayList<String> post)
{
    Stack<Integer> stack=new Stack<Integer>();
    for(int i=0;i<post.size();i++)
    {
        if(Character.isDigit(post.get(i).charAt(0)))
                {
            
                         stack.push(Integer.parseInt(post.get(i)));
                         System.out.println(post.get(i));
            
                }
        else
        {
            int back=stack.pop();
            int font=stack.pop();
            
            switch(post.get(i).charAt(0))
            {
            
            case ‘+‘:
                res=font+back;
                
                break;
            case ‘-‘:
                res=font-back;
                
                break;
            case ‘*‘:
                res=font*back;
                
                break;
            case ‘/‘:
                res=font/back;
                
                break;
                default :
                    
            
            }
            
            
            stack.push(res);
        }
        
        
    }
    
    
    
}


    public static void main(String[] args)
    {
        String s = "12+(23*3-56+7)*(2+90)/2";
        ArrayList<String> a=new ArrayList<String>();
        //a=getExpress(s);
        a=getStringList(s);
        a=getPostOrder(a);
         //a=getPost(a);
    Iterator< String> iter=a.iterator();
        while(iter.hasNext())
        {
            System.out.print(iter.next()+"--");
        }
        
        System.out.println();
        
    calcute(a);
    System.out.println(res+"最终的结果");
        
    }

}