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

Question

Этим утром я читал Стива Йегге: «Когда полиморфизм терпит неудачу» , когда я сталкивался с вопросом, который его коллега спрашивал у потенциальных сотрудников, когда они приходили на собеседование в Amazon.

В качестве примера полиморфизма в действие, давайте посмотрим на классический "eval" вопрос интервью, который (как насколько я знаю) привезли в амазонку Рон Браунштейн. Вопрос в том довольно богатый, так как ему удается исследовать широкий спектр важных навыки: ООП дизайн, рекурсия, бинарный деревья, полиморфизм и время выполнения набор текста, общие навыки кодирования и (если Вы хотите сделать это очень сложно) Теория синтаксического анализа.

В какой-то момент кандидат с надеждой понимает, что вы можете представлять арифметическое выражение в виде двоичного дерево, если вы используете только бинарные операторы, такие как "+", "-", "*", "/". Листовые узлы все числа, а внутренние узлы все операторы. Оценка выражение означает ходить по дереву. Если кандидат не осознает этого, Вы можете осторожно привести их к этому, или если необходимо, просто скажи им.

Даже если вы скажете им, это все еще интересная проблема.

Первая половина вопроса, которая некоторые люди (чьи имена я буду защитить мое умирающее дыхание, но их инициалы Вилли Льюиса) чувствую Требование работы, если вы хотите позвонить Сам разработчик и работаешь на Амазонка, на самом деле довольно сложно. Вопрос в том, как вы выходите из арифметическое выражение (например, в строка), например, "2 + (2)" в дерево выражений. У нас может быть ADJ вызов по этому вопросу в некоторых точка.

Вторая половина: скажем, это проект из двух человек и ваш партнер, кто мы будем называть "Вилли", это ответственность за преобразование строковое выражение в дерево. Ты получаешь самая легкая часть: вам нужно решить, что классы Вилли, чтобы построить дерево с. Вы можете сделать это в любом язык, но не забудьте выбрать один, или Вилли передаст вам сборку язык. Если он чувствует себя отвратительно, это будет для процессора, который не больше изготовлено в производстве.

Вы будете поражены тем, сколько кандидатов boff this.

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

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

Не стесняйтесь решать один, два или все три.

[обновление: название изменено, чтобы лучше соответствовать большинству ответов.]

Answer 1

Я как бы собрал это консольное приложение на 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;
            }
        }
    }
}

Answer 2

Я написал такой парсер с некоторыми базовыми приемами, такими как Инфикс -> РПН и Маневровый двор и Обходы деревьев . Вот реализация, которую я придумал .
Он написан на C ++ и компилируется как в Linux, так и в Windows.
Любые предложения / вопросы приветствуются.

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

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

Answer 3

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

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

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

Answer 4

@ Джастин:

Посмотрите на мою заметку о представлении узлов. Если вы используете эту схему, то

2 + (2)

можно представить как

           .
          / \
         2  ( )
             |
             2

Answer 5

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

Рекурсия.

Answer 6

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