逆波兰算法在规则引擎中的运用

前言

逆波兰表示法(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());
    }