布尔代数表达在C＃中的表达转换

Question

我正在努力将布尔代数表达式转换为这样的东西

  NOT(a AND b) = (NOT a) OR (NOT b)
  NOT (a OR b) = (NOT a) AND (NOT b)
  a AND NOT (b AND c) = (EQ a) AND ( ( NOT b) OR ( NOT c) )

，但是，以某种方式在某些条件下不起作用，例如

  NOT a AND b = (NOT a) AND (EQ b)
  a AND NOT b AND NOT c = (EQ a) AND (NOT b) AND (NOT c)

以下是转换的逻辑。我做错了吗？

    public string ExpressionConversion(string expression)

    {
        string finalVal = null;
        string currentToken = "";
        bool isNotFound = false;
        List<string> strList = new List<string>();
        StringHelper stringHelper = new StringHelper();
        var values = stringHelper.CleverSplit(expression, ' ', false, true); //function which splits all the elements in the expression
        for (int j = 0; j < values.Length; j++)
        {
            currentToken = values[j].Trim();
            if (string.IsNullOrEmpty(currentToken.Trim()))
                continue;

            if ((j > 0) && currentToken.StartsWith("AND") && values[j - 1].StartsWith("AND"))
                continue;
            if (currentToken.Contains("NOT"))
            {
                isNotFound = true;
                continue;
            }
            if (currentToken.StartsWith("("))
                strList.Add(currentToken);
            else if (currentToken.StartsWith(")"))
            {
                strList.Add(currentToken);
                isNotFound = false;
            }
            else if (currentToken.StartsWith("AND"))
            {
                if (isNotFound)
                    strList.Add(" OR ");
                else
                    strList.Add(" AND ");
            }
            else if (currentToken.StartsWith("OR"))
            {
                if (isNotFound)
                    strList.Add(" AND ");
                else
                    strList.Add(" OR ");
            }
            else
            {
                if (isNotFound)
                {
                    strList.Add("( NOT " + currentToken + " )");
                    if (!expression.Contains("("))
                        isNotFound = false;
                }
                else
                    strList.Add("( EQ " + currentToken + " )");
            }
        }
        if (strList.Count > 0)
            finalVal = string.Join(" ", strList);
        return finalVal;
    }

Answer 1

如果您去适当的解析器，您的生活可能最容易。

注意：这里的错误处理非常可怕，并且没有单位测试。您需要改进这些！

---

我们首先将输入标记为（，），变量，操作员等。

首先，让我们定义我们的令牌集。我们将使用一组所有实现相同标记接口的类，并将使用Singleton实例，在该实例中，令牌无需保留任何其他信息。我还将作弊并在操作员令牌上放置优先级和关联信息，我们将在一分钟内使用：

public interface IToken
{
}

public class LeftParenToken : IToken
{
    public static LeftParenToken Instance { get; } = new LeftParenToken();
    private LeftParenToken() { }
    public override string ToString() => "(";
}

public class RightParenToken : IToken
{
    public static RightParenToken Instance { get; } = new RightParenToken();
    private RightParenToken() { }
    public override string ToString() => ")";
}

public abstract class OperatorToken : IToken
{
    public int Precedence { get; }
    public bool IsLeftAssociative { get; }
    protected OperatorToken(int precedence, bool isLeftAssociative) => (Precedence, IsLeftAssociative) = (precedence, isLeftAssociative);
}

public class AndToken : OperatorToken
{
    public static AndToken Instance { get; } = new AndToken();
    private AndToken() : base(1, true) { }
    public override string ToString() => "AND";
}

public class OrToken : OperatorToken
{
    public static OrToken Instance { get; } = new OrToken();
    private OrToken() : base(1, true) { }
    public override string ToString() => "OR";
}

public class EqToken : OperatorToken
{
    public static EqToken Instance { get; } = new EqToken();
    private EqToken() : base(2, false) { }
    public override string ToString() => "EQ";
}

public class NotToken : OperatorToken
{
    public static NotToken Instance { get; } = new NotToken();
    private NotToken() : base(2, false) { }
    public override string ToString() => "NOT";
}

public class VariableToken : IToken
{
    public string Name { get; }
    public VariableToken(string name) => Name = name;
    public override string ToString() => Name;
}

通过定义的，我们的令牌器非常简单：

public class Tokeniser
{
    private static readonly Regex tokenRegex = new Regex(@"(\(|\)|\w+)\s*");

    private readonly string input;
    private int position;

    public Tokeniser(string input)
    {
        this.input = input;
    }

    public IToken? Next()
    {
        if (position == input.Length)
            return null;

        var match = tokenRegex.Match(input, position);
        if (!match.Success || match.Index != position)
        {
            throw new Exception($"Unexpected token at start of '{input.Substring(position)}'");
        }

        string token = match.Groups[1].Value;
        position += match.Length;

        return token switch
        {
            "(" => LeftParenToken.Instance,
            ")" => RightParenToken.Instance,
            "AND" => AndToken.Instance,
            "OR" => OrToken.Instance,
            "NOT" => NotToken.Instance,
            "EQ" => EqToken.Instance,
            _ => new VariableToken(token),
        };
    }
}

我们只是浏览输入，在每个步骤中匹配正则是。正则吞咽了空格（因此我们不需要修剪自己）。任何不是我们已知的关键字之一的东西都是一个变量：这意味着您可以具有称为Eg +的变量。

---

我们的Tokanizer可以将字符串Eg A和（B和B）解析到令牌a，和，（（，b，和，不是，c，）。现在，我们想将其解析为AST。

一种相当简单的方法是首先使用“ nofollow noreferrer”> >。

在后缀表达式中，操作员在操作数之后出现。因此，A + B变为ab +。为了处理此操作，您会做一些堆栈。当您看到操作数时，将其推到堆栈上。当您看到操作员时，您会弹出多大参数，应用操作员，然后将结果推到堆栈上。

因此，表达式a而不是（不是b和c）变为ab而不是c，而不是，即：

操作	堆栈
push a	[a]
push b	[a，b]
不是	[a，not b]
push c	[a，not b，c]
和	[a，（不是b）和c]
<代码>不是	[a，不是（不是b和c）]
和	[a而不是（不是B和C）]

关于此事的可爱之处在于，您不必担心括号：您只需通过令牌即可在后缀表达式代币中行走并随身携带。

public class Parser
{
    public IEnumerable<IToken> Shunt(Tokeniser tokeniser)
    {
        var operators = new Stack<IToken>();
        
        bool lastTokenWasVariable = false;

        while (tokeniser.Next() is { } token)
        {
            if (lastTokenWasVariable && token is VariableToken or NotToken)
            {
                // A variable after a variable, or a NOT after a variable, has an implicit AND between them
                foreach (var t in ProcessOperator(AndToken.Instance))
                {
                    yield return t;
                }
            }
            
            switch (token)
            {
                case VariableToken variable:
                    yield return variable;
                    break;
                case OperatorToken op:
                    foreach (var t in ProcessOperator(op))
                    {
                        yield return t;
                    }
                    break;
                case LeftParenToken:
                    operators.Push(token);
                    break;
                case RightParenToken:
                    while (operators.TryPeek(out var peek) && peek is not LeftParenToken)
                    {
                        if (operators.Count == 0)
                        {
                            throw new Exception("Count not find matching '(' for ')'");
                        }
                        operators.Pop();
                        yield return peek;
                    }
                    if (!operators.TryPop(out var pop) || pop is not LeftParenToken)
                    {
                        throw new Exception("Expected a '(' at the top of the operators stack");
                    }
                    break;
            }
            
            lastTokenWasVariable = token is VariableToken;
        }

        while (operators.TryPop(out var op))
        {
            if (op is LeftParenToken)
            {
                throw new Exception("Unexpected '('");
            }
            yield return op;
        }
        
        IEnumerable<IToken> ProcessOperator(OperatorToken op1)
        {
            while (operators.TryPeek(out var peek) && peek is OperatorToken op2 && (op1.IsLeftAssociative ? op2.Precedence >= op1.Precedence : op2.Precedence > op1.Precedence))
            {
                operators.Pop();
                yield return op2;
            }
            operators.Push(op1);
        }
    }
}

这几乎是 algorithm on wikipedia ）。

唯一的复杂性是您需要支持Eg A B或a而不是b的输入，而不是表示a和b and b and a和b分别。分流码算法无法应付本地：它期望操作数之间的操作员。因此，我们将其入侵：如果我们看到一个直接遵循另一个变量的变量或而不是，我们将假装首先看到and。

---

下一步涉及将其纳入AST。我们将使用一棵树，其中运算符和变量都由节点表示。一个变量节点没有任何孩子：它只是知道变量名称。单一操作员（不是或eq）有一个孩子。二进制运算符（和或或）有两个孩子，这是两件事是被安排或或者在一起的。

我们将以与代币相同的方式定义这些定义，并实现大量类的类。

我们还将添加一个倒置方法：在节点上实现时，它将返回该节点的倒置版本，并应用de Morgan的定律。因此，反转eq节点会导致与倒置子的节点节点（反之亦然）；反转和或或分别以或/和的形式导致其两个孩子倒置。

这意味着反相eq a导致而不是，反转eq a和eq b导致in 而不是a或b代码>等。

public interface INode
{
    INode Invert();
}

public class BinaryOperatorNode : INode
{
    public OperatorToken Operator { get; }
    public INode Left { get; }
    public INode Right { get; }

    public BinaryOperatorNode(OperatorToken op, INode right, INode left) => (Operator, Right, Left) = (op, right, left);

    public INode Invert()
    {
        return Operator switch
        {
            AndToken => new BinaryOperatorNode(OrToken.Instance, Right.Invert(), Left.Invert()),
            OrToken => new BinaryOperatorNode(AndToken.Instance, Right.Invert(), Left.Invert()),
            _ => throw new Exception($"Unexpected binary operator type {Operator}"),
        };
    }
}

public class UnaryOperatorNode : INode
{
    public OperatorToken Operator { get; }
    public INode Child { get; }
    public UnaryOperatorNode(OperatorToken op, INode child) => (Operator, Child) = (op, child);
    
    public INode Invert()
    {
        return Operator switch
        {
            NotToken => new UnaryOperatorNode(EqToken.Instance, Child.Invert()),
            EqToken => new UnaryOperatorNode(NotToken.Instance, Child.Invert()),
            _ => throw new Exception($"Unexpected unary operator type {Operator}"),
        };
    }
}

public class VariableNode : INode
{
    public VariableToken Variable { get; }
    public VariableNode(VariableToken variable) => Variable = variable;

    public INode Invert()
    {
        return this;
    }
}

就此，我们可以编写我们的小方法来生成AST。这几乎可以用我上面描述的堆栈来完成。但是，每次看到变量令牌时，我们都会在eq节点中潜入节点 - 因此，将始终使用指向它的eq节点创建变量。当我们看到而不是令牌时，我们将仅将当前堆栈上的任何内容转动：如果是eq节点，它将自身变成not not < /代码>节点。

public class Parser
{
    public INode BuildAst(IEnumerable<IToken> tokens)
    {
        var stack = new Stack<INode>();

        foreach (var token in tokens)
        {
            switch (token)
            {
                case VariableToken variable:
                    stack.Push(new UnaryOperatorNode(EqToken.Instance, new VariableNode(variable)));
                    break;

                case AndToken:
                case OrToken:
                    if (stack.Count < 2)
                    {
                        throw new Exception($"Expected 2 parameters for operator {token}, got fewer");
                    }
                    stack.Push(new BinaryOperatorNode((OperatorToken)token, stack.Pop(), stack.Pop()));
                    break;

                case EqToken:
                    // We treat EQ as a no-op: we'll add it when we add its variable
                    break;

                case NotToken:
                    if (stack.Count < 1)
                    {
                        throw new Exception($"Expected 1 parameter for operator {token}, got fewer");
                    }
                    // If we encounter a 'not', we invert the current tree
                    stack.Push(stack.Pop().Invert());
                    break;
            }
        }
        
        if (stack.Count != 1)
        {
            throw new Exception("Unexpected leftover tokens");
        }

        return stack.Pop();
    }
}

---

最后，我们需要将AST渲染到字符串。我们将简单地递归依次访问每个节点来做到这一点。

• 如果是变量，请将名称添加到结果。
• 如果是一元运算符，请将其添加到括号内的结果中，然后访问其操作的任何操作，例如（不是＆lt;访问Child＆gt;）。
• 如果是二进制操作员，我们将其左孩子添加到结果中，然后将操作员，然后将其添加到合适的孩子。如果两个孩子本身都是二进制操作员，我们将把它包裹在括号中。

这意味着：

   AND
  /  \
 a    b

将其呈现为a和b，但：

   AND
  /   \
 a     AND
      /   \
     b     c

以a和（b and c）渲染。

public class Renderer
{
    public string Render(INode rootNode)
    {
        var sb = new StringBuilder();

        Visit(rootNode);

        void Visit(INode node)
        {
            switch (node)
            {
                case BinaryOperatorNode op:
                    VisitWithParens(op.Left);
                    sb.Append($" {op.Operator} ");
                    VisitWithParens(op.Right);
                    break;

                case UnaryOperatorNode op:
                    sb.Append($"({op.Operator} ");
                    Visit(op.Child);
                    sb.Append(")");
                    break;

                case VariableNode variable:
                    sb.Append(variable.Variable);
                    break;
            }
        }

        void VisitWithParens(INode node)
        {
            if (node is BinaryOperatorNode)
            {
                sb.Append("( ");
            }
            Visit(node);
            if (node is BinaryOperatorNode)
            {
                sb.Append(" )");
            }
        }

        return sb.ToString();
    }
}

就是这样！将它们拼接在一起：

var tokeniser = new Tokeniser("b NOT a c");
var parser = new Parser();
var tokens = parser.Shunt(tokeniser);
var ast = parser.BuildAst(tokens);
var renderer = new Renderer();
Console.WriteLine(renderer.Render(ast));

在dotnetfiddle.net.net上看到它。