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

Question

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

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

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

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

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

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

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

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

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

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

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

Answer 1

Полиморфная ходьба по дереву , версия 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)

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

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

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

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

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

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

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

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

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

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

Answer 2

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

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

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

       +
      / \
  node   node
  

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

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

      ( )
       |
      node
  

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

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

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

Answer 3

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

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

Answer 4

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

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

    +
   / \
  +   3
 / \
1   2

против

    +
   / \
  1   +
     / \
    2   3

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

Answer 5

Хм ... Я не думаю, что вы можете написать для этого анализатор сверху вниз без возврата назад, так что это должен быть своего рода анализатор с уменьшением сдвига. 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.

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

Answer 6

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

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

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

Answer 7

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

Answer 8

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

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

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

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

Answer 9

Re: Джастин

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

  +
 / \
2  ( )
    |
    2

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

  +
 / \
2   2

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

Answer 10

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

#!/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()