如何解析布尔表达式并将其加载到类中

本文关键字：加载 何解析 布尔表达式 | 更新日期: 2023-09-27 18:21:43

我得到了以下BoolExpr类：

class BoolExpr
{
    public enum BOP { LEAF, AND, OR, NOT };
    //
    //  inner state
    //
    private BOP    _op;
    private BoolExpr _left;
    private BoolExpr _right;
    private String   _lit;
    //
    //  private constructor
    //
    private BoolExpr(BOP op, BoolExpr left, BoolExpr right)
    {
        _op = op;
        _left  = left;
        _right = right;
        _lit = null;
    }
    private BoolExpr(String literal)
    {
        _op = BOP.LEAF;
        _left  = null;
        _right = null;
        _lit = literal;
    }
    //
    //  accessor
    //
    public BOP Op
    {
        get { return _op;  }
        set { _op = value; }
    }
    public BoolExpr Left
    {
        get { return _left;  }
        set { _left = value; }
    }
    public BoolExpr Right
    {
        get { return _right;  }
        set { _right = value; }
    }
    public String Lit
    {
        get { return _lit; }
        set { _lit = value; }
    }
    //
    //  public factory
    //
    public static BoolExpr CreateAnd(BoolExpr left, BoolExpr right)
    {
        return new BoolExpr(BOP.AND, left, right);
    }
    public static BoolExpr CreateNot(BoolExpr child)
    {
        return new BoolExpr(BOP.NOT, child, null);
    }
    public static BoolExpr CreateOr(BoolExpr left, BoolExpr right)
    {
        return new BoolExpr(BOP.OR, left, right);
    }
    public static BoolExpr CreateBoolVar(String str)
    {
        return new BoolExpr(str);
    }
    public BoolExpr(BoolExpr other)
    {
        // No share any object on purpose
        _op = other._op;
        _left  = other._left  == null ? null : new BoolExpr(other._left);
        _right = other._right == null ? null : new BoolExpr(other._right);
        _lit = new StringBuilder(other._lit).ToString();
    }
    //
    //  state checker
    //
    Boolean IsLeaf()
    {
        return (_op == BOP.LEAF);
    }
    Boolean IsAtomic()
    {
        return (IsLeaf() || (_op == BOP.NOT && _left.IsLeaf()));
    }
}

我应该使用什么算法来解析像"￢((A ∧ B) ∨ C ∨ D)"这样的输入布尔表达式字符串，并将其加载到上面的类中？

如何解析布尔表达式并将其加载到类中

TL；DR：如果你想看代码，跳到答案的第二部分。

我会从表达式中构建一个树来解析，然后首先遍历它的深度。你可以参考维基百科上关于二进制表达式树的文章来了解我的建议。

  1. 首先添加省略的可选括号，使下一步更容易
  2. 当您读取任何不是运算符或括号的内容时，请创建LEAF类型的节点
  3. 读取任何运算符（在您的情况下为not、and、or）时，创建相应的运算符节点
  4. 二元运算符将上一个和下一个节点作为子节点，一元运算符只获取下一个

因此，对于您的示例￢((A ∧ B) ∨ C ∨ D)，算法如下所示：

￢((A ∧ B) ∨ C ∨ D)变为￢(((A ∧ B) ∨ C) ∨ D)

  1. 创建一个NOT节点，它将获得以下作为子节点打开paren的结果
  2. 创建A LEAF节点、AND节点和B LEAF节点。CCD_ 15有CCD_ 16和CCD_
  3. 创建OR节点，它将先前创建的AND作为子节点，并为C创建新的LEAF节点
  4. 创建OR节点，它将先前创建的OR和D的新节点作为子节点

在这一点上，你的树看起来是这样的：

  NOT
   |
  OR
  /'
 OR D
 / '
AND C
/'
A B

然后可以添加一个Node.EEvaluate（）方法，该方法根据其类型递归求值（这里可以使用多态性）。例如，它可能看起来像这样：

class LeafEx {
    bool Evaluate() {
        return Boolean.Parse(this.Lit);
    }
}
class NotEx {
    bool Evaluate() {
        return !Left.Evaluate();
    }
}
class OrEx {
    bool Evaluate() {
        return Left.Evaluate() || Right.Evaluate();
    }
}

等等。要获得表达式的结果，您只需要调用

bool result = Root.Evaluate();

好吧，既然这不是一项任务，而且它实际上是一件有趣的事情，我就继续做下去。我将在这里发布的一些代码与我之前描述的内容无关（有些部分缺失），但我将把答案的顶部留作参考（希望没有错！））。

请记住，这远不是最佳的，而且我努力不修改您提供的BoolExpr类。修改它可以减少代码量。也没有任何错误检查。

以下是的主要方法

static void Main(string[] args)
{
    //We'll use ! for not, & for and, | for or and remove whitespace
    string expr = @"!((A&B)|C|D)";
    List<Token> tokens = new List<Token>();
    StringReader reader = new StringReader(expr);
    //Tokenize the expression
    Token t = null;
    do
    {
        t = new Token(reader);
        tokens.Add(t);
    } while (t.type != Token.TokenType.EXPR_END);
    //Use a minimal version of the Shunting Yard algorithm to transform the token list to polish notation
    List<Token> polishNotation = TransformToPolishNotation(tokens);
    var enumerator = polishNotation.GetEnumerator();
    enumerator.MoveNext();
    BoolExpr root = Make(ref enumerator);
    //Request boolean values for all literal operands
    foreach (Token tok in polishNotation.Where(token => token.type == Token.TokenType.LITERAL))
    {
        Console.Write("Enter boolean value for {0}: ", tok.value);
        string line = Console.ReadLine();
        booleanValues[tok.value] = Boolean.Parse(line);
        Console.WriteLine();
    }
    //Eval the expression tree
    Console.WriteLine("Eval: {0}", Eval(root));
    Console.ReadLine();
}

标记化阶段为表达式的所有标记创建一个Token对象。它有助于将解析与实际算法分离。以下是执行此操作的Token类：

class Token
{
    static Dictionary<char, KeyValuePair<TokenType, string>> dict = new Dictionary<char, KeyValuePair<TokenType, string>>()
    {
        {
            '(', new KeyValuePair<TokenType, string>(TokenType.OPEN_PAREN, "(")
        },
        {
            ')', new KeyValuePair<TokenType, string>(TokenType.CLOSE_PAREN, ")")
        },
        {
            '!', new KeyValuePair<TokenType, string>(TokenType.UNARY_OP, "NOT")
        },
        {
            '&', new KeyValuePair<TokenType, string>(TokenType.BINARY_OP, "AND")
        },
        {
            '|', new KeyValuePair<TokenType, string>(TokenType.BINARY_OP, "OR")
        }
    };
    public enum TokenType
    {
        OPEN_PAREN,
        CLOSE_PAREN,
        UNARY_OP,
        BINARY_OP,
        LITERAL,
        EXPR_END
    }
    public TokenType type;
    public string value;
    public Token(StringReader s)
    {
        int c = s.Read();
        if (c == -1)
        {
            type = TokenType.EXPR_END;
            value = "";
            return;
        }
        char ch = (char)c;
        if (dict.ContainsKey(ch))
        {
            type = dict[ch].Key;
            value = dict[ch].Value;
        }
        else
        {
            string str = "";
            str += ch;
            while (s.Peek() != -1 && !dict.ContainsKey((char)s.Peek()))
            {
                str += (char)s.Read();
            }
            type = TokenType.LITERAL;
            value = str;
        }
    }
}

在这一点上，在主方法中，您可以看到我按波兰符号顺序转换了标记列表。它使树的创建变得更加容易，我为此使用了调车场算法的修改实现：

static List<Token> TransformToPolishNotation(List<Token> infixTokenList)
{
    Queue<Token> outputQueue = new Queue<Token>();
    Stack<Token> stack = new Stack<Token>();
    int index = 0;
    while (infixTokenList.Count > index)
    {
        Token t = infixTokenList[index];
        switch (t.type)
        {
            case Token.TokenType.LITERAL:
                outputQueue.Enqueue(t);
                break;
            case Token.TokenType.BINARY_OP:
            case Token.TokenType.UNARY_OP:
            case Token.TokenType.OPEN_PAREN:
                stack.Push(t);
                break;
            case Token.TokenType.CLOSE_PAREN:
                while (stack.Peek().type != Token.TokenType.OPEN_PAREN)
                {
                    outputQueue.Enqueue(stack.Pop());
                }
                stack.Pop();
                if (stack.Count > 0 && stack.Peek().type == Token.TokenType.UNARY_OP)
                {
                    outputQueue.Enqueue(stack.Pop());
                }
                break;
            default:
                break;
        }
        ++index;
    }
    while (stack.Count > 0)
    {
        outputQueue.Enqueue(stack.Pop());
    }
    return outputQueue.Reverse().ToList();
}

经过此转换后，我们的令牌列表将变为NOT, OR, OR, C, D, AND, A, B。

现在，我们已经准备好创建表达式树了。Polish Notation的属性允许我们在进行时遍历令牌列表并递归地创建树节点（我们将使用您的BoolExpr类）：

static BoolExpr Make(ref List<Token>.Enumerator polishNotationTokensEnumerator)
{
    if (polishNotationTokensEnumerator.Current.type == Token.TokenType.LITERAL)
    {
        BoolExpr lit = BoolExpr.CreateBoolVar(polishNotationTokensEnumerator.Current.value);
        polishNotationTokensEnumerator.MoveNext();
        return lit;
    }
    else
    {
        if (polishNotationTokensEnumerator.Current.value == "NOT")
        {
            polishNotationTokensEnumerator.MoveNext();
            BoolExpr operand = Make(ref polishNotationTokensEnumerator);
            return BoolExpr.CreateNot(operand);
        }
        else if (polishNotationTokensEnumerator.Current.value == "AND")
        {
            polishNotationTokensEnumerator.MoveNext();
            BoolExpr left = Make(ref polishNotationTokensEnumerator);
            BoolExpr right = Make(ref polishNotationTokensEnumerator);
            return BoolExpr.CreateAnd(left, right);
        }
        else if (polishNotationTokensEnumerator.Current.value == "OR")
        {
            polishNotationTokensEnumerator.MoveNext();
            BoolExpr left = Make(ref polishNotationTokensEnumerator);
            BoolExpr right = Make(ref polishNotationTokensEnumerator);
            return BoolExpr.CreateOr(left, right);
        }
    }
    return null;
}

现在我们是金子！我们有一个表示表达式的表达式树，因此我们将询问用户每个文字操作数的实际布尔值，并计算根节点（它将根据需要递归地计算树的其余部分）。

下面是我的Eval函数，请记住，如果我修改了BoolExpr类，我会使用一些多态性来使它更干净。

static bool Eval(BoolExpr expr)
{
    if (expr.IsLeaf())
    {
        return booleanValues[expr.Lit];
    }
    if (expr.Op == BoolExpr.BOP.NOT)
    {
        return !Eval(expr.Left);
    }
    if (expr.Op == BoolExpr.BOP.OR)
    {
        return Eval(expr.Left) || Eval(expr.Right);
    }
    if (expr.Op == BoolExpr.BOP.AND)
    {
        return Eval(expr.Left) && Eval(expr.Right);
    }
    throw new ArgumentException();
}

如预期的那样，用A, B, C, D的值false, true, false, true分别喂养我们的测试表达式￢((A ∧ B) ∨ C ∨ D)，得到结果false。

从算法的角度来看，要解析表达式，需要一个堆栈。

我们使用两步算法：

  1. 乐星

lexing的目的是获取"关键字"、"标识符"answers"分隔符"：-关键字是"if"，然后是"else"（"）"/''"/"等。。。-在您的案例中，标识符是"A"、"B"、"C"等。。。-分隔符是空白、制表、行尾、文件尾等…

词法由使用自动机组成。在lexing中，您将逐个字符地读取输入字符串。当你输入一个与你的关键字、标识符、分隔符兼容的字符时，你就开始了一个字符序列。当你使用分隔符时，你会停止序列，在字典中查找序列是否为关键字（如果不是，则为标识符）；然后将tuple[sequence，keyword或identifier/class]放在堆栈上。

我把小关键字"（"也可以看作分隔符的情况留给您。

  1. 解析

语法分析与语法相似。在您的情况下，唯一需要检查的规则是逗号和二进制操作，以及一个简单的标识符。

正式名称：

expression::
  '(' expression ')'
  expression /' expression
  expression '/ expression
  identifier

这可以通过递归函数来编写。首先反转堆栈，然后：

myParseExpression(stack, myC#ResultObject)
{
    if(stack.top = kewyord.'('  )
         then myParseOpenComma(all stack but top, myC#ResultObject)
    if(stack.top = keyword.'/'')
         then myParseBinaryAnd(stack, myC#ResultObject)
}
myParseOpenComma(stack, myC#ResultObject)
{
 ...
}
myParseBinaryAnd(stack, myC#ResultObject)
{
 myNewRigthPartOfExpr = new C#ResultObject
 myParseExpression(stack.top, myNewRigthPartOfExpr)
 remove top of stack;
 myNewLeftPartOfExpr = new C#ResultObject
 myParseExpression(stack.top, myNewLeftPartOfExpr)
 C#ResultObject.add("AND", myNewRigthPartOfExpr, myNewLeftPartOfExpr)
}
...

有多个函数彼此共享递归。作为练习，试着加否定词。

  • Lexing传统上是由lexer完成的（就像lex工具一样）
  • 传统上，解析是由解析器完成的（就像野牛工具一样）
  • 工具允许编写这些函数，更像我在形式表达式中所做的

思想方面是程序编译的基础。编码这些东西会让你进步很多，因为它既困难又基本。

相关文章：