前言
逆波兰表示法（Reverse Polish notation，RPN，或逆波兰记法），是一种是由波兰数学家扬·武卡谢维奇1920年引入的数学表达式方式，在逆波兰记法中，所有操作符置于操作数的后面，因此也被称为后缀表示法。逆波兰记法不需要括号来标识操作符的优先级，比如：3 – 4 + 5，转换为波兰表达式为：3 4 – 5 +
场景
以工单系统为例，比如发起了一个审批流程，通过规则引擎配置了如下规则：
$合同类型$ = ‘商务合同’ || ( $合同总金额$ > 1000000 && $合同总金额$ < 2000000 )
满足上面表达式会走审批1，否则走审批2逻辑。
对于上面的表达式，我们都知道首先应该先比较 || 两边的表达式，||右边的表达式因为是用括号连接，所以需要放在一起做&&比较，最后左右两边做 || 操作
但这是人思维方式，机器并不这样识别，机器可不知道哪个先比较，哪个后比较，所以可以将其转换为如下格式，逆波兰（后缀）表达式
合同类型、商务合同、=、合同总金额、1000000、>、合同总金额、2000000、<、&&、||
上面的表达式，机器就比较好识别了，一般利用栈来输出结果：
当为数值时压栈，当遇到表达式，从栈里面拿出两个数进行比较（运算）
算法流程介绍
转换为逆波兰表达式的基本思路是：
1、需要两个栈来存放“操作数”（如：合同类型）、运算符（如：||）
2、每个操作符都有自己的优先级
3、如果是操作数，则放入操作数栈
4、如果是运算符（不包括括号），则与运算符栈顶元素进行比较，如果优先级大于栈顶的元素，则直接入栈，如果小于，则将栈顶的元素取出，入操作数栈
5、如果运算符是“(”，则直接放入运算符栈顶，如果运算符是“)”，则从运算符依次取出元素放入操作数栈，直到遇到“(”
下面是我画的一个操作流程：
代码实现
public class ExpressionEvaluator {
private static String leftBraces = "(";
private static String rightBraces = ")";
private static Map<String, Integer> operatorPriorityMap = new HashMap<>();
static {
operatorPriorityMap.put("(",-1);
operatorPriorityMap.put(")",-1);
operatorPriorityMap.put("||",1);
operatorPriorityMap.put("&&",1);
operatorPriorityMap.put("=",2);
operatorPriorityMap.put(">",2);
operatorPriorityMap.put("<",2);
// operatorPriorityMap.put("+",1);
// operatorPriorityMap.put("-",1);
// operatorPriorityMap.put("*",2);
// operatorPriorityMap.put("/",2);
}
/**
* 中缀表达式转化为后缀表达式
* @param expression
* @return
*/
public Queue<String> parseExpression(String expression) {
String[] expressionArr = expression.split(" ");
Stack<String> operatorStack = new Stack();
Queue<String> operandQueue = new LinkedBlockingQueue<>();
for(int i=0;i<expressionArr.length;i++) {
if (operatorPriorityMap.containsKey(expressionArr[i])) {
//操作符
if (expressionArr[i].equals(leftBraces)) {
//遇到左括号
operatorStack.add(expressionArr[i]);
}else if (expressionArr[i].equals(rightBraces)) {
//遇到右括号
appendLeftBracesOperator(operatorStack, operandQueue);
} else {
if (operatorStack.isEmpty()) {
operatorStack.add(expressionArr[i]);
continue;
}
String topOperate = operatorStack.peek();
if (comparePriority(expressionArr[i], topOperate) >= 0) {
//优先级大于栈顶的元素
operatorStack.add(expressionArr[i]);
} else {
//优先级小于栈顶的元素
appendLowPriority(operatorStack, operandQueue, expressionArr[i]);
}
}
} else {
//操作数
operandQueue.add(expressionArr[i]);
}
}
while (!operatorStack.isEmpty()) {
operandQueue.add(operatorStack.pop());
}
return operandQueue;
}
/**
* 将操作符栈低优先级的元素移到操作数队列中
* @param operatorStack
* @param operandStack
* @param operator
*/
private void appendLowPriority(Stack<String> operatorStack, Queue<String> operandStack, String operator) {
while (!operatorStack.isEmpty() && comparePriority(operator, operatorStack.peek()) < 0) {
String topOperate = operatorStack.pop();
operandStack.add(topOperate);
}
operatorStack.add(operator);
}
/**
* 将左括号之前的操作符元素移动到操作数栈中
* @param operatorStack
* @param operandStack
*/
private void appendLeftBracesOperator(Stack<String> operatorStack, Queue<String> operandStack) {
String topOperator = operatorStack.pop();
while (!topOperator.equals(leftBraces)) {
operandStack.add(topOperator);
topOperator = operatorStack.pop();
}
}
public static void main(String[] args) {
//String s = "1 + ( 2 + 3 * 4 ) * 2 / 4 - 5";
String s = "商务合同1 = 商务合同 || ( 1100000 > 1000000 && 1100000 < 2000000 )";
ExpressionEvaluator ee = new ExpressionEvaluator();
Queue<String> queue = ee.parseExpression(s);
System.out.println(queue.toString());
}
}
逻辑运算
通过将表达式转换后，通过栈就可以实现对表达式的计算，具体思路：
1、遍历队列，如果是操作数，则入栈
2、如果是操作符，则从栈顶取出两个操作数进行运算操作
3、将最终结果返回
代码实现
/**
* 计算后缀表达式结果
* @param queue
* @return
*/
public boolean calcExpression(Queue<String> queue) {
if(Objects.isNull(queue)) {
throw new RuntimeException("表达式为空");
}
String s = queue.poll();
Stack<Object> stack = new Stack();
while (Objects.nonNull(s)) {
if (operatorPriorityMap.containsKey(s)) {
Object o1 = stack.pop();
Object o2 = stack.pop();
if (">".equals(s)) {
stack.push(Double.parseDouble(o2.toString()) > Double.parseDouble(o1.toString()));
} else if ("<".equals(s)) {
stack.push(Double.parseDouble(o2.toString()) < Double.parseDouble(o1.toString()));
} else if ("=".equals(s)) {
stack.push(o2.equals(o1));
} else if ("||".equals(s)) {
stack.push(Boolean.parseBoolean(o2.toString()) || Boolean.parseBoolean(o1.toString()));
} else if ("&&".equals(s)){
stack.push(Boolean.parseBoolean(o2.toString()) && Boolean.parseBoolean(o1.toString()));
}
} else {
stack.push(s);
}
s = queue.poll();
}
return Boolean.parseBoolean(stack.pop().toString());
}
