前些天，在項目里面在做OLAP模塊，其中一個自定義配置部分，里面需要用到根據(jù)配置的四則運算公式（字符串型），計算公式的結果。
于是在網(wǎng)上搜索了一番，終于有所啟發(fā)。但是也感慨網(wǎng)上很多的例子并不完整，讓我冒著訪問惡意網(wǎng)頁的風險，四處瀏覽。遂將我自己的實現(xiàn)寫在這里，供大家參考討論。
此實現(xiàn)方法主要是參考了機械工業(yè)出版社出版的《數(shù)據(jù)結構、算法與應用——C++語言描述》（2000年1月出版）當中，第5章——堆棧，第169頁，5.5應用——5.5.1括號匹配的例子，使用Java編寫完成。
JVM版本為JDK6 Update1.
因為在處理四則運算的時候最麻煩的邏輯主要是對括號內(nèi)預算的處理，特別是括號的嵌套。
因此該算法主要的邏輯是，通過對括號位置的觀察，得出：從左至右的掃描一個字符串，那么每一個右括號將與最近遇到的那個未匹配的左括號相匹配。這和堆棧的后進先出的規(guī)則是一樣的。因此得到在掃描的過程當中，將每一個遇到的左括號進行壓棧，在出現(xiàn)右括號的時候，出棧。
該解法相對于通過遞歸實現(xiàn)的解法，在時間復雜性上略好，并且實現(xiàn)出來的代碼更加清晰。
以下為具體實現(xiàn)的代碼：
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();
}
}