解析逻辑操作- AND, OR，动态循环条件

Question

我有一个用逻辑子句存储的传入记录过滤器，如下所示。

Acct1 = 'Y' AND Acct2 = 'N' AND Acct3 = 'N' AND Acct4 = 'N' AND Acct5 = 'N' AND ((Acct6 = 'N' OR Acct7 = 'N' AND Acct1 = 'Y') AND Formatted= 'N' AND Acct9 = 'N' AND (Acct10 = 'N' AND Acct11 = 'N') AND EditableField= 'N' )

我输入到这个子句的数据将来自如下的Csv文件。

Country,Type,Usage,Acct1,Acct2,Acct3,Acct4,Acct5,Acct6,Acct7,Formatted,Acct9,Acct10,Acct11,EditableField
USA,Premium,Corporate,Y,N,Y,N,N,N,Y,N,Y,N,Y,N,
Mexico,Premium,Corporate,Y,N,Y,N,Y,N,Y,N,Y,N,Y,N,
USA,Premium,Corporate,Y,N,Y,N,N,N,N,Y,Y,N,Y,N,
USA,Premium,Corporate,Y,N,Y,N,Y,N,Y,Y,Y,N,Y,N,

我必须根据子句中定义的条件过滤掉文件中的记录。这是一个简单的子句的例子，但将有更多的内部条件比这，子句可以随时改变用户想要的，将有10个这样的子句，记录必须依次通过。

所以我正在寻找一种方法来动态解释该子句并将其应用于传入的记录。请提供你的建议，关于如何设计/任何例子，如果可用。

Answer 1

这是完整的解决方案，不包括第三方库，如ANTLR或JavaCC。请注意，虽然它是可扩展的，但其功能仍然有限。如果你想创建更复杂的表达式，你最好使用语法生成器。

首先，让我们编写一个标记器，它将输入字符串拆分为标记。以下是令牌类型:

private static enum TokenType {
    WHITESPACE, AND, OR, EQUALS, LEFT_PAREN, RIGHT_PAREN, IDENTIFIER, LITERAL, EOF
}

令牌类本身:

private static class Token {
    final TokenType type;
    final int start; // start position in input (for error reporting)
    final String data; // payload
    public Token(TokenType type, int start, String data) {
        this.type = type;
        this.start = start;
        this.data = data;
    }
    @Override
    public String toString() {
        return type + "[" + data + "]";
    }
}

为了简化标记化，让我们创建一个regexp，它从输入字符串中读取下一个标记:

private static final Pattern TOKENS = 
        Pattern.compile("(\s+)|(AND)|(OR)|(=)|(\()|(\))|(\w+)|'([^']+)'");

注意，它有许多组，每个TokenType以相同的顺序有一个组(首先是WHITESPACE，然后是AND，等等)。最后是标记器方法:

private static TokenStream tokenize(String input) throws ParseException {
    Matcher matcher = TOKENS.matcher(input);
    List<Token> tokens = new ArrayList<>();
    int offset = 0;
    TokenType[] types = TokenType.values();
    while (offset != input.length()) {
        if (!matcher.find() || matcher.start() != offset) {
            throw new ParseException("Unexpected token at " + offset, offset);
        }
        for (int i = 0; i < types.length; i++) {
            if (matcher.group(i + 1) != null) {
                if (types[i] != TokenType.WHITESPACE)
                    tokens.add(new Token(types[i], offset, matcher.group(i + 1)));
                break;
            }
        }
        offset = matcher.end();
    }
    tokens.add(new Token(TokenType.EOF, input.length(), ""));
    return new TokenStream(tokens);
}

我使用java.text.ParseException。这里我们将正则表达式Matcher应用到输入的末尾。如果在当前位置不匹配，则抛出异常。否则，我们寻找找到的匹配组，并从中创建一个令牌，忽略WHITESPACE令牌。最后，我们添加一个EOF令牌，它表示输入的结束。结果作为特殊的TokenStream对象返回。下面是TokenStream类，它将帮助我们进行解析:

private static class TokenStream {
    final List<Token> tokens;
    int offset = 0;
    public TokenStream(List<Token> tokens) {
        this.tokens = tokens;
    }
    // consume next token of given type (throw exception if type differs)
    public Token consume(TokenType type) throws ParseException {
        Token token = tokens.get(offset++);
        if (token.type != type) {
            throw new ParseException("Unexpected token at " + token.start
                    + ": " + token + " (was looking for " + type + ")",
                    token.start);
        }
        return token;
    }
    // consume token of given type (return null and don't advance if type differs)
    public Token consumeIf(TokenType type) {
        Token token = tokens.get(offset);
        if (token.type == type) {
            offset++;
            return token;
        }
        return null;
    }
    @Override
    public String toString() {
        return tokens.toString();
    }
}

我们有一个标记器，万岁。你现在可以使用System.out.println(tokenize("Acct1 = 'Y' AND (Acct2 = 'N' OR Acct3 = 'N')"));

进行测试

现在让我们编写解析器，它将创建表达式的树状表示。首先是所有树节点的接口Expr:

public interface Expr {
    public boolean evaluate(Map<String, String> data);
}

它是唯一用于计算给定数据集表达式的方法，如果数据集匹配则返回true。

最基本的表达式是EqualsExpr，类似于Acct1 = 'Y'或'Y' = Acct1:

private static class EqualsExpr implements Expr {
    private final String identifier, literal;
    public EqualsExpr(TokenStream stream) throws ParseException {
        Token token = stream.consumeIf(TokenType.IDENTIFIER);
        if(token != null) {
            this.identifier = token.data;
            stream.consume(TokenType.EQUALS);
            this.literal = stream.consume(TokenType.LITERAL).data;
        } else {
            this.literal = stream.consume(TokenType.LITERAL).data;
            stream.consume(TokenType.EQUALS);
            this.identifier = stream.consume(TokenType.IDENTIFIER).data;
        }
    }
    @Override
    public String toString() {
        return identifier+"='"+literal+"'";
    }
    @Override
    public boolean evaluate(Map<String, String> data) {
        return literal.equals(data.get(identifier));
    }
}

toString()方法仅供参考，您可以删除它。

接下来，我们将定义SubExpr类，它要么是EqualsExpr，要么是括号中更复杂的东西(如果我们看到括号):

private static class SubExpr implements Expr {
    private final Expr child;
    public SubExpr(TokenStream stream) throws ParseException {
        if(stream.consumeIf(TokenType.LEFT_PAREN) != null) {
            child = new OrExpr(stream);
            stream.consume(TokenType.RIGHT_PAREN);
        } else {
            child = new EqualsExpr(stream);
        }
    }
    @Override
    public String toString() {
        return "("+child+")";
    }
    @Override
    public boolean evaluate(Map<String, String> data) {
        return child.evaluate(data);
    }
}

下一个是AndExpr，它是一组SubExpr表达式，由AND运算符连接:

private static class AndExpr implements Expr {
    private final List<Expr> children = new ArrayList<>();
    public AndExpr(TokenStream stream) throws ParseException {
        do {
            children.add(new SubExpr(stream));
        } while(stream.consumeIf(TokenType.AND) != null);
    }
    @Override
    public String toString() {
        return children.stream().map(Object::toString).collect(Collectors.joining(" AND "));
    }
    @Override
    public boolean evaluate(Map<String, String> data) {
        for(Expr child : children) {
            if(!child.evaluate(data))
                return false;
        }
        return true;
    }
}

为了简洁，我在toString中使用Java-8流API。如果你不能使用Java-8，你可以用for循环重写它，或者完全删除toString。

最后我们定义OrExpr，它是由OR连接的AndExpr的集合(通常OR的优先级低于AND)。这与AndExpr:

非常相似

private static class OrExpr implements Expr {
    private final List<Expr> children = new ArrayList<>();
    public OrExpr(TokenStream stream) throws ParseException {
        do {
            children.add(new AndExpr(stream));
        } while(stream.consumeIf(TokenType.OR) != null);
    }
    @Override
    public String toString() {
        return children.stream().map(Object::toString).collect(Collectors.joining(" OR "));
    }
    @Override
    public boolean evaluate(Map<String, String> data) {
        for(Expr child : children) {
            if(child.evaluate(data))
                return true;
        }
        return false;
    }
}

和最终的parse方法:

public static Expr parse(TokenStream stream) throws ParseException {
    OrExpr expr = new OrExpr(stream);
    stream.consume(TokenType.EOF); // ensure that we parsed the whole input
    return expr;
}

因此，您可以解析表达式以获得Expr对象，然后根据CSV文件的行对它们求值。我假设您能够将CSV行解析为Map<String, String>。下面是用法示例:

Map<String, String> data = new HashMap<>();
data.put("Acct1", "Y");
data.put("Acct2", "N");
data.put("Acct3", "Y");
data.put("Acct4", "N");
Expr expr = parse(tokenize("Acct1 = 'Y' AND (Acct2 = 'Y' OR Acct3 = 'Y')"));
System.out.println(expr.evaluate(data)); // true
expr = parse(tokenize("Acct1 = 'N' OR 'Y' = Acct2 AND Acct3 = 'Y'"));
System.out.println(expr.evaluate(data)); // false

Answer 2

我不知道这在Java中的效率如何，但是基本的字符串替换操作可能是一个简单的解决方案。

从一个查询字符串开始:

Acct1 = 'Y' AND Acct2 = 'N' AND Acct3 = 'Y' AND Acct4 = 'N' AND Acct5 = 'N' OR (Acct6 = 'N' OR Acct7 = 'N') AND Acct8 = 'N' AND Acct9 = 'Y' AND (Acct10 = 'N' OR Acct11 = 'N') AND Acct12 = 'N')

对于csv中的每一行，例如Y,N,Y,N,Y,N,Y,N,Y,N,Y,N字符串—将查询中的列头替换为值;这给你:

Y = Y和N = ' N '和Y = Y和N = ' N '和Y ="N"或((N = ' N '或Y = ' N ')和N = ' N '和Y ="Y"和(N = ' N '或Y = ' N ')和N = ' N ')

然后用它们的布尔值替换比较:
-用Y代替N = 'N'和Y = 'Y'
-将N = 'Y'和Y = 'N'替换为N

这将导致:

Y AND Y AND Y AND Y AND N OR ((Y OR N) AND Y AND Y AND (Y OR N) AND Y)

然后循环执行一系列字符串替换操作，将真值替换为Y，将假值替换为N:
-用Y代替Y AND Y
-用N取代N AND N, N AND Y和Y AND N
-用Y代替Y OR Y、N OR Y和Y OR N
-用N代替N OR N
-用N代替(N)
-用Y代替(Y)

这将逐渐减少布尔语句:

Y AND Y AND Y AND Y AND N OR ((Y OR N) AND Y AND Y AND (Y OR N) AND Y)
Y AND Y AND N OR ((Y) AND Y AND (Y) AND Y)
Y AND N OR (Y AND Y AND Y AND Y)
N OR (Y AND Y)
N OR (Y)
Y

如果查询包含没有括号的隐式优先级，例如N AND N OR Y AND Y，您希望AND优先于OR，则在替换OR之前，始终用尽替换AND和括号的可能性:

while (string length decreases) {
    while (string length decreases) {
        replace every "(Z)" by "Z"
        replace every "X AND Y" by "Z"
    }
    replace one "X OR Y" by "Z"
}

在此缩减过程中，确保在每次迭代后检查字符串长度是否减少，以避免由格式错误的查询引起的无限循环。

Answer 3

提示:

一个可能的解决方案是将布尔条件值存储在单个字符串属性中，如"ynynnnynynynyn"，或者更好的是打包为二进制整数。然后，对于给定的子句，生成一个包含所有可接受字符串的表。连接操作将返回所有需要的记录。

您甚至可以通过在生成表时将子句编号与可接受的字符串相邻来一次处理多个子句。

尽管表大小在条件数量上可能呈指数级增长，但对于中等数量的条件，这仍然是相当可管理的。

Answer 4

您所拥有的是用某种语言编写的表达式，该语言似乎符合SQL的WHERE子句语法。所以你需要:

• 该语言的解析器，可以构建AST，然后构建表达式树
• 根据上下文(即根据名称Acct1, Acct2等进行解析的环境)评估表达式树的引擎

这是一种简单的语言，因此您可以手工构建解析器，或者查看ANTLR或JavaCC -在这种情况下，我建议您查看一些示例(ANTLR或JavaCC) -当然，您不需要完整的SQL解析器!只提取你需要的部分。

一个更简单的方法是用一些可以通过Java脚本接口调用的语言来编写过滤器表达式，比如Javascript或Groovy(或者Ruby、Python…)。我不建议在输入文本上运行查找/替换来将类似sql的语言转换为目标语言(例如Python有and和or操作符-小写)，因为这很容易根据输入字符串的内容而中断。