逆波兰式计算字符串公式

  1 package t201401;
  2 
  3 import java.util.ArrayList;
  4 import java.util.HashMap;
  5 import java.util.List;
  6 import java.util.Map;
  7 import java.util.Stack;
  8 
  9 public class T1502 {
 10     
 11     /**
 12      * 优先级比较
 13      * @param operator1 比较值
 14      * @param operator2 被比较值
 15      * @return 小于等于返回false,大于返回true
 16      */
 17     static boolean comparePrior(String operator1, String operator2) {
 18         if("(".equals(operator2)) {
 19             return true;
 20         }
 21         if ("*".equals(operator1) || "/".equals(operator1)) {
 22             if ("+".equals(operator2) || "-".equals(operator2)) {
 23                 return true;
 24             }
 25         }
 26         return false;
 27     }
 28 
 29     /**
 30      * 转为后缀表达式:
 31      * 1、如果是"("直接压入stack栈。
 32       * 2、如果是")"，依次从stack栈弹出运算符加到数组newExpressionStrs的末尾，知道遇到"("；
 33       * 3、如果是非括号，比较扫描到的运算符，和stack栈顶的运算符。如果扫描到的运算符优先级高于栈顶运算符则，把运算符压入栈。否则的话，就依次把栈中运算符弹出加到数组newExpressionStrs的末尾，直到遇到优先级低于扫描到的运算符或栈空，并且把扫描到的运算符压入栈中。就这样依次扫描，知道结束为止。如果扫描结束，栈中还有元素，则依次弹出加到数组newExpressionStrs的末尾，就得到了后缀表达式。
 34      * @param expressionStrs
 35      * @return
 36      */
 37     static String[] toSuffixExpression(String[] expressionStrs) {
 38         //新组成的表达式
 39         List<String> newExpressionStrs = new ArrayList<String>();
 40         Stack<String> stack = new Stack<String>();
 41         for (int i = 0; i < expressionStrs.length; i++) {
 42             if ("(".equals(expressionStrs[i])) { // 如果是左括号,则入栈
 43                 stack.push(expressionStrs[i]);
 44             } else if ("+".equals(expressionStrs[i]) || "-".equals(expressionStrs[i]) || "*".equals(expressionStrs[i]) || "/".equals(expressionStrs[i])) {
 45                 if (!stack.empty()) { // 取出先入栈的运算符
 46                     String s = stack.pop();
 47                     if(comparePrior(expressionStrs[i], s)) { //如果栈值优先级小于要入栈的值,则继续压入栈
 48                         stack.push(s);
 49                     } else {  //否则取出值
 50                         newExpressionStrs.add(s);
 51                     }
 52                 }
 53                 stack.push(expressionStrs[i]);
 54             } else if (")".equals(expressionStrs[i])) { //如果是")",则出栈,一直到遇到"("
 55                 while (!stack.empty()) {
 56                     String s = stack.pop();
 57                     if (!"(".equals(s)) {
 58                         newExpressionStrs.add(s);
 59                     } else {
 60                         break;
 61                     }
 62                 }
 63             } else {
 64                 newExpressionStrs.add(expressionStrs[i]);
 65             }
 66         }
 67         while (!stack.empty()) {
 68             String s = stack.pop();
 69             newExpressionStrs.add(s);
 70         }
 71         return newExpressionStrs.toArray(new String[0]);
 72     }
 73 
 74     public static void main(String[] args) {
 75         
 76         //要用的字符串表达式
 77         String expressionStr = "a+b/(a+a)+c";
 78         Map<String,Double> map = new HashMap<String,Double>();
 79         map.put("a", 1.0);
 80         map.put("b", 2.0);
 81         map.put("c", 3.0);
 82         
 83         
 84         // 分割成表达式数组
 85         String[] strs = expressionStr.split("");
 86         String[] newStrs = toSuffixExpression(strs);
 87         Stack<Double> stack = new Stack<Double>();
 88         Double cache;
 89         for (int i = 0; i < newStrs.length; i++) {
 90             if ("*".equals(newStrs[i])){
 91                 stack.push(stack.pop()*stack.pop());
 92             }else if("/".equals(newStrs[i])){
 93                 cache = stack.pop();
 94                 stack.push(stack.pop()/cache);
 95             }else if("+".equals(newStrs[i])){
 96                 stack.push(stack.pop()+stack.pop());
 97             }else if("-".equals(newStrs[i])){
 98                 cache = stack.pop();
 99                 stack.push(stack.pop()-cache);
100             }else{
101                 stack.push(map.get(newStrs[i]));
102             }
103         }
104         
105         System.out.println(stack.pop());
106     }
107 
108 }