Этим утром я читал книгу Стива Йегге «Когда полиморфизм терпит неудачу» , когда я сталкивался с вопросом, который его коллега задавал потенциальным сотрудникам, когда они приходили на собеседование в Amazon.
В качестве примера полиморфизма в действии, давайте посмотрим на классический вопрос «eval» интервью, который (насколько я знаю) был доставлен в Amazon Роном Браунштейном. Вопрос довольно богатый, поскольку ему удается исследовать широкий спектр важных навыков: проектирование ООП, рекурсия, двоичные деревья, полиморфизм и типизирование во время выполнения, общие навыки кодирования и (если вы хотите сделать это очень сложным) теория парсинга. ,
В какой-то момент кандидат, надеюсь, понимает, что вы можете представить арифметическое выражение в виде двоичного дерева, предполагая, что вы используете только двоичные операторы, такие как «+», «-», «*», «/». Все конечные узлы являются числами, а все внутренние узлы являются операторами. Оценка выражения означает ходьбу по дереву. Если кандидат не осознает этого, вы можете осторожно привести его к этому или, если необходимо, просто сказать ему.
Даже если вы скажете им, это все еще интересная проблема.
Первая половина вопроса, которую некоторые люди (чьи имена я буду защищать до умирающего дыхания, но их инициалы - Вилли Льюис) - это требование к работе, если вы хотите назвать себя разработчиком и работать в Amazon, на самом деле довольно сложно , Вопрос в том, как перейти от арифметического выражения (например, в строке), такого как «2 + (2)» к дереву выражений. В какой-то момент у нас может возникнуть проблема с ADJ по этому вопросу.
Вторая половина: скажем, это проект из двух человек, а ваш партнер, которого мы назовем «Вилли», отвечает за преобразование строкового выражения в дерево. Вы получаете простую часть: вам нужно решить, с какими классами Вилли будет строить дерево. Вы можете сделать это на любом языке, но убедитесь, что вы выбрали один, иначе Вилли передаст вам язык ассемблера. Если он чувствует себя ужасно, это будет для процессора, который больше не производится в производстве.
Вы были бы поражены тем, сколько кандидатов выставили этого.
Я не буду давать ответ, но Стандартное Плохое Решение включает в себя использование переключателя или определения случая (или просто хорошего старомодного каскадного ifs). Немного лучшее решение включает в себя использование таблицы указателей функций, а, вероятно, лучшее решение предполагает использование полиморфизма. Я призываю вас поработать над этим когда-нибудь. Прикольные вещи!
Итак, давайте попробуем решить проблему всеми тремя способами. Как перейти от арифметического выражения (например, в строке), такого как "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)
Тесты просто строят двоичные деревья с помощью конструкторов.
Структура программы:
абстрактный базовый класс: узел
- все узлы наследуются от этого класса
абстрактный базовый класс: BinaryNode
- все бинарные операторы наследуются от этого класса
- Метод process выполняет оценку выражения и возвращает результат.
классы бинарных операторов: Plus, Minus, Mul, Div
- два дочерних узла, каждый для подвыражений левой и правой стороны
Числовой класс: Num
- содержит числовое значение листового узла, например, 17 или 42
String Tokenizer + LL (1) Parser даст вам дерево выражений ... способ полиморфизма может включать в себя абстрактный арифметический класс с функцией «define (a, b)», который переопределяется для каждого из задействованных операторов (дополнение, Вычитание и т. Д.), Чтобы вернуть соответствующее значение, и дерево содержит целочисленные и арифметические операторы, которые можно оценить путем обхода дерева по порядку (?).
следует использовать функциональный язык IMO. Деревья сложнее представлять и манипулировать на ОО-языках.
Или, может быть, это реальный вопрос: как вы можете представить (2) как BST? Это та часть, которая сбивает меня с толку.
Рекурсия.
Проблема, я думаю, заключается в том, что нам нужно разобрать perentheses, и все же они не являются бинарным оператором? Должны ли мы принять (2) в качестве одного токена, который оценивается в 2?
Паренсы не должны появляться в дереве выражений, но они влияют на его форму. Например, дерево для (1 + 2) +3 отличается от 1+ (2 + 3):
+
/ \
+ 3
/ \
1 2
против
+
/ \
1 +
/ \
2 3
Скобки являются «подсказкой» для синтаксического анализатора (например, для суперджо30, «рекурсивно спускаться»)
Re: Джастин
Я думаю, что дерево будет выглядеть примерно так:
+
/ \
2 ( )
|
2
По сути, у вас будет узел eval, который просто оценивает дерево под ним. Это тогда было бы оптимизировано, чтобы просто быть:
+
/ \
2 2
В этом случае паренсы не требуются и ничего не добавляют. Они ничего не добавляют логически, поэтому они просто ушли.
Это входит в теорию синтаксического анализа / компиляции, которая является своего рода кроличьей ношей ... Книга Дракона является стандартным текстом для построения компилятора и доводит это до крайности. В этом конкретном случае вы хотите создать не зависящую от контекста грамматику для базовой арифметики, а затем использовать эту грамматику для анализа абстрактного синтаксического дерева . Затем вы можете выполнять итерацию по дереву, уменьшая его снизу вверх (именно в этот момент вы примените оператор полиморфизма / указателей на функции / переключения, чтобы уменьшить дерево).
Я обнаружил, что эти заметки невероятно полезны в теории компиляции и синтаксического анализа.
@Justin:
Посмотрите на мою заметку о представлении узлов. Если вы используете эту схему, то
2 + (2)
может быть представлен как
.
/ \
2 ( )
|
2
Представление узлов
Если мы хотим включить скобки, нам нужно 5 видов узлов:
бинарные узлы: добавьте минус Mul Div, у
них есть два ребенка, слева и справа+ / \ node node
узел для хранения значения: Val
нет дочерних узлов, только числовое значениеузел для слежения за паренями: объедините
один дочерний узел для подвыражения( ) | node
Для полиморфного решения нам нужны такие классовые отношения:
- Узел
- BinaryNode: наследовать от узла
- Плюс: наследование от бинарного узла
- Минус: наследование от бинарного узла
- Mul: наследовать от Binary Node
- Div: наследовать от двоичного узла
- Значение: наследовать от узла
- Парен: наследовать от узла
Для всех узлов существует виртуальная функция, называемая eval (). Если вы вызовете эту функцию, она вернет значение этого подвыражения.
Я не буду давать ответ, но Стандартное Плохое Решение включает в себя использование переключателя или определения случая (или просто хорошего старомодного каскадного ifs). Немного лучшее решение включает в себя использование таблицы указателей функций, а, вероятно, лучшее решение предполагает использование полиморфизма.
Последние двадцать лет эволюции интерпретаторов можно рассматривать как движение по другому пути - полиморфизм (например, наивные метациркулярные интерпретаторы Smalltalk) к функциям-указателям (реализации наивного lisp, многопоточный код, C ++) для переключения (интерпретаторы наивного байтового кода), а затем и далее. в JIT и т. д. - которые либо требуют очень больших классов, либо (в однополиморфных языках) двойную диспетчеризацию, которая сводит полиморфизм к типу, и вы возвращаетесь на первый этап. Какое определение «лучший» используется здесь?
Для простых вещей полиморфное решение в порядке - вот то, что я сделал ранее , но либо стек, и байт-код / переключатель, либо использование компилятора среды выполнения обычно лучше, если, скажем, вычерчиваете функцию с несколькими тысячами точек данных.
Я думаю, что вопрос о том, как написать анализатор, а не оценщик. Или, скорее, как создать дерево выражений из строки.
Операторы case, которые возвращают базовый класс, точно не учитываются.
Базовая структура «полиморфного» решения (иными словами, мне все равно, с чем вы это создадите, я просто хочу расширить его с помощью переписывания как можно меньшего количества кода) - десериализация иерархии объектов из поток с (динамическим) набором известных типов.
Суть реализации полиморфного решения заключается в том, чтобы иметь способ создания объекта выражения из сопоставителя шаблонов, вероятно, рекурсивного. То есть сопоставить BNF или подобный синтаксис с фабрикой объектов.
Как уже упоминалось ранее, при использовании деревьев выражений паренсы не нужны. Порядок операций становится тривиальным и очевидным, когда вы смотрите на дерево выражений. Парены - это подсказки парсеру.
В то время как принятый ответ является решением одной половины проблемы, другая половина - фактически анализирующая выражение - все еще не решена. Как правило, такого рода проблемы могут быть решены с помощью парсера рекурсивного спуска . Написание такого синтаксического анализатора часто является увлекательным занятием, но большинство современных инструментов для синтаксического анализа языка абстрагируют вас от этого.
Парсер также значительно сложнее, если вы разрешите числа с плавающей точкой в вашей строке. Мне пришлось создать DFA для приема чисел с плавающей запятой в C - это была очень кропотливая и детальная задача. Помните, что допустимые числа с плавающей запятой включают в себя: 10, 10., 10.123, 9.876e-5, 1.0f, .025 и т. Д. Я предполагаю, что некоторые из них (в пользу простоты и краткости) были сделаны в ходе интервью.
Хм ... Я не думаю, что вы можете написать для этого анализатор сверху вниз без возврата назад, так что это должен быть своего рода анализатор с уменьшением сдвига. 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).
Я написал такой парсер с некоторыми базовыми методами, такими как
Infix -> RPN и
Shunting Yard и
Tree Traversals .
Вот реализация, которую я придумал .
Он написан на 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;
}
}
}
}
Хорошо, вот моя наивная реализация. Извините, я не хотел использовать объекты для этого, но его легко конвертировать. Я чувствую себя немного как злой Вилли (из истории Стива).
#!/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()