这是最近在项目中的一个需求，已知a=3，求字符串"a<=2"的值，也就是应该返回false。这个问题可大可小，就我们的应用场景也就是用来让用户自定义变量区间，比如类似下面这样的规则：
a<=2 返回积分系数1.0
2<a<=5 返回积分系数1.1
a>5 返回积分系数1.2
如果用switch写死在代码中，以后要修改规则实在是很麻烦的事情，用户也希望能自己维护这样些区间值。于是我想就让用户自己输入这样的表达式和变量的值保存在数据库中，然后计算的时候由系统来解析表达式并求值。问题就归结到求值字符串型逻辑表达式。这个问题恰好是规则引擎的应用领域，可我们的系统已经上线蛮久了，从维护角度也不希望再引入新的开源工具，况且也就这么一个地方用到。如果是算术表达式（比如2+3之类）可以直接扔进数据库执行即可，逻辑表达式倒是可以通过调用脚本语言来eval，但是同样是考虑后期维护问题，也不想引入beanshell、groovy的脚本语言。所以，我就自己写了个parser用于求值。
基本原理就是维护两个栈：操作数栈和操作符号栈，解析和求值的过程就是入栈和出栈操作。首先使用ArrayList实现一个栈，很容易的事情：
然后看看ExpressionParser.java，原理已经列上，注释也有，使用了单例模式，就请自己看了：
a<=2 返回积分系数1.0
2<a<=5 返回积分系数1.1
a>5 返回积分系数1.2
如果用switch写死在代码中，以后要修改规则实在是很麻烦的事情，用户也希望能自己维护这样些区间值。于是我想就让用户自己输入这样的表达式和变量的值保存在数据库中，然后计算的时候由系统来解析表达式并求值。问题就归结到求值字符串型逻辑表达式。这个问题恰好是规则引擎的应用领域，可我们的系统已经上线蛮久了，从维护角度也不希望再引入新的开源工具，况且也就这么一个地方用到。如果是算术表达式（比如2+3之类）可以直接扔进数据库执行即可，逻辑表达式倒是可以通过调用脚本语言来eval，但是同样是考虑后期维护问题，也不想引入beanshell、groovy的脚本语言。所以，我就自己写了个parser用于求值。
基本原理就是维护两个栈：操作数栈和操作符号栈，解析和求值的过程就是入栈和出栈操作。首先使用ArrayList实现一个栈，很容易的事情：
class
Stack {
protected java.util.ArrayList pool = new java.util.ArrayList();
public Stack() {
}
public Stack( int n) {
pool.ensureCapacity(n);
}
public void clear() {
pool.clear();
}
public boolean isEmpty() {
return pool.isEmpty();
}
public int size() {
return pool.size();
}
public Object topEl() {
if (isEmpty())
throw new java.util.EmptyStackException();
return pool.get(pool.size() - 1 );
}
public Object pop() {
if (isEmpty())
throw new java.util.EmptyStackException();
return pool.remove(pool.size() - 1 );
}
public void push(Object el) {
pool.add(el);
}
public String toString() {
return pool.toString();
}
}
protected java.util.ArrayList pool = new java.util.ArrayList();
public Stack() {
}
public Stack( int n) {
pool.ensureCapacity(n);
}
public void clear() {
pool.clear();
}
public boolean isEmpty() {
return pool.isEmpty();
}
public int size() {
return pool.size();
}
public Object topEl() {
if (isEmpty())
throw new java.util.EmptyStackException();
return pool.get(pool.size() - 1 );
}
public Object pop() {
if (isEmpty())
throw new java.util.EmptyStackException();
return pool.remove(pool.size() - 1 );
}
public void push(Object el) {
pool.add(el);
}
public String toString() {
return pool.toString();
}
}
然后看看ExpressionParser.java，原理已经列上，注释也有，使用了单例模式，就请自己看了：
package
net.rubyeye.codelib.util;
/**
* <p>类说明：用于表达式与实际值的比较</p>
* <p>注意事项：</p>
* <pre></pre>
* <p>创建日期：Aug 6, 2007 10:18:58 AM</p>
* <p>文件名:ExpressionParser.java</p>
* @author :庄晓丹
* @version $Id:$
*/
public class ExpressionParser {
private static final boolean DEBUG = true ;
private static ExpressionParser parser = new ExpressionParser();
private ExpressionParser() {
}
public static ExpressionParser getInstance() {
return parser;
}
public boolean fireRule(String expression, double fact) {
traceCalculate( " \nexpression: " + expression);
expression = expression.replace( " \n|\r " , "" ).trim();
char [] chars = expression.toCharArray();
return parseExpression(fact, chars);
}
/**
* @param fact
* @param operatorsStack
* @param operandsStack
* @param chars
* @param operand
* @param operator
* @return
*/
private boolean parseExpression( double fact, char [] chars) {
boolean result = true ;
String operand = "" ;
String operator = "" ;
Stack operatorsStack = new Stack();
Stack operandsStack = new Stack();
for ( int i = 0 ; i < chars.length; i ++ ) {
char token = chars[i];
traceCalculate( " token: " + token);
if (Character.isDigit(token) || token == ' . ' ) {
if ( ! operator.equals( "" )) {
traceCalculate( " push operator: " + operator);
// 将操作符放入操作符号栈
operatorsStack.push(operator);
operator = "" ;
}
operand += token;
result = checkTail(fact, operatorsStack, operandsStack,
chars.length, operand, result, i);
continue ;
} else if (Character.isLetter(token)) {
if ( ! operator.equals( "" )) {
traceCalculate( " push operator: " + operator);
// 将操作符放入操作符号栈
operatorsStack.push(operator);
operator = "" ;
}
operand = String.valueOf(token);
result = checkTail(fact, operatorsStack, operandsStack,
chars.length, operand, result, i);
// 将操作数放入操作数栈
operandsStack.push(operand);
traceCalculate( " push operand: " + token);
operand = "" ;
continue ;
} else {
if ( ! operatorsStack.isEmpty() && ! operandsStack.isEmpty()) {
// 当前操作数是字母(变量)，已存入栈，因此需要取出
if (operand.equals( "" )) {
operand = (String) operandsStack.pop();
result = result
&& calculatePerfomance(operatorsStack,
operandsStack, operand, fact);
// 当前操作数是数字
} else {
result = result
&& calculatePerfomance(operatorsStack,
operandsStack, operand, fact);
}
}
if ( ! operand.equals( "" )) {
result = checkTail(fact, operatorsStack, operandsStack,
chars.length, operand, result, i);
// 将操作数放入操作数栈
operandsStack.push(operand);
traceCalculate( " push2 operand: " + operand);
operand = "" ;
}
operator += token;
continue ;
}
}
return result;
}
/**
* 判断是否已经到表达式尾端，如果是，计算
* @param fact
* @param operatorsStack
* @param operandsStack
* @param chars
* @param operand
* @param result
* @param i
* @return
*/
private boolean checkTail( double fact, Stack operatorsStack,
Stack operandsStack, int chars_length, String operand,
boolean result, int i) {
if (i == chars_length - 1 ) {
result = result
&& calculatePerfomance(operatorsStack, operandsStack,
operand, fact);
}
return result;
}
private void displayStack(String name,Stack stack) {
if (DEBUG) {
for ( int i = 0 ; i < stack.pool.size(); i ++ )
System.out.println(name + stack.pool.get(i));
}
}
private boolean calculatePerfomance(Stack operatorsStack,
Stack operandsStack, String currentOperand, double fact) {
traceCalculate( " 开始计算 " );
displayStack( " operators stack: " ,operatorsStack);
displayStack( " operands stack: " ,operandsStack);
traceCalculate( " currentOperand= " + currentOperand);
String operator = (String) operatorsStack.pop();
double lastOperand = coverOperandToDouble((String) operandsStack.pop(),
fact);
double nextOperand = coverOperandToDouble(currentOperand, fact);
boolean result = true ;
if (operator.equals( " == " ))
return lastOperand == nextOperand;
if (operator.indexOf("=") >= 0)
hasEqual = true;
char [] operators = operator.toCharArray();
for ( int i = 0 ; i < operators.length; i ++ ) {
switch (operators[i]) {
case ' < ' :
result = result && (lastOperand < nextOperand);
break ;
case ' = ' :
// result为false，也就是小于，大于符号不满足的时候，判断等号是否成立
if ( ! result)
result = (lastOperand == nextOperand);
break ;
case ' > ' :
result = result && (lastOperand > nextOperand);
break ;
}
}
if ((!result) && hasEqual)
result = lastOperand == nextOperand;
return result;
}
/**
* 用于debug
*/
private void traceCalculate(String info) {
if (DEBUG)
System.out.println(info);
}
private double coverOperandToDouble(String operand, double fact) {
// 如果是字母，也就是变量，返回fact变量
if (Character.isLetter(operand.toCharArray()[ 0 ]))
return fact;
else
return Double.parseDouble(operand);
}
}
通过DEBUG变量来决定是否输出计算过程，你可以设置为true来看看某个表达式的计算过程。附上单元测试来看看怎么用：
/**
* <p>类说明：用于表达式与实际值的比较</p>
* <p>注意事项：</p>
* <pre></pre>
* <p>创建日期：Aug 6, 2007 10:18:58 AM</p>
* <p>文件名:ExpressionParser.java</p>
* @author :庄晓丹
* @version $Id:$
*/
public class ExpressionParser {
private static final boolean DEBUG = true ;
private static ExpressionParser parser = new ExpressionParser();
private ExpressionParser() {
}
public static ExpressionParser getInstance() {
return parser;
}
public boolean fireRule(String expression, double fact) {
traceCalculate( " \nexpression: " + expression);
expression = expression.replace( " \n|\r " , "" ).trim();
char [] chars = expression.toCharArray();
return parseExpression(fact, chars);
}
/**
* @param fact
* @param operatorsStack
* @param operandsStack
* @param chars
* @param operand
* @param operator
* @return
*/
private boolean parseExpression( double fact, char [] chars) {
boolean result = true ;
String operand = "" ;
String operator = "" ;
Stack operatorsStack = new Stack();
Stack operandsStack = new Stack();
for ( int i = 0 ; i < chars.length; i ++ ) {
char token = chars[i];
traceCalculate( " token: " + token);
if (Character.isDigit(token) || token == ' . ' ) {
if ( ! operator.equals( "" )) {
traceCalculate( " push operator: " + operator);
// 将操作符放入操作符号栈
operatorsStack.push(operator);
operator = "" ;
}
operand += token;
result = checkTail(fact, operatorsStack, operandsStack,
chars.length, operand, result, i);
continue ;
} else if (Character.isLetter(token)) {
if ( ! operator.equals( "" )) {
traceCalculate( " push operator: " + operator);
// 将操作符放入操作符号栈
operatorsStack.push(operator);
operator = "" ;
}
operand = String.valueOf(token);
result = checkTail(fact, operatorsStack, operandsStack,
chars.length, operand, result, i);
// 将操作数放入操作数栈
operandsStack.push(operand);
traceCalculate( " push operand: " + token);
operand = "" ;
continue ;
} else {
if ( ! operatorsStack.isEmpty() && ! operandsStack.isEmpty()) {
// 当前操作数是字母(变量)，已存入栈，因此需要取出
if (operand.equals( "" )) {
operand = (String) operandsStack.pop();
result = result
&& calculatePerfomance(operatorsStack,
operandsStack, operand, fact);
// 当前操作数是数字
} else {
result = result
&& calculatePerfomance(operatorsStack,
operandsStack, operand, fact);
}
}
if ( ! operand.equals( "" )) {
result = checkTail(fact, operatorsStack, operandsStack,
chars.length, operand, result, i);
// 将操作数放入操作数栈
operandsStack.push(operand);
traceCalculate( " push2 operand: " + operand);
operand = "" ;
}
operator += token;
continue ;
}
}
return result;
}
/**
* 判断是否已经到表达式尾端，如果是，计算
* @param fact
* @param operatorsStack
* @param operandsStack
* @param chars
* @param operand
* @param result
* @param i
* @return
*/
private boolean checkTail( double fact, Stack operatorsStack,
Stack operandsStack, int chars_length, String operand,
boolean result, int i) {
if (i == chars_length - 1 ) {
result = result
&& calculatePerfomance(operatorsStack, operandsStack,
operand, fact);
}
return result;
}
private void displayStack(String name,Stack stack) {
if (DEBUG) {
for ( int i = 0 ; i < stack.pool.size(); i ++ )
System.out.println(name + stack.pool.get(i));
}
}
private boolean calculatePerfomance(Stack operatorsStack,
Stack operandsStack, String currentOperand, double fact) {
traceCalculate( " 开始计算 " );
displayStack( " operators stack: " ,operatorsStack);
displayStack( " operands stack: " ,operandsStack);
traceCalculate( " currentOperand= " + currentOperand);
String operator = (String) operatorsStack.pop();
double lastOperand = coverOperandToDouble((String) operandsStack.pop(),
fact);
double nextOperand = coverOperandToDouble(currentOperand, fact);
boolean result = true ;
if (operator.equals( " == " ))
return lastOperand == nextOperand;
if (operator.indexOf("=") >= 0)
hasEqual = true;
char [] operators = operator.toCharArray();
for ( int i = 0 ; i < operators.length; i ++ ) {
switch (operators[i]) {
case ' < ' :
result = result && (lastOperand < nextOperand);
break ;
case ' = ' :
// result为false，也就是小于，大于符号不满足的时候，判断等号是否成立
if ( ! result)
result = (lastOperand == nextOperand);
break ;
case ' > ' :
result = result && (lastOperand > nextOperand);
break ;
}
}
if ((!result) && hasEqual)
result = lastOperand == nextOperand;
return result;
}
/**
* 用于debug
*/
private void traceCalculate(String info) {
if (DEBUG)
System.out.println(info);
}
private double coverOperandToDouble(String operand, double fact) {
// 如果是字母，也就是变量，返回fact变量
if (Character.isLetter(operand.toCharArray()[ 0 ]))
return fact;
else
return Double.parseDouble(operand);
}
}
package
net.rubyeye.codelib.util;
/**
* 测试表达式计算
*/
import junit.framework.TestCase;
public class ExpressionCalculateTest extends TestCase {
String exp1,exp2,exp3, exp4;
double v1, v2, v3, v4, v5;
ExpressionParser parser = null ;
protected void setUp() throws Exception {
exp1 = " a<80 " ;
exp2 = " 80<=a<81 " ;
exp3 = " 81<=a<=82 " ;
exp4 = " a>=90 " ;
v1 = 70.0 ;
v2 = 81.2 ;
v3 = 80 ;
v4 = 90 ;
v5 = 92 ;
parser = ExpressionParser.getInstance();
}
public void testFireRule() throws Exception {
assertFalse(parser.fireRule(exp1, v4));
assertTrue(parser.fireRule(exp1, v1));
assertFalse(parser.fireRule(exp1, v3));
assertFalse(parser.fireRule(exp2, v2));
assertTrue(parser.fireRule(exp2, v3));
assertFalse(parser.fireRule(exp2, 82 ));
assertTrue(parser.fireRule(exp3, v2));
assertTrue(parser.fireRule(exp4, v4));
assertFalse(parser.fireRule(exp4, v1));
assertTrue(parser.fireRule(exp4, v5));
assertTrue(parser.fireRule( " b==100.00 " , 100.0 ));
assertTrue(parser.fireRule( " c==0.00 " , 0 ));
assertTrue(parser.fireRule( " 60<=c<=80 " , 79.9 ));
assertFalse(parser.fireRule( " 60<=50<=80 " , 0.0 ));
assertTrue(parser.fireRule( " 60<=79<=80 " , 0.0 ));
assertFalse(parser.fireRule( " 60<=99<=80 " , 0.0 ));
assertTrue(parser.fireRule( " 60<=80<=90<100 " , 0.0 ));
assertFalse(parser.fireRule( " 60<=99<=80<100 " , 0.0 ));
assertTrue(parser.fireRule("10=<a=<30", 25));
}
}
/**
* 测试表达式计算
*/
import junit.framework.TestCase;
public class ExpressionCalculateTest extends TestCase {
String exp1,exp2,exp3, exp4;
double v1, v2, v3, v4, v5;
ExpressionParser parser = null ;
protected void setUp() throws Exception {
exp1 = " a<80 " ;
exp2 = " 80<=a<81 " ;
exp3 = " 81<=a<=82 " ;
exp4 = " a>=90 " ;
v1 = 70.0 ;
v2 = 81.2 ;
v3 = 80 ;
v4 = 90 ;
v5 = 92 ;
parser = ExpressionParser.getInstance();
}
public void testFireRule() throws Exception {
assertFalse(parser.fireRule(exp1, v4));
assertTrue(parser.fireRule(exp1, v1));
assertFalse(parser.fireRule(exp1, v3));
assertFalse(parser.fireRule(exp2, v2));
assertTrue(parser.fireRule(exp2, v3));
assertFalse(parser.fireRule(exp2, 82 ));
assertTrue(parser.fireRule(exp3, v2));
assertTrue(parser.fireRule(exp4, v4));
assertFalse(parser.fireRule(exp4, v1));
assertTrue(parser.fireRule(exp4, v5));
assertTrue(parser.fireRule( " b==100.00 " , 100.0 ));
assertTrue(parser.fireRule( " c==0.00 " , 0 ));
assertTrue(parser.fireRule( " 60<=c<=80 " , 79.9 ));
assertFalse(parser.fireRule( " 60<=50<=80 " , 0.0 ));
assertTrue(parser.fireRule( " 60<=79<=80 " , 0.0 ));
assertFalse(parser.fireRule( " 60<=99<=80 " , 0.0 ));
assertTrue(parser.fireRule( " 60<=80<=90<100 " , 0.0 ));
assertFalse(parser.fireRule( " 60<=99<=80<100 " , 0.0 ));
assertTrue(parser.fireRule("10=<a=<30", 25));
}
}
这个小程序对处理一般的类似区间的规则计算应该还有点用，希望对别人帮助吧。表达式中的逻辑运算符>=和<=可以用=>和=<替代。
文章转自庄周梦蝶 ，原文发布时间2007-08-06
