Оценка выражения и движение по дереву с использованием полиморфизма? (ala Steve Yegge)

Question

Сегодня утром я читал Steve Yegge's: When Polymorphism Fails, когда я столкнулся с вопросом, что его сотрудник использовал, чтобы спросить потенциальных сотрудников, когда они пришли на собеседование в Amazon.

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

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

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

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

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

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

Я не отдадим ответ, но Standard Bad Решение предполагает использование выключателя или корпуса даного (или просто хороших старомодных каскадно-КСФ).A Немного лучшее решение включает в себя с использованием таблицы указателей функций, и, возможно, наилучшего решения предполагает использование полиморфизма. I поощрять вас к работе через него когда-нибудь. Забавные вещи!

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

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

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

Answer 1

Полиморфные Дерево Walking, 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

• все бинарные операторы наследовать этот класс
метод
• процесс делает работу evaluting выражение и возвращает результат

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

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

номер класс: Num

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

Answer 2

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

Answer 3

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

Answer 4

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

Рекурсия.

Answer 5

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

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

+ 
/\ 
    + 3 
/\ 
1 2 

против

+ 
/\ 
    1 + 
    /\ 
    2 3 

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

Answer 6

Re: Джастин

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

+ 
/\ 
2 () 
    | 
    2 

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

+ 
/\ 
2 2 

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

Answer 7

Это входит в теорию разбора/компилятора, которая является своего рода кроличьей дырой ... The Dragon Book является стандартным текстом для построения компилятора и принимает это в крайности.В этом конкретном случае вы хотите построить context-free grammar для базовой арифметики, затем используйте эту грамматику для разбора abstract syntax tree. Затем вы можете перебирать дерево, уменьшая его снизу вверх (именно в этот момент вы примените оператор полиморфизма/указатели функций/оператора switch, чтобы уменьшить дерево).

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

Answer 8

@Justin:

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

2 + (2) 

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

  . 
     /\ 
     2 () 
      | 
      2 

Answer 9

ПРедСТАВИТельСТВО Узлов

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

• двоичные узлы: Добавить Minus Mul Div
  У них есть двое детей, слева и вышка ХТ сторона

   + 
      /\ 
  node node 
  

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

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

  () 
      | 
      node 
  

для полиморфного решения, мы должны иметь такого рода классовых отношений:

• Узел
• BinaryNode: наследуются от узла
• Plus: наследование от Binary узла
• Минус: наследоваться от Binary узла
• Mul: наследование от Binary узла
• Div: наследовать от Binary Узел
• Значение: inherit from Node
• Paren: inherit from node

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

Answer 10

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

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

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

Answer 11

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

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

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

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

Answer 12

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

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

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

Answer 13

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

Начало -> 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.

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

Answer 14

Я написал такой парсер с некоторыми основными методами, как Infix -> RPN и Shunting Yard и Tree Traversals. Here is the implementation I've came up with.
Он написан на C++ и компилируется как на Linux, так и на Windows.
Любые предложения/вопросы приветствуются.

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

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

Answer 15

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

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 16

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

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