Java实现字符串表达式求值
需求说明
最近在用java写一个计算器，遇到了一个问题，获取用户输入的需要计算的表达式，因为是字符串的形式所以无法进行直接计算，所以需要写一些算法来对字符串表达式进行求值。
实现
JS实现
相信大家应该都知道JavaScript，JavaScript里面有个函数eval()可以计算某个字符串，并执行其中的JavaScript代码。虽然JavaScript名字里面有个Java，但是JavaScript和Java没什么联系的，那我上面说的这些有什么用呢？
在JDK1.6中，我们可以使用内置的JavaScript引擎，意味着我们可以使用JavavScript里面的eval()函数。
import javax.script.ScriptEngine;
import javax.script.ScriptEngineManager;
import javax.script.ScriptException;
public class OperationJS {
public static void main(String[] args) throws ScriptException {
ScriptEngineManager mgr = new ScriptEngineManager();
ScriptEngine engine = mgr.getEngineByName("JavaScript");
String foo = "(40+2)*2";
System.out.println(engine.eval(foo));
}
}
使用这个要注意一个安全问题，执行的JavaScript可以访问所有Java类，因此可以无限制地劫持您的应用程序。
例如下面这句代码，将通过JavaScript将文件写入（默认情况下）程序的当前目录
engine.eval("var f = new java.io.FileWriter('hello.txt'); f.write('hello!'); f.close();");
发现这个有点方便。秉着学习的原则，出现了实现二，用算法来解决。
栈实现
基本分析
- 表达式主要有括号和加减乘除四种基本运算。表达式可以看成是由一个个二元运算组成，前一个二元运算可以作为后一个二元运算的输入。
例如：“1+2+3”，可以看成是两个二元运算组成(1+2)+3，前一个二元运算过后就变成3+3，这又是一个二元运算，最后结果为6。既然都是二元运算计算，我们就可以用同一段程序来解决，递归或循环。但是我们要注意加减乘除有优先级之分。 - 加减乘除四种运算符是有优先级的，乘法或除法同级，且比加法或减法优先级高。优先级的出现对程序的设计影响很大，例如：”1+2+3-4“=“3+3-4”=“6-4”=2，如果整个表达式都是同级的我们就可以直接从头一直运算到尾。但是因为有优先级的出现我们就不可以这样做，例如：“1+2*3-4”=“1+6-4”=“3”,我们需要先算在表达式中间的”2*3“，而不能从头的"1+2"开始算。优先级的出现让程序变的复杂了起来。
- 括号的处理，括号就相当于在表达式里面嵌套了一个子表达式，而子表达式的优先级比括号外的其他运算优先级高。
分析可得，表达式有两个基本元素，操作数和运算符。
算法思想
- 操作数栈：解析表达式，采用逐个读取字符的形式，如果是操作数就入操作数栈，需要注意的是，我们是逐个读取字符，也就意味着数字"123"将分3次读取(“1”,“2”,“3”)，所以需要一个追加器将字符缓存起来，当完整的读取了整个数值时在入操作数栈。
- 运算符栈：如果是运算符就进行比较，优先级同级或低于栈顶运算符时，将触发一次二元运算，进行二元运算的为运算符栈的栈顶元素和操作数栈顶的两个元素，再把运算得到的结果入操作数栈。如果运算栈还有元素，这是一个递归操作，直到运算栈没有元素或者运算符的优先级高于栈顶元素，那么把运算符入运算符栈。继续读取表达式的下一个元素。
例如：”1+2*3-4“。
如下图所示，(6)在读取"-“时，优先级低于栈顶运算符”"，触发二元运算，取出操作数栈顶元素"3"和"2"与运算符栈顶元素"“进行一次二元运算"2*3”=“6”，得到结果"6"，把运算出来的结果"6"入操作数栈(6.1所示)。栈顶还有元素，继续比较，栈顶元素”+“和"-“同级，再触发二元运算，取出操作数栈顶元素"6"和"1"与运算符栈顶元素”+“进行一次二元运算"1+6”=“7”，得到结果"7"，把运算出来的结果"7"入操作数栈(6.2所示)。此时运算符栈没有元素，运算符"-“入运算符栈(6.3所示)。读取下一个字符"4”，表达式已读取完毕，此时进行二元运算，直到运算符栈没有运算符，此时操作栈唯一的元素就是最后表达式计算的结果"3"(8所示)。
- 括号运算：相当于子表达式运算，当读取表达式字符时，读取到"(“左括号，将左括号入运算符栈，当读取到”)"右括号时，将一直运算整个子表达式的二元运算，直到遇到左括号时停止，此时把子表达式的结果入操作数栈。加减乘除左括号右括号中左括号的优先级最低，右括号的优先级最高。
例如：“1+2*(3+4)”
代码实现
import java.math.BigDecimal;
import java.util.HashMap;
import java.util.Map;
import java.util.Stack;
/**
* 对表达式求值，支持加减乘除括号小数点，不支持负数
*/
public class Operation {
//优先级Map
private static final Map<String,Integer> OP_PRIORITY_MAP=new HashMap<String, Integer>(){
{
put("(",0);
put("+",3);
put("-",3);
put("*",4);
put("/",4);
put(")",10);
}
};
public double operationExpression(String expression){
Stack<String> opStack = new Stack<String>(); //运算符栈
Stack<BigDecimal> numStack = new Stack<BigDecimal>(); //操作数栈
StringBuilder numBuilder = new StringBuilder(); //当前数值的追加器
for (int i = 0;i < expression.length();i++){
char c = expression.charAt(i);
if (c >= '0' && c <= '9' || c == '.'){ //如果是数值则加入追加器
numBuilder.append(c);
}else{ //如果是运算符
if (numBuilder.length() > 0){ //如果numBuilder有值说明里面已经有一个数值
numStack.push(new BigDecimal(numBuilder.toString())); //把数值入运算符栈
numBuilder.delete(0,numBuilder.length()); //清空数值
}
//读取到的字符是运算符
String op = String.valueOf(c);
if (opStack.empty()){ //如果操作数栈没有运算符
opStack.push(op);
}else{
//如果是"("则直接入运算栈
if ("(".equals(op)){
opStack.push(op);
}else if (")".equals(op)){
//如果是")"则进行括号匹配运算括号内的表达式
while (!"(".equals(opStack.peek())){
stackOperation(opStack,numStack);
}
opStack.pop();
}else{
//如果是运算符，需要对比当前运算符op和栈顶的运算符优先级。
do {
//比较当前运算符和栈顶运算符的优先级,如果nowOp和opStack栈顶元素相同或者低级，
// 则进行运算，直到nowOp高于opStack栈顶
if (jubgmentPriority(op,opStack.peek())){
stackOperation(opStack,numStack);
if (opStack.empty()){
opStack.push(op);
break;
}
}else {
opStack.push(op);
break;
}
}while (!opStack.empty());
}
}
}
}
//表达式结束，追加器里面有值
if (numBuilder.length()>0){
numStack.push(new BigDecimal(numBuilder.toString()));
}
while (!opStack.empty()){
stackOperation(opStack,numStack);
}
return numStack.pop().doubleValue();
}
/**
* 进行一次二元运算
* @param opStack
* @param numStack
*/
public void stackOperation(Stack<String> opStack,Stack<BigDecimal> numStack){
String opT = opStack.pop(); //栈顶运算符
BigDecimal num2 = numStack.pop(); //第二个操作数
BigDecimal num1 = numStack.pop(); //第一个操作数
BigDecimal operationNum = oneOperation(opT,num1,num2); //num1 op num2
numStack.push(operationNum); //把计算完的结果放入操作数栈
}
//
/**
* 单次计算，计算为num1 op num2
* @param op 运算符
* @param num1 第一个操作数
* @param num2 第二个操作数
* @return num1 op num2
*/
public BigDecimal oneOperation(String op,BigDecimal num1,BigDecimal num2){
BigDecimal result = new BigDecimal(0);
switch (op){
case "+":
result = num1.add(num2);
break;
case "-":
result = num1.subtract(num2);
break;
case "*":
result = num1.multiply(num2);
break;
case "/":
result = num1.divide(num2);
break;
default:
break;
}
return result;
}
/**
* 比较运算符优先级
* @param op1
* @param op2
* @return op1比op2相同或低级则返回true，op1比op2高级则返回false
*/
private boolean jubgmentPriority(String op1, String op2){
return (OP_PRIORITY_MAP.get(op1) - OP_PRIORITY_MAP.get(op2)) <= 0;
}
public static void main(String[] args) {
Operation operation = new Operation();
System.out.println(operation.operationExpression("(2+2)*3+3+3/3+2.2"));
}