Вычисление выражений и хождение по дереву с использованием полиморфизма?(ала Стив Йегге)

StackOverflow https://stackoverflow.com/questions/12516

Вопрос

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

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

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

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

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

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

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

Я не буду давать ответ, но стандартное плохое решение предполагает использование switch или case statment (или просто старого доброго cascaded-ifs).A Немного лучшее решение предполагает использование таблицы указателей на функции, и, вероятно, лучшее решение предполагает использование полиморфизма.Я призываю вас когда-нибудь поработать над этим .Забавная штука!

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

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

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

Это было полезно?

Решение

Хождение по Полиморфным Деревьям, Версия 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)

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

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

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

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

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

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

классы бинарных операторов:Плюс, Минус,Mul,Div

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

класс чисел:Число

  • содержит числовое значение конечного узла, например17 или 42

Другие советы

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

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

    +
   / \
  +   3
 / \
1   2

против

    +
   / \
  1   +
     / \
    2   3

Круглые скобки являются "подсказкой" для синтаксического анализатора (например, для superjoe30, для "рекурсивного спуска")

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

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

Представляющий узлы

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

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

         +
    / \
node   node

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

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

        ( )
     |
    node

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

  • Узел
  • Бинарный узел :наследовать от узла
  • Plus :наследование от двоичного узла
  • Минус :наследование от двоичного узла
  • Мул :наследование от двоичного узла
  • Див :наследование от двоичного узла
  • Значение :наследовать от узла
  • Парен :наследовать от узла

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

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

Я не буду давать ответ, но стандартное плохое решение предполагает использование switch или case statment (или просто старого доброго cascaded-ifs).A Немного лучшее решение предполагает использование таблицы указателей на функции, и, вероятно, лучшее решение предполагает использование полиморфизма.

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

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

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

Пуск -> E1
E1 -> E1 + E1 | E1-E1
E1 -> E2*E2 | E2/E2 |E2
E2 -> число | (E1)

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

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

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

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

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

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

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

Ре:Джастин

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

  +
 / \
2  ( )
    |
    2

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

  +
 / \
2   2

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

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

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

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

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

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

Рекурсия.

@Джастин:

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

2 + (2)

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

           .
          / \
         2  ( )
             |
             2

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

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

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

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

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

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

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

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

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

#!/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()
Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top