大魚

前些天，在項目里面在做OLAP模塊，其中一個自定義配置部分，里面需要用到根據配置的四則運算公式（字符串型），計算公式的結果。

于是在網上搜索了一番，終于有所啟發。但是也感慨網上很多的例子并不完整，讓我冒著訪問惡意網頁的風險，四處瀏覽。遂將我自己的實現寫在這里，供大家參考討論。

此實現方法主要是參考了機械工業出版社出版的《數據結構、算法與應用——C++語言描述》（2000年1月出版）當中，第5章——堆棧，第169頁，5.5應用——5.5.1括號匹配的例子，使用Java編寫完成。

JVM版本為JDK6 Update1.

因為在處理四則運算的時候最麻煩的邏輯主要是對括號內預算的處理，特別是括號的嵌套。

因此該算法主要的邏輯是，通過對括號位置的觀察，得出：從左至右的掃描一個字符串，那么每一個右括號將與最近遇到的那個未匹配的左括號相匹配。這和堆棧的后進先出的規則是一樣的。因此得到在掃描的過程當中，將每一個遇到的左括號進行壓棧，在出現右括號的時候，出棧。

該解法相對于通過遞歸實現的解法，在時間復雜性上略好，并且實現出來的代碼更加清晰。

以下為具體實現的代碼：

package azurecube.common;

import java.util.LinkedList;
import java.util.ArrayList;

public class FormulaCalculator {
 private boolean isRightFormat = true;
 
 public double getResult(String formula){
  double returnValue = 0;
  try{
   returnValue = doAnalysis(formula);
  }catch(NumberFormatException nfe){
   System.out.println("公式格式有誤，請檢查:" + formula);
  }catch(Exception e){
   e.printStackTrace();
  }
  if(!isRightFormat){
   System.out.println("公式格式有誤，請檢查:" + formula);
  }
  return returnValue;
 }

 private double doAnalysis(String formula){
  double returnValue = 0;
  LinkedList<Integer> stack = new LinkedList<Integer>();
  
  int curPos = 0;
  String beforePart = "";
  String afterPart = "";
  String calculator = "";
  isRightFormat = true;
  while(isRightFormat&&(formula.indexOf('(') >= 0||formula.indexOf(')') >= 0)){
   curPos = 0;
   for(char s : formula.toCharArray()){
    if(s == '('){
     stack.add(curPos);
    }else if(s == ')'){
     if(stack.size() > 0){
      beforePart = formula.substring(0, stack.getLast());
      afterPart = formula.substring(curPos + 1);
      calculator = formula.substring(stack.getLast() + 1, curPos);
      formula = beforePart + doCalculation(calculator) + afterPart;
      stack.clear();
      break;
     }else{
      System.out.println("有未關閉的右括號！");
      isRightFormat = false;
     }
    }
    curPos++;
   }
   if(stack.size() > 0){
    System.out.println("有未關閉的左括號！");
    break;
   }
  }
  if(isRightFormat){
   returnValue = doCalculation(formula);
  }
  return returnValue;
 }

 private double doCalculation(String formula) {
  ArrayList<Double> values = new ArrayList<Double>();
  ArrayList<String> operators = new ArrayList<String>();

  int curPos = 0;
  int prePos = 0;
  for (char s : formula.toCharArray()) {
   if (s == '+' || s == '-' || s == '*' || s == '/') {
    values.add(Double.parseDouble(formula.substring(prePos, curPos)
      .trim()));
    operators.add("" + s);
    prePos = curPos + 1;
   }
   curPos++;
  }
  values.add(Double.parseDouble(formula.substring(prePos).trim()));

  char op;
  for (curPos = operators.size() - 1; curPos >= 0; curPos--) {
   op = operators.get(curPos).charAt(0);
   switch (op) {
   case '*':
    values.add(curPos, values.get(curPos) * values.get(curPos + 1));
    values.remove(curPos + 1);
    values.remove(curPos + 1);
    operators.remove(curPos);
    break;
   case '/':
    values.add(curPos, values.get(curPos) / values.get(curPos + 1));
    values.remove(curPos + 1);
    values.remove(curPos + 1);
    operators.remove(curPos);
    break;
   }
  }

  for (curPos = operators.size() - 1; curPos >= 0; curPos--) {
   op = operators.get(curPos).charAt(0);
   switch (op) {
   case '+':
    values.add(curPos, values.get(curPos) + values.get(curPos + 1));
    values.remove(curPos + 1);
    values.remove(curPos + 1);
    operators.remove(curPos);
    break;
   case '-':
    values.add(curPos, values.get(curPos) - values.get(curPos + 1));
    values.remove(curPos + 1);
    values.remove(curPos + 1);
    operators.remove(curPos);
    break;
   }
  }

  return values.get(0).doubleValue();
 }
}