前些天，在项目里面在做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();
}
}