布尔代数表达式因式分解

Question

我正在用C#为一个项目创建一个布尔代数简化器。为了简化布尔代数表达式，我采取以下方法：

1) 简化每个变量上的 NOT，并在适用的情况下应用 De Morgan 定律

2) 简化表达式中的括号（如果有的话）

3) 展开可以展开的表达式中的任何括号

4) 简化表达式中的每个项。例如，对于表达式 A+B•A，B•A 将是一个项。将这些变量应用 NOT，并在与数组中每个变量的索引相对应的列表中表示。例如，Nots [0] 包含表达式中第一个变量上的 NOT 的数量。在程序的这一点上，没有通过 NOT 门连接任何变量。

5) 在可能的情况下进行因式分解

6) 如果表达式无法因式分解，则已经简化。如果已经因式分解，则从步骤 2 开始重复直到当表达式通过这些步骤时不再改变。

我无法创建适用于所有/大多数情况的因式分解子程序。我已经创建了一个因式分解子程序并将其放在下面。我尝试让它仅扩展最多两个括号，并且这些括号不包含括号，以使我的子程序更容易创建。然而，对我来说创建这样的算法是相当困难的。

如果有人能够提供一些伪代码，或者解释如何创建这样的算法，指出我的代码中的错误，甚至提供一些我可以分析和理解的代码，我将非常感激。下面显示了代码：（警告：由于缺乏经验，它是可怕的编程。）

private bool Factorise(ref List<string> Expression, ref List<int> NOTsNew)
{
        string PreviousExpression = convertexpressionlisttostring(Expression);
        // loop and get each indiviual variable - no duplicates 
        // loop through expression for every variable and see if it occurs more than once 

        List<List<string>> itemsthatappearwithinexpression = new List<List<string>>();
        List<string> charactersthatappearwithinexpression = new List<string>();
        List<string> Notsofcharactersthathappearwithinexpression = new List<string>();
        List<string> numberoftimescharacterappears = new List<string>();
        List<string> positionofitemswithinexpression = new List<string>();
        itemsthatappearwithinexpression.Add(charactersthatappearwithinexpression);
        itemsthatappearwithinexpression.Add(Notsofcharactersthathappearwithinexpression);
        itemsthatappearwithinexpression.Add(positionofitemswithinexpression);
        itemsthatappearwithinexpression.Add(numberoftimescharacterappears);

        for (int i = 0; i < Expression.Count; i++)
        {
            if (Expression[i] != "•" && Expression[i] != "+" && Expression[i] != "⊕")
            {
                if (itemsthatappearwithinexpression[0].Count == 0)
                {
                    itemsthatappearwithinexpression[0].Add(Expression[i]);
                    itemsthatappearwithinexpression[1].Add(NOTsNew[i].ToString());
                    itemsthatappearwithinexpression[2].Add(i.ToString());
                }
                bool matched = false;
                for (int y = 0; y < itemsthatappearwithinexpression[0].Count; y++)
                {
                    if (itemsthatappearwithinexpression[0][y] == Expression[i] && itemsthatappearwithinexpression[1][y] == NOTsNew[i].ToString())
                    {
                        matched = true;
                        break;
                    }
                }
                if (!matched)
                {
                    itemsthatappearwithinexpression[0].Add(Expression[i]);
                    itemsthatappearwithinexpression[1].Add(NOTsNew[i].ToString());
                    itemsthatappearwithinexpression[2].Add(i.ToString());
                }
            }

        }
        for (int x = 0; x < itemsthatappearwithinexpression[0].Count; x++)
        {
            int occurances = 1;
            for (int c = 0; c < Expression.Count; c++)
            {
                int position = int.Parse(itemsthatappearwithinexpression[2][x]);
                if (NOTsNew[c] == NOTsNew[position] && c != position && itemsthatappearwithinexpression[0][x] == Expression[c])
                {
                    occurances++;
                }
            }
            itemsthatappearwithinexpression[3].Add(occurances.ToString());
        }
        for (int i = 0; i < itemsthatappearwithinexpression[0].Count; i++)
        {
            if (i < itemsthatappearwithinexpression[0].Count - 1)
            {
                if (itemsthatappearwithinexpression[3][i] == itemsthatappearwithinexpression[3][i + 1] && int.Parse(itemsthatappearwithinexpression[2][i]) == (int.Parse(itemsthatappearwithinexpression[2][i + 1]) - 2))
                {
                    itemsthatappearwithinexpression[0][i] = itemsthatappearwithinexpression[0][i].ToString() + itemsthatappearwithinexpression[0][i + 1].ToString(); // chars, nots, position, occurances
                    itemsthatappearwithinexpression[1][i] = itemsthatappearwithinexpression[1][i].ToString() + itemsthatappearwithinexpression[1][i + 1].ToString(); // Nots[0]

                    itemsthatappearwithinexpression[0].RemoveAt(i + 1);
                    itemsthatappearwithinexpression[1].RemoveAt(i + 1);
                    itemsthatappearwithinexpression[2].RemoveAt(i + 1);
                    itemsthatappearwithinexpression[3].RemoveAt(i + 1);
                }
            }
        }
        List<int> positionsoffirstcharinmatches = new List<int>();
        string factorisedexpression = "";
        bool donextthing = false;
        List<int> NOTsinfactorisation = new List<int>();

        for (int d = 0; d < itemsthatappearwithinexpression[0].Count; d++)
        {
            int counter = 0;
            bool singularexpansion = false;
            if (itemsthatappearwithinexpression[0][d].Length == 1)
            {
                singularexpansion = true;
            }
            if (int.Parse(itemsthatappearwithinexpression[3][d]) > 1)
            {
                for (int i = 0; i < Expression.Count; i++)
                {
                    bool Continue = false;
                    if (singularexpansion && Expression[i] == itemsthatappearwithinexpression[0][d] && NOTsNew[i] == NOTsNew[int.Parse(itemsthatappearwithinexpression[2][d])])
                    {
                        Continue = true;
                    }
                    if (i+2 <= Expression.Count-1 && !singularexpansion && Expression[i] == itemsthatappearwithinexpression[0][d][0].ToString() && Expression[i+2] == itemsthatappearwithinexpression[0][d][1].ToString() && NOTsNew[i] == int.Parse(itemsthatappearwithinexpression[1][d][0].ToString()) && NOTsNew[i+2] == int.Parse(itemsthatappearwithinexpression[1][d][1].ToString()))
                    {
                        Continue = true;
                    }
                    donextthing = false;
                    if (Continue)
                    {
                        if (i != 0)
                        {
                            if (Expression[i - 1] == "•")
                            {
                                positionsoffirstcharinmatches.Add(i - 2);
                                if (counter == 0)
                                {
                                    if (singularexpansion)
                                    {

                                        factorisedexpression += itemsthatappearwithinexpression[0][d] + "•(" + Expression[i - 2] + Expression[i - 3];
                                        NOTsinfactorisation.Add(int.Parse(itemsthatappearwithinexpression[1][d]));
                                        NOTsinfactorisation.Add(0);
                                        NOTsinfactorisation.Add(0);
                                        NOTsinfactorisation.Add(NOTsNew[i - 2]);
                                        NOTsinfactorisation.Add(0);
                                        counter++;
                                    }
                                    else
                                    {
                                        positionsoffirstcharinmatches.Add(i);
                                        factorisedexpression += itemsthatappearwithinexpression[0][d][0] + "•" + itemsthatappearwithinexpression[0][d][1] + "•(" + Expression[i - 2] + Expression[i - 3];
                                        //string NOTsOfAdjacentVariables = itemsthatappearwithinexpression[1][d]; 
                                        NOTsinfactorisation.Add(int.Parse(itemsthatappearwithinexpression[1][d][0].ToString()));
                                        NOTsinfactorisation.Add(0);
                                        NOTsinfactorisation.Add(int.Parse(itemsthatappearwithinexpression[1][d][1].ToString()));
                                        NOTsinfactorisation.Add(0);
                                        NOTsinfactorisation.Add(0);
                                        NOTsinfactorisation.Add(NOTsNew[i - 2]);
                                        NOTsinfactorisation.Add(0);
                                        counter++;
                                    }

                                }
                                else
                                {
                                    if (i >= Expression.Count - 3)
                                    {
                                        factorisedexpression += Expression[i - 2] + ")";
                                        NOTsinfactorisation.Add(NOTsNew[i - 2]);
                                        NOTsinfactorisation.Add(0);
                                    }
                                    else
                                    {
                                        factorisedexpression += Expression[i + 3] + Expression[i + 2];
                                        NOTsinfactorisation.Add(0);
                                        NOTsinfactorisation.Add(NOTsNew[i + 2]);
                                    }
                                }
                            }
                            else
                            {
                                donextthing = true;
                            }
                        }
                        else
                        {
                            donextthing = true;
                        }
                        if (donextthing)
                        {
                            positionsoffirstcharinmatches.Add(i);
                            if (counter == 0)
                            {
                                if (singularexpansion)
                                {
                                    positionsoffirstcharinmatches.Add(i + 2);
                                    factorisedexpression += itemsthatappearwithinexpression[0][d] + "•(" + Expression[i + 2] + Expression[i + 3];
                                    NOTsinfactorisation.Add(int.Parse(itemsthatappearwithinexpression[1][d]));
                                    NOTsinfactorisation.Add(0);
                                    NOTsinfactorisation.Add(0);
                                    NOTsinfactorisation.Add(NOTsNew[i + 2]);
                                    NOTsinfactorisation.Add(0);
                                    counter++;
                                }
                                else
                                {
                                    bool useone = false;
                                    if (Expression[i]+Expression[i+2] == itemsthatappearwithinexpression[0][d] || Expression[i + 2] + Expression[i] == itemsthatappearwithinexpression[0][d])
                                    {
                                        useone = true;
                                    }
                                    positionsoffirstcharinmatches.Add(i+2);
                                    if (useone)
                                    {
                                        factorisedexpression += itemsthatappearwithinexpression[0][d][0] + "•" + itemsthatappearwithinexpression[0][d][1] + "•(" + "1" + Expression[i + 3];

                                    }
                                    else
                                    {
                                        factorisedexpression += itemsthatappearwithinexpression[0][d][0] + "•" + itemsthatappearwithinexpression[0][d][1] + "•(" + Expression[i + 2] + Expression[i + 3];

                                    }
                                    //string NOTsOfAdjacentVariables = itemsthatappearwithinexpression[1][d]; 
                                    NOTsinfactorisation.Add(int.Parse(itemsthatappearwithinexpression[1][d][0].ToString()));
                                    NOTsinfactorisation.Add(0);
                                    NOTsinfactorisation.Add(int.Parse(itemsthatappearwithinexpression[1][d][1].ToString()));
                                    NOTsinfactorisation.Add(0);
                                    NOTsinfactorisation.Add(0);
                                    if (useone)
                                    {
                                        NOTsinfactorisation.Add(0);
                                    }
                                    else
                                    {
                                        NOTsinfactorisation.Add(NOTsNew[i + 2]);
                                    }

                                    NOTsinfactorisation.Add(0);
                                    counter++;
                                }
                            }
                            else
                            {
                                if (i == Expression.Count - 3)
                                {

                                    if (Expression[i]+Expression[i+2] == itemsthatappearwithinexpression[0][d] || Expression[i + 2] + Expression[i] == itemsthatappearwithinexpression[0][d])
                                    {
                                        factorisedexpression += "1" + ")";
                                        NOTsinfactorisation.Add(0);

                                    }
                                    else
                                    {
                                        factorisedexpression += Expression[i + 2] + ")";
                                        NOTsinfactorisation.Add(NOTsNew[i + 2]);
                                    }
                                    NOTsinfactorisation.Add(0);
                                }
                                else
                                {
                                    factorisedexpression += Expression[i + 3] + Expression[i + 2];
                                    NOTsinfactorisation.Add(0);
                                    NOTsinfactorisation.Add(NOTsNew[i + 2]);
                                }

                            }
                        }
                    }

                }
            }
            else
            {

            }
        }
        // character • ()  --> A•B + A•C Xor A•D = A•(B+C XOR D) - find every instance of the object - get the operator before the object and  place the o
        //int n = 5; //Expression
        positionsoffirstcharinmatches = intbubblesorthightolow(positionsoffirstcharinmatches);
        List<int> PositionstoremovefromExpression = new List<int>();
        for (int i = 0; i < positionsoffirstcharinmatches.Count; i++)
        {
            if (positionsoffirstcharinmatches[i] < Expression.Count - 3)
            {
                PositionstoremovefromExpression.Add(positionsoffirstcharinmatches[i] + 3);
                PositionstoremovefromExpression.Add(positionsoffirstcharinmatches[i] + 2);
                PositionstoremovefromExpression.Add(positionsoffirstcharinmatches[i] + 1);
                PositionstoremovefromExpression.Add(positionsoffirstcharinmatches[i]);
            }
            else
            {
                PositionstoremovefromExpression.Add(positionsoffirstcharinmatches[i] + 2);
                PositionstoremovefromExpression.Add(positionsoffirstcharinmatches[i] + 1);
                PositionstoremovefromExpression.Add(positionsoffirstcharinmatches[i]);
            }

        }

        PositionstoremovefromExpression = intbubblesorthightolow(PositionstoremovefromExpression);
        PositionstoremovefromExpression = PositionstoremovefromExpression.Distinct().ToList();
        for (int i = 0; i < PositionstoremovefromExpression.Count; i++)
        {
            NOTsNew.RemoveAt(PositionstoremovefromExpression[i]);
            Expression.RemoveAt(PositionstoremovefromExpression[i]); // A • B + C • A
        }
        for (int i = 0; i < factorisedexpression.Length; i++)
        {
            try
            {
                Expression[PositionstoremovefromExpression[PositionstoremovefromExpression.Count - 1] + i] = factorisedexpression[i].ToString();
                NOTsNew[PositionstoremovefromExpression[PositionstoremovefromExpression.Count - 1] + i] = NOTsinfactorisation[i];
            }
            catch (Exception)
            {
                Expression.Add(factorisedexpression[i].ToString());
                NOTsNew.Add(NOTsinfactorisation[i]);
            }

        }
        if (PreviousExpression == convertexpressionlisttostring(Expression))
        {
            return false;
        }
        else
        {
            return true;
        }

    }

列表表达式是一个字符串列表，其中包含表达式中的每个字符。例如，对于 A + B，列表将是 ["A","+","B"]。NOTsNew 列表是前面提到的列表，其中包含每个变量上的 NOT。只要我花时间理解它，并在必要时进行调整并提及这一点，我就可以在我的项目中使用他人的代码，因此我不会作弊。 P.S. 上面的一些代码可以放入子程序中，但我目前正在尝试获得一些可工作的代码，然后将其缩短为单独的子程序。

- B.Iqbal

---

为什么你要通过引用传递 Expression？你没有在任何地方对它进行赋值。修改列表并不等同于覆盖变量。 - Jeroen van Langen

你有没有看过像Lex＆Yacc（或它们的更现代化的替代品）或类似Antlr的工具的词法分析器/解析器系统？使用一个能够正确解析输入的工具集来编写这个程序比自己编写所有代码要容易得多。 - Flydog57

@Flydog57：虽然那是务实的建议，但对于学生们，我总是鼓励他们编写自己的词法分析器和语法分析器。没有比编写自己的更好的方法来了解词法分析器和语法分析器的工作原理。布尔代数语言仅有三个运算符，每个标记都是单个字符；这是最容易进行词法分析和语法分析的语言，因此它是一个很好的起点。布尔代数词法分析器的主循环只有十几行代码，大多数解析器只是正确获取运算符优先级。 - Eric Lippert

当然。但是，我更多的是工程师（两个学位）而不是计算机科学家（0个学位）。如果我可以使用Antlr（甚至是Lex / Yac - 自90年代初以来我就没有接触过），来解析文本流而不编写词法分析器/语法分析器，那么我会很高兴（并且我得到了可靠的测试代码）。这样我写的错误就被限制在一定范围内了。 - Flydog57

Answer 1

你说：

警告：由于我缺乏经验，这是可怕的编程。

这是正确的。然后你说：

上面的一些代码可以放入子程序中，但我目前正在尝试获取一些可工作的代码，然后再将其缩短成单独的子程序。

这就是为什么你的代码很糟糕。首先将代码分解为子程序。然后为这些子程序编写测试用例，直到您对子程序的正确性有100％的信心。然后您将拥有一个可以用来创建更复杂例程的工具。

但那只是代码布局。 您的根本问题是，您正在编写适用于词法分析器输出的分析器，但您忘记编写解析器。

以下是应按顺序发生的内容：

• 您有一个包含表达式的字符串："A+B•A"。
• 您编写一个词法分析器。词法分析器接受一个字符串并产生标记列表。

什么是标记？它们是：

abstract class Token { ... }
sealed class IdentifierToken : Token { ... }
sealed class NotToken : Token { ... }
sealed class OrToken : Token { ... }
sealed class AndToken : Token { ... }
sealed class LeftParenToken : Token { ... }
sealed class RightParenToken : Token { ... }
sealed class TrueToken : Token { ... }
sealed class FalseToken : Token { ... }

所以，任务一是编写这个方法：

public static List<Token> Lexer(string s) { ... }

一旦方法编写完成，为其编写广泛的测试用例。您需要确保您的词法分析器非常可靠。

• 好了，现在我们有了一个标记列表。 下一个问题是解析它们。 解析需要一个标记列表并生成一个单独的树。

树中的节点是什么？

abstract class ParseNode { ... }
sealed class OrNode : ParseNode 
{ 
  public ParseNode Left { get; }
  public ParseNode Right { get; }
  ...
  // Or maybe IEnumerable<ParseNode> Children { get; }
  // is easier; both techniques have their strengths.
}
sealed class AndNode : ParseNode { ... }
sealed class NotNode : ParseNode { ... }
sealed class IdentifierNode : ParseNode { ... }
sealed class TrueNode : ParseNode { ... }
sealed class FalseNode : ParseNode { ... }

注意没有括号。括号在树结构中表达。

例如，如果我们有"(A+~B)*C"，那么词法分析器会生成LPAREN、IDENTIFIER(A)、OR、NOT、IDENTIFIER(B)、RPAREN、AND、IDENTIFIER(C)。然后解析器从词法分析器的列表中提取信息并生成

         And
       /     \
     Or     Id(C)
   /   \
 Id(A) Not
         |
       Id(B)

那么你的下一个任务是编写这个方法：

public static ParseNode Parser(List<Token> tokens) { ... }

再次强调，编写大量测试用例。解析器需要完美无误。

对于初学者来说，编写解析器最难的部分是正确处理运算符优先级。您需要确保A+B*C解析为A+(B*C)而不是(A+B)*C。编写语言的形式化、明确的上下文无关文法将有所帮助。例如，仅从我头脑中想出以下无歧义解析：

EXPR    : OREX
OREX    : ANDEX ORTAIL
ORTAIL  : NIL
ORTAIL  : + ANDEX ORTAIL
ANDEX   : NOTEX ANDTAIL
ANDTAIL : NIL
ANDTAIL : * NOTEX ANDTAIL
NOTEX   : CONST
NOTEX   : ( EXPR )
NOTEX   : ~ NOTEX
NOTEX   : IDENT
IDENT   : <any single letter>
CONST   : 1
CONST   : 0

不要相信我的话，自己编写语法并编写递归下降解析器来解析它。

• 现在我们有了一个解析树。这是你用来进行优化的东西。

一些例子：

• Not -> True 可以被替换为 False，反之亦然
• Not -> Not -> anything，可以被替换为 anything
• 左侧或右侧带有 True 的 Or 可以被替换为 True
• 左侧带有 False 的 Or 可以被替换为右侧的任何内容。
• 左侧或右侧带有 False 的 And 是 False

等等。你必须将每个优化表示为对解析树的操作。为每个优化编写单独的方法。

练习：什么是解析树上的因式分解优化？这可能是一个令人惊讶的难题，所以在实现完整算法之前，请尝试想出简化版。

高级练习：解析树优化器是双重分派的一个例子，因为有两个驱动方法操作的东西：(1)节点类型是什么，(2)优化器的行动是什么。C# 不支持本地双重分派。 你能使用访问者模式来优雅地实现这个模式，而不必复制很多代码吗？

所以写一堆这种形式的方法：

public static ParseNode FooOptimization(ParseNode p) { ... }
public static ParseNode BarOptimization(ParseNode p) { ... }

运行它们，直到树被完全优化。

同样，将每个优化写成自己的方法，并为每个方法编写测试用例，直到您确信每个优化都是正确的。

现在养成好习惯。广泛的测试可以节省时间。当我还是学生时，我看到同学整晚都在寻找他们解析器中的错误。如果他们早点编写了测试用例，就不会整晚找错了。

让我们来看一个例子：

public static ParseNode NotFalseOptimization(ParseNode p)
{
  if (p is NotNode n)
  {  
    // The child might itself have a Not(False) somewhere in it.
    ParseNode child = NotFalseOptimization(n.Child);
    if (child is FalseNode)
      return new TrueNode();
    else
      return new NotNode(child);
  }
  else if (p is OrNode o)
    return new OrNode(NotFalseOptimization(o.Left), NotFalseOptimization(o.Right);
  else if (p is AndNode a)
    return new AndNode(NotFalseOptimization(a.Left), NotFalseOptimization(a.Right);
  else
     return p;
}

学习实现方法。确保你了解它是如何工作的。

练习：你能优化我的糟糕实现，使其在发现没有任何变化可以改进的情况下不分配内存吗？

• 最后，您需要编写一个方法，将优化后的解析树转换回字符串。在ParseNode上实现ToString。

现在你的程序是：

static string DoItAll(string s) 
{
  var tokens = Lex(s);
  var tree = Parse(tokens);
  var optimized = Optimize(tree);
  return optimized.ToString();
}

完成了。 开始行动，你有很多工作要做，但每一步都可行。

其他建议：

• 使解析树不变。优化器不会重写该树。优化器保留旧树，并将新树作为其输出产生。

• 在优化布尔代数时，必须小心，以确保每次优化不会撤消任何先前优化的进展。你可能会陷入循环中，其中一个优化扩展了一个术语，然后下一个优化将其分解，并再次扩展，如此往复，永无止境。

- Eric Lippert