Оценка экспрессии и ходьба по дереву с использованием полиморфизма? (аля Стив Йегге)

Я как бы собрал это консольное приложение на c # в качестве доказательства концепции. Чувствую, что это могло бы быть намного лучше (что оператор switch в GetNode немного неуклюжий (потому что там я попал в пустую строку, пытаясь отобразить имя класса для оператора)). Любые предложения о том, как это можно улучшить, очень приветствуются.

using System;

class Program
{
    static void Main(string[] args)
    {
        string expression = "(((3.5 * 4.5) / (1 + 2)) + 5)";
        Console.WriteLine(string.Format("{0} = {1}", expression, new Expression.ExpressionTree(expression).Value));
        Console.WriteLine("\nShow's over folks, press a key to exit");
        Console.ReadKey(false);
    }
}

namespace Expression
{
    // -------------------------------------------------------

    abstract class NodeBase
    {
        public abstract double Value { get; }
    }

    // -------------------------------------------------------

    class ValueNode : NodeBase
    {
        public ValueNode(double value)
        {
            _double = value;
        }

        private double _double;
        public override double Value
        {
            get
            {
                return _double;
            }
        }
    }

    // -------------------------------------------------------

    abstract class ExpressionNodeBase : NodeBase
    {
        protected NodeBase GetNode(string expression)
        {
            // Remove parenthesis
            expression = RemoveParenthesis(expression);

            // Is expression just a number?
            double value = 0;
            if (double.TryParse(expression, out value))
            {
                return new ValueNode(value);
            }
            else
            {
                int pos = ParseExpression(expression);
                if (pos > 0)
                {
                    string leftExpression = expression.Substring(0, pos - 1).Trim();
                    string rightExpression = expression.Substring(pos).Trim();

                    switch (expression.Substring(pos - 1, 1))
                    {
                        case "+":
                            return new Add(leftExpression, rightExpression);
                        case "-":
                            return new Subtract(leftExpression, rightExpression);
                        case "*":
                            return new Multiply(leftExpression, rightExpression);
                        case "/":
                            return new Divide(leftExpression, rightExpression);
                        default:
                            throw new Exception("Unknown operator");
                    }
                }
                else
                {
                    throw new Exception("Unable to parse expression");
                }
            }
        }

        private string RemoveParenthesis(string expression)
        {
            if (expression.Contains("("))
            {
                expression = expression.Trim();

                int level = 0;
                int pos = 0;

                foreach (char token in expression.ToCharArray())
                {
                    pos++;
                    switch (token)
                    {
                        case '(':
                            level++;
                            break;
                        case ')':
                            level--;
                            break;
                    }

                    if (level == 0)
                    {
                        break;
                    }
                }

                if (level == 0 && pos == expression.Length)
                {
                    expression = expression.Substring(1, expression.Length - 2);
                    expression = RemoveParenthesis(expression);
                }
            }
            return expression;
        }

        private int ParseExpression(string expression)
        {
            int winningLevel = 0;
            byte winningTokenWeight = 0;
            int winningPos = 0;

            int level = 0;
            int pos = 0;

            foreach (char token in expression.ToCharArray())
            {
                pos++;

                switch (token)
                {
                    case '(':
                        level++;
                        break;
                    case ')':
                        level--;
                        break;
                }

                if (level <= winningLevel)
                {
                    if (OperatorWeight(token) > winningTokenWeight)
                    {
                        winningLevel = level;
                        winningTokenWeight = OperatorWeight(token);
                        winningPos = pos;
                    }
                }
            }
            return winningPos;
        }

        private byte OperatorWeight(char value)
        {
            switch (value)
            {
                case '+':
                case '-':
                    return 3;
                case '*':
                    return 2;
                case '/':
                    return 1;
                default:
                    return 0;
            }
        }
    }

    // -------------------------------------------------------

    class ExpressionTree : ExpressionNodeBase
    {
        protected NodeBase _rootNode;

        public ExpressionTree(string expression)
        {
            _rootNode = GetNode(expression);
        }

        public override double Value
        {
            get
            {
                return _rootNode.Value;
            }
        }
    }

    // -------------------------------------------------------

    abstract class OperatorNodeBase : ExpressionNodeBase
    {
        protected NodeBase _leftNode;
        protected NodeBase _rightNode;

        public OperatorNodeBase(string leftExpression, string rightExpression)
        {
            _leftNode = GetNode(leftExpression);
            _rightNode = GetNode(rightExpression);

        }
    }

    // -------------------------------------------------------

    class Add : OperatorNodeBase
    {
        public Add(string leftExpression, string rightExpression)
            : base(leftExpression, rightExpression)
        {
        }

        public override double Value
        {
            get
            {
                return _leftNode.Value + _rightNode.Value;
            }
        }
    }

    // -------------------------------------------------------

    class Subtract : OperatorNodeBase
    {
        public Subtract(string leftExpression, string rightExpression)
            : base(leftExpression, rightExpression)
        {
        }

        public override double Value
        {
            get
            {
                return _leftNode.Value - _rightNode.Value;
            }
        }
    }

    // -------------------------------------------------------

    class Divide : OperatorNodeBase
    {
        public Divide(string leftExpression, string rightExpression)
            : base(leftExpression, rightExpression)
        {
        }

        public override double Value
        {
            get
            {
                return _leftNode.Value / _rightNode.Value;
            }
        }
    }

    // -------------------------------------------------------

    class Multiply : OperatorNodeBase
    {
        public Multiply(string leftExpression, string rightExpression)
            : base(leftExpression, rightExpression)
        {
        }

        public override double Value
        {
            get
            {
                return _leftNode.Value * _rightNode.Value;
            }
        }
    }
}

Я написал такой парсер с некоторыми базовыми приемами, такими как Infix -> RPN и Shunting Yard и Обходы деревьев . Вот реализация, которую я придумал .
Он написан на C ++ и компилируется как в Linux, так и в Windows.
Любые предложения / вопросы приветствуются.

Итак, давайте попробуем решить проблему всеми тремя способами. Как перейти от арифметического выражения (например, в строке), такого как "2 + (2)", к дереву выражений с использованием каскадных if, таблицы указателей на функции и / или полиморфизма?

Это интересно, но я не думаю, что это относится к области объектно-ориентированного программирования ... Я думаю, что это больше связано с методами синтаксического анализа .

следует использовать функциональный язык Imo. Деревья сложнее представлять и манипулировать на ОО-языках.

Я думаю, что вопрос в том, как написать синтаксический анализатор, а не оценщик. Или, скорее, как создать дерево выражений из строки.

Операторы case, которые возвращают базовый класс, точно не учитываются.

Базовая структура «полиморфного» решения (это еще один способ сказать, мне все равно, с чем вы это строите, я просто хочу расширить его с помощью переписывания наименьшего количества кода) - десериализация объекта иерархия из потока с (динамическим) набором известных типов.

Суть реализации полиморфного решения заключается в том, чтобы иметь способ создания объекта выражения из сопоставителя шаблонов, вероятно, рекурсивного. То есть сопоставить BNF или аналогичный синтаксис с фабрикой объектов.

Хм ... Я не думаю, что вы можете написать для этого нисходящий парсер без возврата назад, так что это должен быть своего рода парсер с уменьшением сдвига. LR (1) или даже LALR, конечно, будут отлично работать со следующим (специальным) определением языка:

Start -> E1
E1 -> E1 + E1 | E1-E1
E1 -> E2 * E2 | E2 / E2 | E2
E2 -> число | (E1)

Разделение его на E1 и E2 необходимо для сохранения приоритета * и / над + и -.

Но вот как бы я это сделал, если бы мне пришлось писать синтаксический анализатор вручную:

• Два стека, один хранит узлы дерева в качестве операндов, а другой хранит операторы
• Читайте ввод слева направо, делайте листовые узлы чисел и помещайте их в стек операндов.
• Если у вас есть> = 2 операнда в стеке, всплывают 2, объедините их с верхним оператором в стеке операторов и перенесите эту структуру обратно в дерево операндов, , если только
• Следующий оператор имеет более высокий приоритет, чем тот, который в настоящее время находится на вершине стека.

Это оставляет нам проблему обработки скобок. Одним из элегантных (я думал) решений является сохранение приоритета каждого оператора в виде числа в переменной. Итак, изначально,

• int plus, minus = 1;
• int mul, div = 2;

Теперь каждый раз, когда вы видите увеличение левой скобки все эти переменные на 2, и каждый раз, когда вы видите правую скобку, уменьшайте все переменные на 2.

Это гарантирует, что + in 3 * (4 + 5) имеет более высокий приоритет, чем *, и 3 * 4 не будет помещен в стек. Вместо этого он будет ждать 5, нажмите 4 + 5, затем нажмите 3 * (4 + 5).

Я не буду давать ответ, но Стандартное Плохое Решение включает в себя использование переключателя или определения случая (или просто хорошего старомодного каскадного ввода-вывода). Немного лучшее решение предполагает использование таблицы указателей функций, а, вероятно, лучшее решение предполагает использование полиморфизма.

Последние двадцать лет эволюции интерпретаторов можно рассматривать как движение по другому пути - полиморфизм (например, наивные метациркулярные интерпретаторы Smalltalk) на функции указателей (реализации наивного lisp, многопоточного кода, C ++) для переключения ( наивные интерпретаторы байт-кода), а затем и далее в JIT и т. д., которые либо требуют очень больших классов, либо (в однополиморфных языках) двойной диспетчеризации, что сводит полиморфизм к регистру типов, и вы возвращаетесь на этап один. Какое определение 'best' используется здесь?

Для простых вещей полиморфное решение в порядке - вот то, что я сделал ранее , но либо стек и байт-код / ​​переключатель, либо использование компилятора среды выполнения обычно лучше, если вы, скажем, строите функцию с несколькими тысячами точек данных.

Представление узлов

Если мы хотим включить круглые скобки, нам нужно 5 видов узлов:

• двоичные узлы: Добавить минус Mul Div
  у них есть два потомка, левая и правая стороны

       +
      / \
  node   node
  

• узел для хранения значения: Val
  нет дочерних узлов, только числовое значение

• узел для отслеживания паренов: Paren
  один дочерний узел для подвыражения

      ( )
       |
      node
  

Для Полиморфное решение, нам нужно иметь такие классовые отношения:

• Node
• BinaryNode: наследовать от Node
• Plus: наследовать от Binary Node
• Минус: наследование от двоичного узла
• Mul: наследование от двоичного узла
• Div: наследование от двоичного узла
• Значение: наследование от узла
• Paren: наследовать от узла

Существует виртуальная функция для всех узлов, называемая eval (). Если вы вызовете эту функцию, она вернет значение этого подвыражения.

Это входит в теорию синтаксического анализа / компилятора, которая является своего рода кроличьей ношей ... Книга Дракона является стандартным текстом для построения компилятора, и доводит это до крайности. В этом конкретном случае вы хотите создать контекстную грамматику без контекста для базовой арифметики, а затем использовать эту грамматику для анализа абстрактного синтаксического дерева . Затем вы можете перебирать дерево, уменьшая его снизу вверх (именно в этот момент вы примените оператор полиморфизма / указателей на функции / переключателя, чтобы уменьшить дерево).

Я нашел эти заметки невероятно полезными в теории компиляции и парсинга.

Проблема, я думаю, в том, что нам нужно разобрать perentheses, и все же они не являются бинарным оператором? Должны ли мы взять (2) в качестве одного токена, который оценивается в 2?

Паренсы не должны отображаться в дереве выражений, но они влияют на его форму. Например, дерево для (1 + 2) +3 отличается от 1+ (2 + 3):

    +
   / \
  +   3
 / \
1   2

против

    +
   / \
  1   +
     / \
    2   3

Скобки являются «подсказкой» для синтаксический анализатор (например, per superjoe30, чтобы «рекурсивно спуститься»)

Re: Джастин

Я думаю, что дерево выглядело бы примерно так:

  +
 / \
2  ( )
    |
    2

По сути, у вас был бы «eval» узел, который просто оценивает дерево под ним , Это было бы оптимизировано так:

  +
 / \
2   2

В этом случае паренсы не требуются и ничего не добавляют. Они ничего не добавляют логически, поэтому они просто ушли.

Или возможно это - реальный вопрос: как можно представить (2) как BST? Это - часть, которая сбивает меня с толку.

Рекурсия.

Строковый Токенизатор + LL (1) Синтаксический анализатор даст Вам дерево выражений... полиморфизм, путь мог бы связать абстрактный Арифметический класс с, "оценивают (a, b)" функцию, которая переопределяется для каждого из включенных операторов (Дополнение, Вычитание и т.д.) для возврата соответствующего значения, и дерево содержит Целые числа и Арифметические операторы, которые могут быть оценены сообщением (?) - заказывают обход дерева.

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

, В то время как принятый ответ является решением одной половины проблемы, другая половина - на самом деле парсинг выражения - является все еще нерешенной. Как правило, эти виды проблем могут быть решены с помощью синтаксический анализатор с рекурсивным спуском . Запись такого синтаксического анализатора часто является забавным осуществлением, но большинство современные инструменты для синтаксического анализа естественных языков абстрагирует это далеко для Вас.

синтаксический анализатор также значительно тяжелее при разрешении чисел с плавающей точкой в строке. Я должен был создать DFA для принятия чисел с плавающей точкой в C - это была очень кропотливая и подробная задача. Помните, допустимые плавающие точки включают: 10, 10., 10.123, 9.876e-5, 1.0f.025, и т.д. Я предполагаю, что некоторое разрешение от этого (в пользу simplicty и краткости) было сделано в интервью.

@Justin:

Взгляд на мое примечание по представлению узлов. Если Вы используете ту схему, то

2 + (2)

может быть представлен как

           .
          / \
         2  ( )
             |
             2