java处理逻辑表达式计算问题

在处理SQL的where条件时，发现逻辑运算表达式不是那么简单，并不是一种线型计算结构。

但是表达式树的计算又是SQL查询引擎的核心，SQL的抽象语法树最终还是要转换为表达式树来处理。

所以基于原来的表达式案例，进行简单的升级，写了一个简单的逻辑表达式处理器。

首先我们的逻辑表达式的操作数只有两种true，false，

操作符也只有三种，and(与),or(或),!(非)

我们先写一个antlr的语法文件

grammar LExpr;
@header{package com.example.listeners.expr2;}
s : e ;

e : '(' e ')'       # Atom
  | NOT e           # Not
  | e AND e         # And
  | e OR e             # Or
  | BOOL            # Bool
  ;

AND: 'and' ;
OR : 'or' ;
NOT : '!';
BOOL : 'true' |'false' ;
WS : [ \t\n]+ -> skip ;

基于这个语法文件，我们就得到了基本的词法分析器和语法分析树。

接下来就是如何解析表达式，我们模拟栈机用一个stack来存储操作数

public class TestExpression {

    public static class Evaluator extends LExprBaseListener {
        Stack<Boolean> stack = new Stack<Boolean>();


        @Override
        public void exitNot(LExprParser.NotContext ctx) {
            Boolean pop = stack.pop();
            stack.push(!pop);
        }

        @Override
        public void exitOr(LExprParser.OrContext ctx) {
            Boolean left = stack.pop();
            Boolean right = stack.pop();
            stack.push(left || right);
        }

        @Override
        public void exitBool(LExprParser.BoolContext ctx) {
            String text = ctx.getText();
            if (text.equals("true")) {
                stack.push(true);
            } else {
                stack.push(false);
            }
        }

        @Override
        public void exitAnd(LExprParser.AndContext ctx) {
            Boolean left = stack.pop();
            Boolean right = stack.pop();
            stack.push(left && right);
        }
    }

    public static void main(String[] args) throws Exception {
        String sdl = "! (false or true) and false";
        CodePointCharStream input = CharStreams.fromString(sdl);
        LExprLexer lexer = new LExprLexer(input);
        CommonTokenStream tokens = new CommonTokenStream(lexer);
        LExprParser parser = new LExprParser(tokens);
        parser.setBuildParseTree(true);      // tell ANTLR to build a parse tree
        ParseTree tree = parser.s(); // parse
        // show tree in text form
        System.out.println(tree.toStringTree(parser));

        ParseTreeWalker walker = new ParseTreeWalker();
        TestExpression.Evaluator eval = new TestExpression.Evaluator();
        walker.walk(eval, tree);
        System.out.println("stack result = " + eval.stack.pop());
    }
}

输出：

(s (e (e ! (e ( (e (e false) or (e true)) ))) and (e false)))
stack result = false

 除此之外，还可以使用访问者模式来遍历表达式树，或者用Map存储树的每个节点的值，最终的结果都是一样的。