(JAVA)(資料結構)中序式轉後序式(轉回中序式)

1. /* 
2.  *  
3.  * 中序式轉後序式 
4.  *  
5.  *  
6.  */  
7. public class InFixToPosfix {  
8.  static int priority(char op){ //順序   *,/ > +,-   
9.   if(op == '+' || op == '-')  
10.    return 1 ;  
11.   else if(op == '*' || op == '/')  
12.    return 2 ;  
13.   else  
14.    return 0 ;  
15.  }  
16.    
17.  public static void main(String[] args){  
18.   String infix = "(A+B)*D+E/(F+A*D)+C";  
19.   //a+b*d+c/d , (A+B)*D+E/(F+A*D)+C  
20.   System.out.println("後序式為 :" +ToPosfix(infix.toCharArray()));  
21.   String Posfix = ToPosfix(infix.toCharArray());  
22.   System.out.println("中序式為 :" +ToInFix(Posfix.toCharArray()));  
23.     
24.  }  
25.    
26.  static String ToPosfix(char[] infix){  
27.   char[] stack = new char[infix.length]; //堆疊  
28.   StringBuffer Posfix = new StringBuffer(); //輸出:後序式  
29.   char[] Infix = infix;  
30.   int top =   0;   
31.   for(char op : Infix){  
32.    if(op == '+'|| op == '-'||op == '*' || op == '/'){  
33.     while( priority(stack[top]) >=  priority(op)){  
34.      Posfix.append(stack[top]);  
35.      top--;  
36.     }  
37.     if(top  <  stack.length){  
38.            top++ ;    
39.         stack[top] = op;  
40.         }  
41.       
42.    }else if(op == '('){  
43.     if(top  <  stack.length ){  
44.         top++ ;    
45.      stack[top] = op;  
46.      }  
47.    }else if(op == ')'){  
48.     while(stack[top] != '('){  
49.      Posfix.append(stack[top]);  
50.      top--;  
51.     }  
52.     top--;// ( 不輸出  
53.    }else{  
54.     Posfix.append(op) ;  
55.    }  
56.   }  
57.     while(top > 0){  
58.      Posfix.append(stack[top]);  
59.         top--;  
60.     }  
61.   return Posfix.toString();  
62.     
63.  }  
64.     static String ToInFix(char[] posfix){  
65.  String[] stack = new String[posfix.length]; //運算式堆疊  
66.  StringBuffer InFix = new StringBuffer(); //輸出:中序式  
67.  char[] Posfix = posfix;  
68.   
69.   int top = 0;   
70.  for(char op : posfix){  // stack 1 + op + stack 2  
71.   if(op == '+'|| op == '-'||op == '*' || op == '/'){  
72.      String s = stack[top] ;  
73.      stack[top] = null ;  
74.      String s2 = stack[--top] ;  
75.     if(op == '+'|| op == '-')  
76.      stack[top] = "("+s2+op+s+")";  
77.     else  
78.      stack[top] = s2+op+s;    
79.   }else{  
80.    top++;  
81.    stack[top] =String.valueOf(op) ;  
82.      
83.   }  
84.      
85.  }  
86.  for(String s : stack){  
87.   if(s != null)  
88.    InFix.append(s);  
89.   }  
90.  return InFix.toString();  
91.  }  
92. }