计算表达式算法

import java.util.ArrayList;
import java.util.Stack;
 
 
public class PostfixExp {
  
   public static void main(String[] args) {
      PostfixExp pExp = new PostfixExp();
     
      //String exp = "a + b*c + (d * e + f) * g";
      //string exp = "1+1+3*2*3-4";
      //string exp = "2+(1+3)*2*3-4";
      //string exp = "2+1+3*2*(3-4)";
      String exp = "(13+10/2)*21*(39-4)";
      String case1 = "(13+10/2)*(21*(39-4)+(13+10/2)*21*(39-4))";
      String case2 = "(6*7+9+8/2*12+12/3)+88/11";
      String case3 = "(6*7+9+8/2*12+12/3)+(88/11+(13+10/2)*(21*(39-4)+(13+10/2)*21*(39-4)))";
      String case4 = "(6*7+9+8/2*12+12/3)+((88/11+(13+10/2)*(21*(39-4)+(13+10/2)*21*(39-4)))+(6*7+9+8/2*12+12/3)+(88/11+(13+10/2)*(21*(39-4)+(13+10/2)*21*(39-4))))";
      String case5 = "(6*7+9+8/2*12+12/3)+((88/11+(13+10/2)*(21*(39-4)+(13+10/2)*21*(39-4)))+(6*7+9+8/2*12+12/3)+(88/11+(13+10/2)*(21*(39-4)+(13+10/2)*21*(39-4))))+(6*7+9+8/2*12+12/3)+((88/11+(13+10/2)*(21*(39-4)+(13+10/2)*21*(39-4)))+(6*7+9+8/2*12+12/3)+(88/11+(13+10/2)*(21*(39-4)+(13+10/2)*21*(39-4))))";
      String case6 = "(3*(4+9)+8/(2*12)+12/3)+(((7+(13+10/2))*(21*(39-4)+(13+10/2)*21*(39-4)))+(6*7+9+8/2*12+12/3)+(88/11+(13+10/2)*(21*(39-4)+(13+10/2)*21*(39-4))))+(6*7+9+8/2*12+12/3)+((88/11+(13+10/2)*(21*(39-4)+(13+10/2)*21*(39-4)))+(6*7+9+8/2*12+12/3)+(88/11+(13+10/2)*(21*(39-4)+(13+10/2)*21*(39-4))))";
 
      ArrayList<String> expList = pExp.change2PostfixExp(case6);
      for(String item : expList) {
         System.out.print(item + " ");
      }
      System.out.println("\n");
      System.out.println("My answer is \t\t" + pExp.calculate(expList));
     
      int rightAnswer = (3*(4+9)+8/(2*12)+12/3)+(((7+(13+10/2))*(21*(39-4)+(13+10/2)*21*(39-4)))+(6*7+9+8/2*12+12/3)+(88/11+(13+10/2)*(21*(39-4)+(13+10/2)*21*(39-4))))+(6*7+9+8/2*12+12/3)+((88/11+(13+10/2)*(21*(39-4)+(13+10/2)*21*(39-4)))+(6*7+9+8/2*12+12/3)+(88/11+(13+10/2)*(21*(39-4)+(13+10/2)*21*(39-4))));
      System.out.println("The right answer is \t" + rightAnswer);
     
      System.out.println();
   }
  
   private Stack<String> opStack;
   private Stack<String> expStack;
   private String[] ops = {"+", "-", "*", "/", "(", ")", "#"};
  
   public PostfixExp() {
      opStack = new Stack<String>();
      expStack = new Stack<String>();
   }
  
   private boolean isOp(char c) {
      String cStr = Character.toString(c);
     
      for (String op : ops) {
         if(cStr.equals(op)) {
            return true;
         }
      }
     
      return false;
   }
  
   private boolean isOp(String str) {
      for(String op : ops) {
         if(str.equals(op)) {
            return true;
         }
      }
     
      return false;
   }
  
   private int getOpPriority(String op){
      if("+".equals(op) || "-".equals(op)) {
         return 1;
      }
      else if("*".equals(op) || "/".equals(op)) {
         return 2;
      }
      else if("(".equals(op)) {
         return 3;
      }
      else if("#".equals(op)) {
         return 0;
      }
     
      return Integer.MAX_VALUE;
   }
  
   public String[] getItems(String str) {
      ArrayList<String> list = new ArrayList<String>();
     
      // Remove all blank spaces.
      str = str.replaceAll("\\s", "");
     
      int i = 0;
      StringBuilder sBuilder = new StringBuilder();
      while(i < str.length()) {
         if(i == str.length() - 1) {
            sBuilder.append(
                   Character.toString(str.charAt(i)));
            list.add(sBuilder.toString());
         }
        
         if(!isOp(str.charAt(i))) {
            sBuilder.append(
                Character.toString(str.charAt(i)));
           
         }
         else {
            if(sBuilder.length() > 0) {
                list.add(sBuilder.toString());
                sBuilder.delete(0, sBuilder.length());
            }
            list.add(Character.toString(str.charAt(i)));
         }
        
         ++i;
      }
 
      list.add("#");
 
      String[] result = new String[list.size()];
      return list.toArray(result);
   }
  
   public ArrayList<String> change2PostfixExp(String normalExp) {
      ArrayList<String> expList = new ArrayList<String>();
      String[] items = getItems(normalExp);
     
      opStack.clear();
      expStack.clear();
     
      opStack.push("#");
     
      int i = 0;
      while(i < items.length) {
         //System.out.println(i + ":" + items[i]);
         if(!isOp(items[i])) {
            expList.add(items[i]);
         }
         else {
            if(items[i].equals(")")){
                while(!opStack.isEmpty() && !opStack.peek().equals("(")) {
                   expList.add(opStack.pop());
                }
               
                if(!opStack.isEmpty() && opStack.peek().equals("(")) {
                   opStack.pop();
                }
                ++i;
                continue;
            }
           
            if(items[i].equals("#")) {
                while(!opStack.isEmpty() && !opStack.peek().equals("#")) {
                   expList.add(opStack.pop());
                }
                break;
            }
           
            if(!opStack.isEmpty()) {
                while(!opStack.isEmpty()
                      && (getOpPriority(opStack.peek()) >= getOpPriority(items[i])
                      && !opStack.peek().equals("("))
                ) {
                   expList.add(opStack.pop());
                }
                opStack.push(items[i]);
            }
         }
        
         ++i;
      }
     
      return expList;
   }
  
   public double calculate(ArrayList<String> postfixExp) {
      Stack<Double> calcStack = new Stack<Double>();
     
      int i = 0;
      String ite = null;
      double result = Double.MAX_VALUE;
     
      while(i < postfixExp.size()) {
         ite = postfixExp.get(i);
         if(!isOp(postfixExp.get(i))) {
            calcStack.push(new Double(
                         Double.parseDouble(
                               postfixExp.get(i))
            ));
         }
         else {
            double num2 = calcStack.peek();
            calcStack.pop();
            if(!calcStack.isEmpty()) {
                double num1 = calcStack.peek();
                calcStack.pop();
               
                if("*".equals(ite)) {
                   result = num1 * num2;
                }
                else if("+".equals(ite)) {
                   result = num1 + num2;
                }
                else if("-".equals(ite)) {
                   result = num1 - num2;
                }
                else if("/".equals(ite)) {
                   result = num1 / num2;
                }
                System.out.println(num1 + "\t" + ite + "\t" + num2 + " = " + result);
                calcStack.push(result);
            }
         }
         ++i;
      }
     
      return result;
   }
}