package expression1;     
 import java.util.*;     
 //棧類     
  public class Stacks{     
    private LinkedList list=new LinkedList();     
    int top=-1;     
     public void push(Object value){     
       top++;     
       list.addFirst(value);     
    }     
     public Object pop(){     
       Object temp=list.getFirst();     
       top--;     
       list.removeFirst();     
       return temp;     
    
    }     
     public Object top(){     
    return list.getFirst();     
    }     
 }     
 
 
 
 
 package expression1;    
    
 import java.io.*;    
 import java.util.*;    
    
  public class Expression {    
     private ArrayList expression = new ArrayList();// 存儲中序表達式    
    
     private ArrayList right = new ArrayList();// 存儲右序表達式    
    
     private String result;// 結果    
    
     // 依據輸入信息創建對象，將數值與操作符放入ArrayList中    
      private Expression(String input) {    
         StringTokenizer st = new StringTokenizer(input, "+-*/()", true);    
          while (st.hasMoreElements()) { 
             String s=st.nextToken();
             expression.add(s);
         }
     }
    
     // 將中序表達式轉換為右序表達式
      private void toRight() { 
         Stacks aStack = new Stacks();  
         String operator;
         int position = 0;
          while (true) {
              if (Calculate.isOperator((String) expression.get(position))) {    
                 if (aStack.top == -1   
                          || ((String) expression.get(position)).equals("(")) {    
                     aStack.push(expression.get(position));    
                  } else {    
                      if (((String) expression.get(position)).equals(")")) {  
                          while(true){
                         
                              if (aStack.top != -1&&!((String) aStack.top()).equals("(")) {    
                                 operator = (String) aStack.pop();
                                 right.add(operator);    
                              }else{
                                 if(aStack.top != -1)
                                     aStack.pop();
                                 break;
                             }   
                         } 
                      } else {  
                          while(true){
                             if (aStack.top != -1&&Calculate.priority((String) expression    
                                     .get(position)) <= Calculate    
                                     .priority((String) aStack.top())    
                                      ) {    
                                 operator = (String) aStack.pop(); 
                                 if (!operator.equals("("))    
                                     right.add(operator);    
                              }else{
                                 break;
                             }    
                             
                         } 
                         aStack.push(expression.get(position));
                     }    
                 }    
             } else   
                 right.add(expression.get(position));    
             position++;    
             if (position >= expression.size())    
                 break;    
         }    
          while (aStack.top != -1) {    
             operator = (String) aStack.pop();  
             if(!operator.equals("("))  
                 right.add(operator);    
         }    
     }    
    
     // 對右序表達式進行求值    
      private void getResult() {    
         this.toRight();
          for(int i=0;i<right.size();i++){
             System.out.println(right.get(i));  
         }    
         Stacks aStack = new Stacks();    
         String op1, op2, is = null;    
         Iterator it = right.iterator();    
    
          while (it.hasNext()) {    
             is = (String) it.next();    
              if (Calculate.isOperator(is)) {    
                 op1 = (String) aStack.pop();    
                 op2 = (String) aStack.pop();    
                 aStack.push(Calculate.twoResult(is, op1, op2));    
             } else   
                 aStack.push(is);    
         }    
         result = (String) aStack.pop();    
         it = expression.iterator();    
          while (it.hasNext()) {    
             System.out.print((String) it.next());    
         }    
         System.out.println("=" + result);    
     }    
    
      public static void main(String avg[]) {    
          try {    
             System.out.println("Input a expression:");    
             BufferedReader is = new BufferedReader(new InputStreamReader(    
                     System.in));    
              for (;;) {    
                 String input = new String();    
                 input = is.readLine().trim();    
                 if (input.equals("q"))    
                     break;    
                  else {    
                     Expression boya = new Expression(input);    
                     boya.getResult();    
                 }    
                 System.out    
                         .println("Input another expression or input 'q' to quit:");    
             }    
             is.close();    
          } catch (IOException e) {    
             System.out.println("Wrong input!!!");    
         }    
     }    
 }    
 
 
 
 ackage expression1;    
    
  public class Calculate {    
     // 判斷是否為操作符號    
      public static boolean isOperator(String operator) {    
         if (operator.equals("+") || operator.equals("-")    
                 || operator.equals("*") || operator.equals("/")    
                 || operator.equals("(") || operator.equals(")"))    
             return true;    
         else   
             return false;    
     }    
    
     // 設置操作符號的優先級別    
      public static int priority(String operator) {    
         if (operator.equals("+") || operator.equals("-"))    
             return 1;  
         else if (operator.equals("*") || operator.equals("/"))    
             return 2;    
         else   
             return 0;    
     }    
    
     // 做2值之間的計算    
      public static String twoResult(String operator, String a, String b) {    
          try {    
             String op = operator;    
             String rs = new String();    
             double x = Double.parseDouble(b);    
             double y = Double.parseDouble(a);    
             double z = 0;    
             if (op.equals("+"))    
                 z = x + y;    
             else if (op.equals("-"))    
                 z = x - y;    
             else if (op.equals("*"))    
                 z = x * y;    
             else if (op.equals("/"))    
                 z = x / y;    
             else   
                 z = 0;    
             return rs + z;    
          } catch (NumberFormatException e) {    
             System.out.println("input has something wrong!");    
             return "Error";    
         }    
     }    
 }