Блог

В настоящее время я пытаюсь определить алгоритм для дерева выражений. Строки, которые я получу в данный момент, будут похожи на Hello 12 World или A2-12-A3-14 . Строки будут содержать одни и те же операторы. В моем алгоритме в настоящее время последний операнд не помещается в дерево. Я посмотрел онлайн, и мне трудно понять, как заставить это работать должным образом.

 Stack<BaseNode> TreeStack = new Stack<BaseNode>();
BaseNode temp1 = new BaseNode();
BaseNode temp2 = new BaseNode();
for (int i = 0; i < tree.Length; i  )
{
    VariableNode varNode = new VariableNode();
    NumericalNode numNode = new NumericalNode();
    if (CheckExpressions(tree[i])) // if the character is an operator
    {
        OperatorNode expression = new OperatorNode(tree[i]);
        temp1 = TreeStack.Pop();
        if (TreeStack.Count != 0)
        {
            temp2 = TreeStack.Pop();
        }
        expression.Right = temp1;
        expression.Left = temp2;

        TreeStack.Push(expression);
    }
    else if (!CheckExpressions(tree[i]))
    {
        if (Char.IsLetter(tree[i]))
        {
            while (Char.IsLetter(tree[i])) // for the variable node
            {
                varNode.name  = tree[i];
                if (i   1 == tree.Length)
                {
                    break;
                }
                i  ;
            }
            TreeStack.Push(varNode);
            if (i   1 != tree.Length)
            {
                i--;
            }
        }
        else if (Char.IsDigit(tree[i])) // for constant value
        {
            int zero = 0; // for appending the numbers to combine them
            while (Char.IsDigit(tree[i]))
            {
                if (zero == 0)
                {
                    zero = tree[i] - '0';
                }
                else
                {
                    zero = int.Parse(zero.ToString()   tree[i].ToString());
                }
                if (i < tree.Length)
                {
                    i  ;
                }
            }
            if (i   1 != tree.Length)
            {
                i--;
            }
            numNode.number = zero;
            TreeStack.Push(numNode);
        }
    }
}
  

Я думаю, вы понимаете, что вам не хватает второго операнда, потому что, как только вы видите оператор, вы пытаетесь открыть стек для двух значений. В приведенном вами примере легко увидеть, что этого никогда не будет (этот стек будет иметь 2 переменные, поскольку оператор является двоичным). Итак, вам следует каким-то образом сохранить вторую переменную и оператор и попытаться оценить их на более позднем этапе. Приведенный ниже алгоритм может быть полезен, поймите, он базовый для простых операторов.

1. Начните с двух стеков, одного из переменных и одного из операторов.
2. Прежде чем запускать оператор в стеке операторов, проверьте приоритет. Если приоритет существующего оператора в верхней части стека выше или равен тому, который вы собираетесь ввести, тогда начните извлекать стек для operator и переменных.
3. Наконец, когда вы пройдетесь по всей строке, проверьте свой стек на наличие любого оставшегося оператора, завершите его оценку, и вы должны получить конечные результаты.

В 2*3 4 когда вы достигнете , у вас будет 2,3 в одном стеке и * в другом. Теперь, пытаясь нажать , вы увидите существующий * в стеке с более высоким приоритетом, поэтому вставьте его, поскольку это двоичный оператор, вставьте 2 переменные, создайте выражение, оцените его и нажмите на стек переменных (поскольку результатом вычисления будет переменная / число), а затем снова посмотрите, есть ли в стеке еще какой-либо оператор с более высоким приоритетом.

Добавляя решение, пожалуйста, имейте в виду: 1. Приоритет оператора / какой тип оператора (унарный / двоичный) / является ли он симметричным / несимметричным ( симметрично, но мощность нет), будет играть важную роль.

Старайтесь не изменять переменную i внутри цикла, рано или поздно вы столкнетесь с проблемами.

Приведенный код работает только для приведенных 2 примеров, а часть для проверки приоритета пуста, но может быть заполнена на основе существующего кода.

Вам нужно будет изменить имя переменной loigc, в случае смешанных имен, таких как ‘A2’, ваша текущая логика потерпит неудачу.

 string tree = "AB-12-AC-14";

            Stack<BaseNode> TreeStack = new Stack<BaseNode>();
            Stack<BaseNode> TreeStack1 = new Stack<BaseNode>();
            BaseNode temp1 = new BaseNode();
            BaseNode temp2 = new BaseNode();
            for (int i = 0; i < tree.Length; i  )
            {
                VariableNode varNode = new VariableNode();
                NumericalNode numNode = new NumericalNode();
                if (CheckExpressions(tree[i])) // if the character is an operator
                {
                    OperatorNode expression = new OperatorNode(tree[i]);

                    //check priority should pass the current operator to really check for priority
                    if (CheckPriority() || TreeStack1.Count == 0)
                    {
                        TreeStack1.Push(expression);
                    }
                    else
                    {
                        // assuming binary operators only
                        temp1 = TreeStack.Pop();
                        temp2 = TreeStack.Pop();
                        expression.Right = temp1;
                        expression.Left = temp2;
                        TreeStack.Push(expression);
                        // need to check if there are more operators on stack1 are they higher priority then current operator
                        // if they are then pop them and apply them too
                    }
                }
                else if (!CheckExpressions(tree[i]))
                {
                    if (Char.IsLetter(tree[i]))
                    {
                        while (Char.IsLetter(tree[i])) // for the variable node
                        {
                            varNode.name  = tree[i];
                            if (i   1 == tree.Length)
                            {
                                break;
                            }
                            i  ;
                        }
                        TreeStack.Push(varNode);
                        if (i   1 != tree.Length)
                        {
                            i--;
                        }
                    }
                    else if (Char.IsDigit(tree[i])) // for constant value
                    {
                        int zero = 0; // for appending the numbers to combine them
                        while (i < tree.Length amp;amp; Char.IsDigit(tree[i])) // need to check for length otherwise index will go out of bounds
                        {
                            if (zero == 0)
                            {
                                zero = tree[i] - '0';
                            }
                            else
                            {
                                zero = int.Parse(zero.ToString()   tree[i].ToString());
                            }
                            if (i < tree.Length)
                            {
                                i  ;
                            }
                        }
                        if (i   1 != tree.Length)
                        {
                            i--;
                        }
                        numNode.number = zero;
                        TreeStack.Push(numNode);
                    }
                }
            }

            // finish any remaining operators and push the final expression on the stack
            while (TreeStack1.Count!=0)
            {
                OperatorNode expression1 = new OperatorNode(((OperatorNode)TreeStack1.Pop()).v);
                expression1.Right = TreeStack.Pop();
                expression1.Left = TreeStack.Pop();
                TreeStack.Push(expression1);
            }