operatetree.java

来自「经典问题」· Java 代码 · 共 446 行

//package datastruct;


import java.util.*;
import java.math.*;


public class OperateTree {
    
    int[] prior =new int[300];
    char[] oper={'(',')','+','-','*','/','^'};
    Scanner scan;
    static Scanner scan1;
    
    public OperateTree()
    {
        for(int i=0;i<7;i++)
           prior[oper[i]]=i+2;
        prior[oper[2]]=prior[oper[3]];
        prior[oper[4]]=prior[oper[5]];
    }    
    
    public TreeNode InputPreExpr(String E,Scanner s)
    {   
        TreeNode t;
        String st;
        
        if(!s.hasNext()) return null;
        st=s.next();
        t=new TreeNode(st);
        if(prior[st.charAt(0)]>0)    
        {
            t.lchild=InputPreExpr(E,s);
            t.rchild=InputPreExpr(E,s);
        }
        else
        {
            t.lchild=null;
            t.rchild=null;
        }
        return t;           
    }
    
    public TreeNode PostExpr(String E1)
    {
        TreeNode t;
        char c;
        String st;
        scan=new Scanner(E1);
        
        Stack<TreeNode> s1=new Stack<TreeNode>();
        Stack<TreeNode> s2=new Stack<TreeNode>();
        
        while(scan.hasNext())
        {
            st=scan.next();
            if(prior[st.charAt(0)]==0)
            {
                t=new TreeNode(st);
                s1.push(t);
            }
            else
            {
                switch(st.charAt(0))
                {
                    case '(':
                        t=new TreeNode(st);
                        s2.push(t);
                    break;
                    case ')':
                        c=s2.peek().data.charAt(0);
                        s2.pop();
                        while(c!='(')
                        {
                            t=new TreeNode(String.valueOf(c));
                            t.rchild=s1.pop();
                            t.lchild=s1.pop();
                            s1.push(t);
                            c=s2.peek().data.charAt(0);
                            s2.pop();
                        }
                    break;
                    default:
                        while(!s2.empty()&&
                                prior[s2.peek().data.charAt(0)]>=prior[st.charAt(0)])
                        {
                            t=new TreeNode(s2.peek().data);
                            if(!s1.empty()){t.rchild=s1.pop();}
                            if(!s1.empty()){t.lchild=s1.pop();}
                            s1.push(t);
                            s2.pop();
                        } 
                        if(scan.hasNext())
                        {
                            t=new TreeNode(st);
                            s2.push(t);
                        } 
                     break;   
                }        
            }
        }
        while(!s2.empty())
        {
            t=new TreeNode(s2.peek().data);
            if(!s1.empty()){t.rchild=s1.pop();}
            if(!s1.empty()){t.lchild=s1.pop();}
            s1.push(t);
            s2.pop();
        }        
        return s1.pop();
    } 
    
    public void OutputExpr(TreeNode T)
    {
        Stack<TreeNode> s=new Stack<TreeNode>();
        Stack<TreeNode> s1=new Stack<TreeNode>();
        TreeNode p,temp,op1=null;
        TreeNode parent=null;
        
        p=T;
        if(prior[T.data.charAt(0)]>0)   op1=T;
        
        while(p!=null||!s.empty())
        {
            if(p!=null)
            {
                s.push(p);
                if(p!=null&&prior[p.data.charAt(0)]>0&&prior[p.data.charAt(0)]==prior[op1.data.charAt(0)])
                {    
                    op1=p;
                }    
                if(prior[p.data.charAt(0)]>0&&prior[p.data.charAt(0)]<prior[op1.data.charAt(0)]&&(p==op1.lchild||p==op1.rchild)
                        ||prior[p.data.charAt(0)]>0&&p==op1.rchild&&prior[p.data.charAt(0)]==prior[op1.data.charAt(0)])
                {
                    System.out.print("(");
                    op1=p;
                    temp=p;
                    while(temp.rchild!=null)
                    {
                        parent=temp.rchild;
                        temp=temp.rchild;
                    }
                    s1.push(parent);
                }
                p=p.lchild;
                if(p!=null&&prior[p.data.charAt(0)]>0&&prior[p.data.charAt(0)]>prior[op1.data.charAt(0)])
                {
                    op1=p;
                }    
            }
            else
            {
                p=s.pop();
                if(p!=null)
                    System.out.print(p.data);
                if(!s1.empty()&&p!=null&&p==s1.peek())
                {
                    System.out.print(")");
                    s1.pop();
                }
                if(prior[p.data.charAt(0)]>0&&prior[p.data.charAt(0)]==prior[op1.data.charAt(0)])
                {
                    op1=p;
                }
                p=p.rchild;
                if(p!=null&&prior[p.data.charAt(0)]>0&&prior[p.data.charAt(0)]>prior[op1.data.charAt(0)])
                {
                    op1=p;
                }    
            }
        }    
    } 
    
    public void SetValue(TreeNode T)
    {
        scan=new Scanner(System.in);
        String cc;
        int cc1;
        
        while(!isComplete(T))
        {
            System.out.println("\nPlease enter a Value and the number you want to set:");
            cc=scan.next();
            cc1=scan.nextInt();
            while(cc1>999||cc1<0)
            {
                cc=scan.next();
                cc1=scan.nextInt();
            }
            Set(T,cc,cc1);
            OutputExpr(T);
        }            
    } 
    
    public boolean isComplete(TreeNode T)
    {
        Stack<TreeNode> s2=new Stack<TreeNode>();
        TreeNode p;
        
        p=T;
        while(p!=null||!s2.empty())
        { 
            if(p!=null){s2.push(p);p=p.lchild;}
            else
            {
                p=s2.pop();
                if(p!=null)
                {
                    if(Character.isLetter(p.data.charAt(0)))
                    {
                        return false;
                    }    
                } 
                p=p.rchild;
            }
        } 
        return true;
    }
    
    public void Set(TreeNode T,String cc,int cc1)
    {
        if(T!=null)
        {
            if(T.data.equals(cc)) T.data=String.valueOf(cc1);
            Set(T.lchild,cc,cc1);
            Set(T.rchild,cc,cc1);
        }
        return;
    }
    
    public int GetValue(TreeNode T)
    {
        Stack<TreeNode> s3=new Stack<TreeNode>();
        Stack<Integer> s4=new Stack<Integer>();
        int flag=1;
        TreeNode p,temp;
        int con;
        int con1;
        
        p=T;
        while(p!=null||!s3.empty())
        {
            while(p!=null){s3.push(p);p=p.lchild;}
            temp=null;
            flag=1;
            while(!s3.empty()&&flag!=0)
            {
                p=s3.peek();
                if(p.rchild==temp)
                {
                    if(Character.isDigit(p.data.charAt(0)))
                        s4.push(Integer.parseInt(p.data));
                    else
                    {
                        try{
                            switch(p.data.charAt(0))
                            {
                            case '+': 
                                    con=s4.pop()+s4.pop();
                                    s4.push(con);  
                            break;
                            case '-':
                                    con=-s4.pop()+s4.pop();
                                    s4.push(con);    
                            break;
                            case '*':
                                    con=s4.pop()*s4.pop();
                                    s4.push(con);  
                            break;
                            case '/':
                                    con1=s4.pop();
                                    con=s4.pop()/con1;
                                    s4.push(con);
                            break;
                            case '^':
                                    con1=s4.pop();
                                    con=(int)Math.pow(s4.pop(),con1);
                                    s4.push(con);   
                            break;
                            }
                        }catch(Exception ex)    
                        {
                            ex.printStackTrace();
                        }        
                    }
                    p=s3.pop();
                    temp=p;
                }
                else
                {
                    p=p.rchild;
                    flag=0;
                }
            }   
            if(s3.empty())
                break;
        }
        return s4.pop();
    }
    
    public TreeNode MadeExpr(String oo,TreeNode T,TreeNode T1)
    {
        TreeNode T2=new TreeNode();

        T2.data=oo;
        T2.lchild=T;
        T2.rchild=T1;

        return T2;
    }
    
    public void MergeConst(TreeNode T)
    {
        TreeNode p;
        Stack<TreeNode> s = new Stack<TreeNode>();
        
        p=T;
        while(p!=null||!s.empty())
        {
            if(p!=null){s.push(p);p=p.lchild;}
            else
            {
                p=s.pop();
                if(prior[p.data.charAt(0)]>0&&Character.isDigit(p.lchild.data.charAt(0))
                        &&Character.isDigit(p.rchild.data.charAt(0)))
                {
                    switch(p.data.charAt(0))
                    {
                        case '+':
                            p.data = String.valueOf(Integer.parseInt(p.lchild.data) + Integer.parseInt(p.rchild.data));
                            p.lchild=null;
                            p.rchild=null;                                    
                        break;
                        case '-':
                            p.data = String.valueOf(Integer.parseInt(p.lchild.data) - Integer.parseInt(p.rchild.data));
                            p.lchild=null;
                            p.rchild=null;
                        break;
                        case '*':
                            p.data = String.valueOf(Integer.parseInt(p.lchild.data) * Integer.parseInt(p.rchild.data));
                            p.lchild=null;
                            p.rchild=null;
                        break;
                        case '/':
                            if(Integer.parseInt(p.rchild.data)==0)
                            {
                                System.out.println("Operation Error! Can't MergeConst!");
                            }
                            else
                            {
                                p.data=String.valueOf(Integer.parseInt(p.lchild.data) / Integer.parseInt(p.rchild.data));                              
                                p.lchild=null;
                                p.rchild=null;
                            }
                        break;
                        case '^':
                            p.data = String.valueOf((int)Math.pow(Integer.parseInt(p.lchild.data),Integer.parseInt(p.rchild.data)));
                            p.lchild=null;
                            p.rchild=null;
                        break;    
                    }        
                }    
                p=p.rchild;    
            }    
        }            
    }        

    public void PrintTree(TreeNode T,int j)
    {
        int i;
        if(T.lchild!=null)
            PrintTree(T.rchild,j+1);
        for(i=1;i<=j;i++)
            System.out.print("  ");
        System.out.println(T.data);
        if(T.rchild!=null)
            PrintTree(T.lchild,j+1);
    }

    public void PreVisit(TreeNode T)
    {
        if(T!=null)
        {
            System.out.print(T.data);
            PreVisit(T.lchild);
            PreVisit(T.rchild);
        }   
        return;
    }

    public void LastVisit(TreeNode T)
    {
        if(T!=null)
        {
            LastVisit(T.lchild);
            LastVisit(T.rchild);
            System.out.print(T.data);
        }
        return;
    }

    public void MidVisit(TreeNode T)
    {
        if(T!=null)
        {
            MidVisit(T.lchild);
            System.out.print(T.data);
            MidVisit(T.rchild);
        }
        return;
    }
            
    public static void main(String[] args) {
        // TODO code application logic here
        Scanner scan = new Scanner(System.in);
        Scanner scan1;
        String E,E1,oo;
        OperateTree tree = new OperateTree();
        TreeNode T,T1,T2;
        System.out.println("\nPlease enter a number:");
        E=scan.nextLine();
        scan1=new Scanner(E);
        T=tree.InputPreExpr(E, scan1);
        tree.MergeConst(T);
        tree.LastVisit(T);
        System.out.println();
        tree.OutputExpr(T);
        System.out.println("\nPlease enter another number:");
        E1=scan.nextLine();
        T1=tree.PostExpr(E1);
        tree.MergeConst(T1);
        tree.OutputExpr(T1);
        System.out.println();
        tree.LastVisit(T1);
        System.out.println();        
        System.out.println("\nPlease enter the operator:");
        oo=scan.nextLine();
        T2=tree.MadeExpr(oo, T, T1);
        tree.OutputExpr(T2);
        System.out.println();
        tree.PrintTree(T2, 0);
    }

}