Логическая инверсия дерева символов

Question

У меня есть класс Symbol_Group, который представляет обратимое выражение природы AB(C+DE) + FG.Symbol_Group содержит List<List<iSymbol>>, где iSymbol - это интерфейс, применяемый к Symbol_Group, и Symbol.

Приведенное выше уравнение будет представлено как A,B,Sym_Grp + F,G; Sym_Grp = C + D,E, где каждый + представляет новый List<iSymbol>

Мне нужно иметь возможность инвертировать и расширять это уравнение, используя алгоритм, который может обрабатывать любое количество вложений и любое количество символов, соединенных или объединенных вместе, чтобы создать набор Symbol_Group, каждый из которых содержит уникальное расширение.Для вышеупомянутого вопроса набор ответов будет !A!F; !B!F; !C!D!F; !C!E!F; !A!G; !B!G; !C!D!G; !C!E!G;

Я знаю, что мне нужно будет использовать рекурсию, но у меня было очень мало опыта с этим.Буду признателен за любую помощь в выяснении этого алгоритма.

Answer 1

Если вам не требуется использовать List<List<iSymbol>>, я рекомендую переключиться на другую структуру класса с базовым классом (или интерфейсом) Expression и подклассами (или разработчиками) SymbolExpression, NotExpression, OrExpression и AndExpression.A SymbolExpression содержит один символ;NotExpression содержит одно Expression, а OrExpression и AndExpression содержат по два выражения в каждом.Это гораздо более стандартная структура для работы с математическими выражениями, и, вероятно, для нее проще выполнять преобразования.

С помощью приведенных выше классов вы можете моделировать любое выражение в виде двоичного дерева.Отмените выражение, заменив корень на NotExpression, чей дочерний элемент является исходным корнем.Затем обойдите дерево с помощью поиска в глубину, и всякий раз, когда вы нажимаете NotExpression, чей дочерний элемент - OrExpression или AndExpression, вы можете заменить его на AndExpression или OrExpression (соответственно)чьи дети NotExpression s, с оригинальными детьми под ними.Возможно, вы также захотите устранить двойные отрицания (найдите NotExpression s, чей ребенок - NotExpression, и удалите оба).

(Понятен ли этот ответ, вероятно, зависит от того, насколько вам удобно работатьдеревья. Дайте мне знать, если вам нужны разъяснения.)

Answer 2

Я пришел к этому более простому решению после небольшой настройки. Я надеюсь, что это поможет кому-то еще с подобной проблемой! Это структура класса (плюс несколько других свойств)

public class SymbolGroup : iSymbol
{

    public SymbolGroup(SymbolGroup Parent, SymRelation Relation)
    {
        Symbols = new List<iSymbol>();
        this.Parent = Parent;
        SymbolRelation = Relation;
        if (SymbolRelation == SymRelation.AND)
            Name = "AND Group";
        else
            Name = "OR Group";
    }

    public int Depth
    {
        get
        {
            foreach (iSymbol s in Symbols)
            {
                if (s is SymbolGroup)
                {
                    return (s as SymbolGroup).Depth + 1;
                }
            }
            return 1;
        }
    }
}

Метод инверсии также содержится в этом классе. Он заменяет нерасширенную группу в списке результатов на все расширенные результаты этого результата. Он удаляет только один уровень за раз.

    public List<SymbolGroup> InvertGroup()
    {
        List<SymbolGroup> Results = new List<SymbolGroup>();

        foreach (iSymbol s in Symbols)
        {
            if (s is SymbolGroup)
            {
                SymbolGroup sg = s as SymbolGroup;
                sg.Parent = null;
                Results.Add(s as SymbolGroup);
            }
            else if (s is Symbol)
            {
                SymbolGroup sg = new SymbolGroup(null, SymRelation.AND);
                sg.AddSymbol(s);
                Results.Add(sg);
            }
        }

        bool AllChecked = false;
        while (!AllChecked)
        {
            AllChecked = true;
            for(int i=0;i<Results.Count;i++) 
            {
                SymbolGroup result = Results[i];
                if (result.Depth > 1)
                {
                    AllChecked = false;
                    Results.RemoveAt(i--);
                }
                else
                    continue;

                if (result.SymbolRelation == SymRelation.OR)
                {
                    Results.AddRange(result.MultiplyOut());
                    continue;
                }

                for(int j=0;j<result.nSymbols;j++)
                {
                    iSymbol s = result.Symbols[j];
                    if (s is SymbolGroup)
                    {
                        result.Symbols.RemoveAt(j--);   //removes the symbolgroup that is being replaced, so that the rest of the group can be added to the expansion.
                        AllChecked = false;
                        SymbolGroup subResult = s as SymbolGroup;
                        if(subResult.SymbolRelation == SymRelation.OR)
                        {
                            List<SymbolGroup> newResults;
                            newResults = subResult.MultiplyOut();
                            foreach(SymbolGroup newSg in newResults)
                            {
                                newSg.Symbols.AddRange(result.Symbols);
                            }
                            Results.AddRange(newResults);
                        }
                        break;
                    }
                }
            }
        }
        return Results;
    }

Answer 3

После большой работы, этот метод я использовал, чтобы получить минимальные условия обращения.

    public List<iSymbol> GetInvertedGroup()
    {
        TrimSymbolList();
        List<List<iSymbol>> symbols = this.CopyListMembers(Symbols);
        List<iSymbol> SymList;
        while (symbols.Count > 1)
        {
            symbols.Add(MultiplyLists(symbols[0], symbols[1]));
            symbols.RemoveRange(0, 2);
        }
        SymList = symbols[0];
        for(int i=0;i<symbols[0].Count;i++)
        {
            if (SymList[i] is Symbol)
            {
                Symbol sym = SymList[i] as Symbol;
                SymList.RemoveAt(i--);
                Symbol_Group symgrp = new Symbol_Group(null);
                symgrp.AddSymbol(sym);
                SymList.Add(symgrp);
            }
        }

        for (int i = 0; i < SymList.Count; i++)
        {
            if (SymList[i] is Symbol_Group)
            {
                Symbol_Group SymGrp = SymList[i] as Symbol_Group;
                if (SymGrp.Symbols.Count > 1)
                {
                    List<iSymbol> list = SymGrp.GetInvertedGroup();
                    SymList.RemoveAt(i--);
                    AddElementsOf(list, SymList);
                }
            }
        }
        return SymList;
    }

    public List<iSymbol> MultiplyLists(List<iSymbol> L1, List<iSymbol> L2)
    {
        List<iSymbol> Combined = new List<iSymbol>(L1.Count + L2.Count);
        foreach (iSymbol S1 in L1)
        {
            foreach (iSymbol S2 in L2)
            {
                Symbol_Group newGrp = new Symbol_Group(null);
                newGrp.AddSymbol(S1);
                newGrp.AddSymbol(S2);
                Combined.Add(newGrp);
            }
        }
        return Combined;
    }

Результатом стал список групп символов, где каждая группа представляла 1 или термин в конечном результате (например,! A! F). Был использован некоторый дополнительный код, чтобы уменьшить это до List>, так как в ответе было достаточное количество вложений. Чтобы уменьшить его, я использовал:

    public List<List<Symbol>> ReduceList(List<iSymbol> List)
    {
        List<List<Symbol>> Output = new List<List<Symbol>>(List.Count);
        foreach (iSymbol iSym in List)
        {
            if (iSym is Symbol_Group)
            {
                List<Symbol> L = new List<Symbol>();
                (iSym as Symbol_Group).GetAllSymbols(L);
                Output.Add(L);
            }
            else
            {
                throw (new Exception());
            }
        }
        return Output;
    }

    public void GetAllSymbols(List<Symbol> List)
    {
        foreach (List<iSymbol> SubList in Symbols)
        {
            foreach (iSymbol iSym in SubList)
            {
                if (iSym is Symbol)
                {
                    List.Add(iSym as Symbol);
                }
                else if (iSym is Symbol_Group)
                {
                    (iSym as Symbol_Group).GetAllSymbols(List);
                }
                else
                {
                    throw(new Exception());
                }
            }
        }
    }

Надеюсь, это поможет кому-то еще!