c# - bool 代数表达式分解

Question

我正在为一个项目用c创建一个布尔代数简化器。为了简化布尔代数表达式，我采用以下方法：
1）简化每个变量的NOT，并在适用的情况下应用德摩根定律
2）简化表达式中的括号（如果有）
3）展开表达式中可以展开的任何括号
4）简化表达式中的每个项，例如，对于表达式A+B•A，B•A将是一个项。术语被拆分，因此每个术语只包含一个gate-and，or，xor。NOT应用于这些变量，并在与数组中每个变量的索引相对应的列表中表示。例如，nots[0]包含表达式中第一个变量上的nots数。在我的程序中，此时没有变量通过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。我被允许在我的项目中使用来自其他人的代码，只要我花时间去理解它，在必要的地方修改它并提到这一点，这样我就不会作弊。
上面的一些代码可以放在子程序中，但我目前正试图在将其缩短为单独的子程序之前获得一些工作代码。

Answer 1

你说：
警告：这是可怕的编程，因为我缺乏经验。
这是正确的。然后你说：
上面的一些代码可以放在子例程中，但我目前正在尝试获取一些工作代码，然后再将其缩短为单独的子例程。
这就是为什么你的代码是可怕的。首先将代码分解为子例程。然后为这些子例程编写测试用例，直到您100%确信该子例程是正确的。你将有一个工具，你可以用来做一个更复杂的程序。
但那只是代码布局。您的基本问题是，您正在编写一个分析器，该分析器在lexer的输出上工作，但您忘记编写解析器。
以下是事情发生的顺序：
您有一个包含表达式的字符串："A+B•A"例如。
你写了一本词典。lexer接受一个字符串并生成一个令牌列表。
什么是代币？他们是：

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) { ... }

编写方法后，为其编写扩展测试用例。你需要确保你的lexer是完全可靠的。
好的，我们现在有一个令牌列表。下一个问题是解析它们。解析接受一个令牌列表并生成一个树。
树中的节点是什么？

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"，那么lexer会说 LPAREN, IDENTIFIER(A), OR, NOT, IDENTIFIER(B), RPAREN, AND, IDENTIFIER(C)。然后解析器从lexer获取列表并生成

         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
Or左侧或右侧的 True可替换为 True
Or左边的 False可以被右边的替换。
And两边都有 False是 False
等等。必须将每个优化表示为对解析树的操作。用自己的方法编写每个优化。
练习：解析树上的因子优化是什么？这可能是一个出人意料的难题，所以在实现完整算法之前，请尝试给出一个简化版本。
高级练习：解析树优化器是double dispatch的一个例子，因为驱动方法动作的因素有两个：（1）节点的类型是什么，和（2）优化器的动作是什么。C不支持本机双重分派。您能使用visitor模式优雅地实现这个模式而不需要复制大量代码吗？
所以写一大堆这样的方法：

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

运行它们直到树完全优化。
再次，用自己的方法编写每个优化，并为每个方法编写测试用例，直到您确定每个优化都是正确的。
现在养成好习惯。广泛的测试节省时间。当我还是个学生的时候，我看到同学们整夜都在寻找语法分析器中的错误。如果他们早点写测试用例，他们就不会整夜都在试图把bug弄出来。
让我们看一个例子：

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;
}

研究一下执行情况。确保你理解它的工作原理。
练习：你能优化我糟糕的实现吗？这样，如果优化没有发现任何变化，它就不会分配内存了。
最后，您需要编写一个将优化的解析树转换回字符串的方法。在 ToString上执行 ParseNode。
现在您的程序是：

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

你完了。忙吧，你有很多工作要做，但每一步都是可行的。
一些附加建议：
使解析树不可变。优化器不会重写树。优化器将旧树单独留下，并生成新树作为其输出。
在优化布尔代数时，必须注意，每次优化都不会撤消以前任何优化的进度。你可以进入一个循环，其中一个优化扩展了一个术语，然后下一个优化再次将其退出，然后再次扩展，依此类推，直到永远。