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

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

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

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

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

Первая половина вопроса, которую некоторые люди (чьи имена я буду защищать до умирающего дыхания, но их инициалы - Вилли Льюис) - это требование к работе, если вы хотите назвать себя разработчиком и работать в Amazon, на самом деле довольно сложно , Вопрос в том, как перейти от арифметического выражения (например, в строке), такого как «2 + (2)» к дереву выражений. В какой-то момент у нас может возникнуть проблема с ADJ по этому вопросу.

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

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

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

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

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

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

15.08.2008 17:31:39
Основываясь на ответе Марка Харриссона, я написал реализацию php
serdarsenay 4.11.2013 00:14:18
16 ОТВЕТОВ
РЕШЕНИЕ

Полиморфная ходьба по дереву , версия Python

#!/usr/bin/python

class Node:
    """base class, you should not process one of these"""
    def process(self):
        raise('you should not be processing a node')

class BinaryNode(Node):
    """base class for binary nodes"""
    def __init__(self, _left, _right):
        self.left = _left
        self.right = _right
    def process(self):
        raise('you should not be processing a binarynode')

class Plus(BinaryNode):
    def process(self):
        return self.left.process() + self.right.process()

class Minus(BinaryNode):
    def process(self):
        return self.left.process() - self.right.process()

class Mul(BinaryNode):
    def process(self):
        return self.left.process() * self.right.process()

class Div(BinaryNode):
    def process(self):
        return self.left.process() / self.right.process()

class Num(Node):
    def __init__(self, _value):
        self.value = _value
    def process(self):
        return self.value

def demo(n):
    print n.process()

demo(Num(2))                                       # 2
demo(Plus(Num(2),Num(5)))                          # 2 + 3
demo(Plus(Mul(Num(2),Num(3)),Div(Num(10),Num(5)))) # (2 * 3) + (10 / 2)

Тесты просто строят двоичные деревья с помощью конструкторов.

Структура программы:

абстрактный базовый класс: узел

  • все узлы наследуются от этого класса

абстрактный базовый класс: BinaryNode

  • все бинарные операторы наследуются от этого класса
  • Метод process выполняет оценку выражения и возвращает результат.

классы бинарных операторов: Plus, Minus, Mul, Div

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

Числовой класс: Num

  • содержит числовое значение листового узла, например, 17 или 42
11
2.09.2008 15:34:27
Этот ответ ужасно перегружен. Вопрос был для 2 + (2), а не произвольного арифметического вычисления. Кроме того, это просто выполняет дерево, но не создает его.
ReaperUnreal 31.10.2008 22:44:31
Вопрос был для арифметического расчета ТАКОГО 2 + (2), а не для вычисления 2 + (2). Таким образом, он не перегружен, но отвечает на вопрос, как задумано.
Thomas Owens 10.11.2008 12:53:23
Этот ответ не относится к вопросу «Как вы переходите от арифметического выражения (например, в STRING), такого как« 2 + (2) ».... Куда относится« demo (Plus (Mul (Num (2), Num (3)), Div (Num (10), Num (5)))) "взяты? Эта другая программа, которую мы не видим? Почему это помечено как лучший ответ?
Guge 20.11.2008 02:09:30
«Вы получаете простую часть: вам нужно решить, с какими классами Вилли будет строить дерево».
vanja. 11.08.2009 07:31:55

String Tokenizer + LL (1) Parser даст вам дерево выражений ... способ полиморфизма может включать в себя абстрактный арифметический класс с функцией «define (a, b)», который переопределяется для каждого из задействованных операторов (дополнение, Вычитание и т. Д.), Чтобы вернуть соответствующее значение, и дерево содержит целочисленные и арифметические операторы, которые можно оценить путем обхода дерева по порядку (?).

2
15.08.2008 17:50:11

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

0
24.08.2008 21:35:36
В самом деле ? Это наивная реализация C ++: class AST {vector <AST *> child; толчок пустоты (AST *); / * добавить ребенка, должен вызываться из парсера yacc / bison / AST eval (); / рекурсивные вычисления дочерних узлов / строковый дамп (int = 0); / дамп в виде дерева с вкладками * /};
Dmitry Ponyatov 13.03.2017 18:27:32
Но вы правы в eval () body: когда вы пытаетесь сделать nive eval похожим на nest [0] / * lchild * / = nest [0] -> eval (), очень легко получить утечку памяти объекта nest [0] раньше это eval. Я действительно не знаю, как отследить это в случае переменных, общих для нескольких выражений, но номера листьев можно просто удалить.
Dmitry Ponyatov 13.03.2017 18:33:09
Я забыл 'string val' как метку для самого узла в AST
Dmitry Ponyatov 13.03.2017 18:34:41

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

Рекурсия.

0
15.08.2008 19:50:45

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

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

    +
   / \
  +   3
 / \
1   2

против

    +
   / \
  1   +
     / \
    2   3

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

4
15.08.2008 20:04:21

Re: Джастин

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

  +
 / \
2  ( )
    |
    2

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

  +
 / \
2   2

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

1
15.08.2008 20:14:33

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

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

4
15.08.2008 21:58:53
Вот минимальный CFG для исходного вопроса: S -> NN -> 2 N -> NON -> (N) O -> - N
ReaperUnreal 31.10.2008 21:04:18

@Justin:

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

2 + (2)

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

           .
          / \
         2  ( )
             |
             2
0
15.08.2008 23:40:16

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

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

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

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

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

        ( )
         |
        node
    

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

  • Узел
  • BinaryNode: наследовать от узла
  • Плюс: наследование от бинарного узла
  • Минус: наследование от бинарного узла
  • Mul: наследовать от Binary Node
  • Div: наследовать от двоичного узла
  • Значение: наследовать от узла
  • Парен: наследовать от узла

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

4
15.08.2008 23:38:03
Нет смысла включать скобки в абстрактное синтаксическое дерево.
Jonas Kongslund 21.11.2008 01:45:21
В некоторых случаях есть. У вас может быть инструмент для перезаписи / воссоздания исходного выражения, а не для оптимизации избыточности в исходном выражении. Конечно, в случае оценки выражения и получения ответа вы правы.
Mark Harrison 17.11.2015 17:58:40

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

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

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

2
20.08.2008 18:09:15

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

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

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

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

1
3.07.2012 14:51:48

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

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

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

0
25.08.2008 15:21:17

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

Пуск -> E1
E1 -> E1 + E1 | E1-E1
E1 -> E2 * E2 | E2 / E2 | E2
E2 -> номер | (Е1)

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

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

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

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

  • int плюс, минус = 1;
  • int mul, div = 2;

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

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

2
10.11.2008 12:49:51

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

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

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

0
21.11.2008 01:35:25

Я как бы собрал это консольное приложение на 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;
            }
        }
    }
}
0
23.01.2009 22:00:02
Приятно видеть полную реализацию, но меня немного смущает, почему вы объединили логику разбора с представлением дерева выражений, создав тесную связь логики разбора с деревом выражений. Кроме того, вы можете сгенерировать карту (управляемую xml, базой данных, словарем в коде или пользовательским атрибутом, применяемым к каждому классу, представляющему узел) между вашими токенами и классом, на который они отображаются. Проблема здесь заключается в использовании отражения (с помощью Activator или другого метода) для генерации ваших классов.
Merritt 15.08.2010 19:06:52
@Merritt ммм хорошая мысль, возможно, в следующий раз у меня будет свободное время для обеда. Спасибо за предложения.
Wilfred Knievel 20.10.2010 08:44:48

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

#!/usr/bin/env python

#tree structure [left argument, operator, right argument, priority level]
tree_root = [None, None, None, None]
#count of parethesis nesting
parenthesis_level = 0
#current node with empty right argument
current_node = tree_root

#indices in tree_root nodes Left, Operator, Right, PRiority
L, O, R, PR = 0, 1, 2, 3

#functions that realise operators
def sum(a, b):
    return a + b

def diff(a, b):
    return a - b

def mul(a, b):
    return a * b

def div(a, b):
    return a / b

#tree evaluator
def process_node(n):
    try:
        len(n)
    except TypeError:
        return n
    left = process_node(n[L])
    right = process_node(n[R])
    return n[O](left, right)

#mapping operators to relevant functions
o2f = {'+': sum, '-': diff, '*': mul, '/': div, '(': None, ')': None}

#converts token to a node in tree
def convert_token(t):
    global current_node, tree_root, parenthesis_level
    if t == '(':
        parenthesis_level += 2
        return
    if t == ')':
        parenthesis_level -= 2
        return
    try: #assumption that we have just an integer
        l = int(t)
    except (ValueError, TypeError):
        pass #if not, no problem
    else:
        if tree_root[L] is None: #if it is first number, put it on the left of root node
            tree_root[L] = l
        else: #put on the right of current_node
            current_node[R] = l
        return

    priority = (1 if t in '+-' else 2) + parenthesis_level

    #if tree_root does not have operator put it there
    if tree_root[O] is None and t in o2f:
            tree_root[O] = o2f[t]
            tree_root[PR] = priority
            return

    #if new node has less or equals priority, put it on the top of tree
    if tree_root[PR] >= priority:
        temp = [tree_root, o2f[t], None, priority]
        tree_root = current_node = temp
        return

    #starting from root search for a place with higher priority in hierarchy
    current_node = tree_root
    while type(current_node[R]) != type(1) and priority > current_node[R][PR]:
        current_node = current_node[R]
    #insert new node
    temp = [current_node[R], o2f[t], None, priority]
    current_node[R] = temp
    current_node = temp



def parse(e):
    token = ''
    for c in e:
        if c <= '9' and c >='0':
            token += c
            continue
        if c == ' ':
            if token != '':
                convert_token(token)
                token = ''
            continue
        if c in o2f:
            if token != '':
                convert_token(token)
            convert_token(c)
            token = ''
            continue
        print "Unrecognized character:", c
    if token != '':
        convert_token(token)


def main():
    parse('(((3 * 4) / (1 + 2)) + 5)')
    print tree_root
    print process_node(tree_root)

if __name__ == '__main__':
    main()
0
25.10.2013 20:39:14