c语言中布尔表达式字符串到树结构的转换#

我不知道一个图书馆,但它可以像这样实现。

您需要的基本上是来自给定表达式的表达式树(按顺序遍历)

要构造树,请使用以下步骤: 在表达式中循环

1. 如果字符不是运算符,则将其推入堆栈。

2. 如果字符是运算符,则弹出两个操作数并使其成为子操作数 并将当前节点推入堆栈。

3. 最后,堆栈中只有元素是您的树。

请参考这个 link 算法的实现。

实际上,可以使用类似于语法分析器的生成器库。 ANTLR 为了达到你的效果,但是对于一个简单的任务来说,这是过分的。

你可以用下面的方法来定义你自己的小语法(我用了‘+’代替了‘‘’’和‘‘。’代替‘& & & &’’。”用符号替换这些符号,同时对递归下降解析器代码进行适当的代码更改):

S → T '+' S | T
T → F '.' T | F
F → A | '('S')'
A → 'a' | 'b' | 'c' | ... | ɛ

基于上述语法,现在您可以轻松地编写递归下降分析器如下(下面的代码可能不是语法正确的,只是使用它作为伪代码):

public Node S(){
        Node  T = T();

        if(inputHasMoreUnseenCharacters() && peekNextCharacterInString().equals("+")){
            eatNextCharacterInString();//eats '+'
            Node S = S();
            return new NodeOR(T, S);
        }

        return T;
    }

public Node T(){
    Node F= F();

    if(inputHasMoreUnseenCharacters() && peekNextCharacterInString().equals(".")){
        eatNextCharacterInString();//eats '.'
        Node T = T();
        return new NodeAND(F, T);
    }

    return F;
}

public Node F(){
    String nextCharacterInput = eatNextCharacterInString();
    Node node = null;
    if(nextCharacterInput.equals("(")){
        //eatNextCharacterInString(); //eats '('
        node = S();
        eatNextCharacterInString(); //eats ')'
    }else{
        node = A(nextCharacterInput);
    }
    return node;
}

public Node A(String nextCharacterInput){
    Node node = null;
    return new NodeSingleValue(nextCharacterInput);
}

类nodeor、node and和nodesinglevalue都是类node的子类。一旦调用方法s(),就可以将树的根作为node类型的对象。

对于递归下降解析的介绍, this 链接可能有用。