Expression Evaluation und Baum-Walking-Polymorphismus?(ala Steve Yegge)
https://stackoverflow.com/questions/12516
-
08-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Heute morgen war ich Lesen Steve Yegge ist:Wenn Polymorphismus Fehl,, wenn ich stieß auf eine Frage, die von einem co-worker sein verwendet, um Fragen Sie potenzielle Mitarbeiter, wenn Sie kam für Ihr interview bei Amazon.
Als ein Beispiel für Polymorphismus in Aktion, schauen wir uns die Klassiker "eval" - interview die Frage, welche (wie soweit ich weiß), war gebracht zu Amazon von Ron Braunstein.Die Frage ist ziemlich Reich ein, wie es gelingt Sonde eine Vielzahl von wichtig Fähigkeiten:OOP design, Rekursion, binary Bäume, Polymorphismus und Laufzeit Eingabe, general coding-Fähigkeiten zu verbessern, und (wenn Sie möchten zu machen es extra hart) parsing-Theorie.
An einem gewissen Punkt, der Kandidat hoffentlich merkt, dass Sie darstellen kann, eine arithmetischer Ausdruck als binäre Baum, vorausgesetzt, Sie sind nur mit binäre Operatoren wie "+", "-", "*", "/".Die Blattknoten sind alle zahlen, und die inneren Knoten sind alle Betreiber.Die Bewertung der Ausdruck bedeutet Fuß des Baumes.Wenn der Kandidat nicht dies zu realisieren, Sie können leicht dazu führen, dass Sie es sind, oder wenn notwendig, einfach sagen Sie.
Auch wenn man Ihnen sagt, es ist immer noch ein Interessantes problem.
Die erste Hälfte der Frage, welche einige Leute (deren Namen ich schützen zu meinem sterbenden Atem, aber Ihre Initialen sind Willie Lewis) ist ein Gefühl Job Anforderung, Wenn Sie Anrufen Möchten Selbst Ein Entwickler Und Arbeit In Amazon ist eigentlich ein bisschen hart.Die Frage:wie gehen Sie von einem arithmetischer Ausdruck (z.B.in einem string) wie "2 + (2)", um ein expression tree.Wir haben vielleicht ein ADJ die Herausforderung bei dieser Frage an einigen Punkt.
Die zweite Hälfte:lassen Sie uns sagen, das ein 2-Personen-Projekt, und Ihr partner, die nennen wir "Willie", ist verantwortlich für die Umgestaltung der string-Ausdruck, der in einen Baum.Sie erhalten der einfache Teil:Sie müssen entscheiden, was Klassen Willie zu konstruieren, die Baum mit.Sie können es in jeder Sprache, aber stellen Sie sicher, dass Sie ein pick, oder Willie erhalten Sie Montage - Sprache.Wenn er das Gefühl ornery, es für einen Prozessor, der nicht mehr hergestellt bei der Produktion.
Sie würden überrascht sein, wie viele Bewerber boff diese ein.
Ich werde nicht verraten, die Antwort, aber eine Standard-Bad-Lösung beinhaltet die Verwendung eines switch-oder case-Anweisung (oder einfach nur gute altmodische kaskadiert-ifs).Ein Etwas Bessere Lösung besteht im mit Hilfe einer Tabelle von Funktionszeigern, und die Wahrscheinlich Beste Lösung umfasst die Verwendung von Polymorphismus.Ich ermutigen Sie es irgendwann.Fun stuff!
Also, lassen Sie uns versuchen, um das problem anzugehen alle drei Möglichkeiten.Wie gehen Sie von einem arithmetischen Ausdruck (z.B.in einer Zeichenfolge) wie "2 + (2)", um einen Ausdruck Baum mittels kaskadierter-wenn eine Tabelle von Funktionszeigern und/oder Polymorphie?
Feel free to tackle ein, zwei, oder alle drei.
[update:Titel geändert, um besser mit dem übereinstimmen, was die meisten Antworten wurden.]
Lösung
Polymorphe Struktur Zu Fuß, Python version
#!/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)
Die tests sind nur Gebäude bis die binäre Bäume durch die Verwendung von Konstruktoren.
Programm-Struktur:
abstrakte Basisklasse:Knoten
- alle Knoten, die von dieser Klasse Erben aus
abstrakte Basisklasse:BinaryNode
- alle binären Operatoren Erben von dieser Klasse
- Prozess Methode ist die Arbeit des evaluting den Ausdruck aus und gibt das Ergebnis zurück
binärer operator-Klassen:Plus,Minus,Mul,Div
- zwei untergeordnete Knoten, jeweils eine für Links und rechts Teilausdrücke
Anzahl Klassen:Num
- hält ein Blatt-Knoten numerischer Wert, z.B.17 42
Andere Tipps
Das problem, das ich denke, ist, dass wir brauchen, um zu analysieren perentheses, und doch sind Sie nicht ein binärer operator?Sollten wir uns nehmen (2) als ein einzelnes token, das ergibt 2?
Die Klammern brauchen nicht zu zeigen, bis Sie in der expression tree, aber Sie wirken auf seine Form.E. g., der Baum (1+2)+3 unterscheidet sich von 1+(2+3):
+
/ \
+ 3
/ \
1 2
versus
+
/ \
1 +
/ \
2 3
Die Klammern sind ein "Tipp", um den parser (z.B., pro superjoe30, um "Rekursives absteigen")
Diese wird in Analyse/compiler-Theorie, die ist Art von ein Kaninchen Loch... Der Drache-Buch ist das standard-text für Compilerbau und nimmt diese auf die Spitze.In diesem speziellen Fall möchten Sie bauen ein Kontext-freie Grammatik für grundlegende Arithmetik, verwenden Sie dann die Grammatik zu analysieren eines abstract syntax tree.Sie können dann Durchlaufen Sie den Baum, wodurch es von unten nach oben (es ist an dieser Stelle, Sie würde gelten, die Polymorphismus/Funktionszeiger/switch-Anweisung zur Verringerung der Baum).
Ich habe gefunden diese Hinweise unglaublich nützlich zu sein, in der compiler-und Analyse-Theorie.
Repräsentieren die Knoten
Wenn wir wollen Klammern benötigen wir 5 Arten von Knoten:
die binäre Knoten:Hinzufügen, Minus, Mul Div
diese haben zwei Kinder, einen linken und rechten Seite+ / \ node nodeein Knoten einen Wert:Val
keine Kinder Knoten Sie einfach einen numerischen Werteinen Knoten zu verfolgen, die parens:Klammer
einen einzelnen untergeordneten Knoten für den Teilausdruck( ) | node
Für eine polymorphe Lösung, wir müssen diese Art von Klasse Beziehung:
- Knoten
- BinaryNode :Erben von Knoten
- Plus :Erben von Binären Knoten
- Minus :Erben von Binären Knoten
- Mul :Erben von Binären Knoten
- Div :Erben von Binären Knoten
- Wert :Erben von Knoten
- Teil :Erben von Knoten
Es ist eine virtuelle Funktion für alle Knoten genannt eval().Rufen Sie diese Funktion, wird es wieder den Wert der Teilausdruck.
String-Tokenizer + LL(1) Parser geben Sie einen Ausdruck Baum...der Polymorphismus Weg könnte darin bestehen, eine abstrakte Arithmetik-Klasse mit einem "zu bewerten(a,b)" - Funktion, die überschrieben wird für jede der beteiligten (Addition, Subtraktion usw.), um den entsprechenden Wert, und der Baum enthält ganze zahlen und Arithmetischen Operatoren, die ausgewertet werden können durch post(?)-um traversal) des Baums.
Ich werde nicht verraten, die Antwort, aber eine Standard-Bad-Lösung beinhaltet die Verwendung eines switch-oder case-Anweisung (oder einfach nur gute altmodische kaskadiert-ifs).Ein Etwas Bessere Lösung besteht im mit Hilfe einer Tabelle von Funktionszeigern, und die Wahrscheinlich Beste Lösung umfasst die Verwendung von Polymorphismus.
Die letzten zwanzig Jahre der Entwicklung von Dolmetschern kann gesehen werden als in die andere Richtung - Polymorphismus (z.B. naive Smalltalk metacircular Dolmetscher) zu Funktionszeigern (naive lisp-Implementierungen, threaded-code, C++) switch (naive byte-code-Interpreter), und dann weiter zu E und so weiter -, die entweder eine sehr große Klassen, oder (einzeln polymorphe Sprachen) Doppel-Versand, der reduziert den Polymorphismus zu einer Art Fall, und Sie sind zurück auf Stufe eins.Was ist die definition von "best" ist hier im Einsatz?
Für einfache Sachen eine polymorphe Lösung ist OK - hier ist eine, die ich früher gemacht, aber entweder stack und der bytecode - / - Schalter oder die Nutzung der runtime-compiler ist in der Regel besser, wenn man, sagen wir, Plotten einer Funktion mit ein paar tausend Datenpunkten.
Hm...Ich glaube nicht, dass Sie schreiben können, einen top-down-parser für diese ohne backtracking, so es hat eine Art von einem shift-reduce-parser.LR(1) - oder sogar LALR natürlich funktioniert das gut mit der folgenden (ad-hoc) Sprache definition:
Start -> E1
E1 -> E1+E1 | E1-E1
E1 -> E2*E2 | E2/E2 | E2
E2 -> Anzahl | (E1)
Trennen Sie es in E1 und E2 ist notwendig, um die Priorität von * und / über + und -.
Aber das ist, wie ich es tun würde, wenn ich schreiben musste der parser von hand:
- Zwei Stapel, die eine Speicherung von Knoten des Baumes als Operanden und eine Speicherung von Operatoren
- Lesen Sie die Eingabe von Links nach rechts, stellen Sie Blattknoten der Zahl, und schieben Sie Sie in den Operanden stack ein.
- Wenn Sie >= 2 Operanden auf dem stack, pop 2, kombinieren Sie mit dem obersten operator-in operator-stack und schieben diese Struktur wieder auf die Operanden-Baum, es sei denn,
- Der next-operator hat eine höhere Priorität gibt, der gerade oben auf dem Stapel.
Dies lässt uns das problem der Umgang mit Klammern.Eine elegante (dachte ich) Lösung zum speichern der Rangfolge der jeweiligen Betreiber, wie eine Zahl in einer Variablen.Also anfangs
- int plus, minus = 1;
- int mul, div = 2;
Jetzt jedes mal, wenn Sie sehen eine linke Klammer Schrittweite alle diese Variablen durch 2, und jedes mal, wenn Sie sehen, eine Klammer, Dekrementieren alle Variablen durch 2.
Dadurch wird sichergestellt, dass das + 3*(4+5) hat eine höhere Priorität als das * und 3*4 wird nicht auf dem Stapel abgelegt.Stattdessen wird es warten, bis 5 push 4+5, und drücken Sie anschließend 3*(4+5).
Re:Justin
Ich denke, der Baum würde in etwa so Aussehen:
+
/ \
2 ( )
|
2
Im Grunde, Sie hätten eine "eval" - Knoten, die nur ausgewertet, den Baum darunter.Das wäre dann optimiert sich zu einfach:
+
/ \
2 2
In diesem Fall werden die Klammern sind nicht erforderlich, und nichts hinzufügen.Sie sich nicht alles logisch, so würden Sie einfach Weg.
Ich denke, die Frage ist wie schreiben Sie einen parser, der nicht der Gutachter.Oder vielmehr, wie der Ausdruck-Baum aus einem string.
Case-Anweisungen, die eine Basisklasse nicht genau zählen.
Die grundlegende Struktur einer "polymorphen" Lösung (das ist eine andere Art zu sagen, ich don ' T care, was Sie bauen, diese mit, ich will nur, Sie zu verlängern mit dem umschreiben der geringsten Menge an code möglich) ist Deserialisieren Objekt-Hierarchie aus einem stream mit einem (dynamischen) Gruppe von bekannten Arten.
Die crux an der Umsetzung der polymorphen Lösung ist ein Weg, um einen Ausdruck zu erstellen Objekt aus einer pattern-matcher, wahrscheinlich rekursiv.I. e., anzeigen in BNF oder ähnliche syntax, um ein Objekt factory.
Oder vielleicht ist die eigentliche Frage:wie können Sie darstellen, (2) als BST?Das ist der Teil, der mich stolpern bis.
Rekursion.
@Justin:
Blick auf meine Hinweis auf die Darstellung der Knoten.Wenn Sie dieses Schema, dann
2 + (2)
kann als dargestellt werden
.
/ \
2 ( )
|
2
sollte eine funktionale Sprache, imo.Bäume sind schwerer zu erklären und zu manipulieren, die in OO-Sprachen.
Als Menschen haben zu erwähnen, wenn Sie bisher verwenden von ausdrucksbaumstrukturen Klammern sind nicht erforderlich.Die Reihenfolge der Operationen banal und offensichtlich, wenn Sie ein expression tree.Die Klammern sind Hinweise für den parser.
Während die akzeptierte Antwort ist die Lösung für die Hälfte des Problems, die andere Hälfte - eigentlich Parsen des Ausdrucks ist immer noch ungelöst.In der Regel werden diese Arten von Problemen behoben werden können, mit einer rekursiver Abstieg parser.Schreiben wie ein parser ist oft eine lustige übung, aber die meisten moderne Werkzeuge für die Sprache analysieren wird Abstrakt, dass Weg für Sie.
Der parser ist auch deutlich härter, wenn Sie zulassen, dass floating-point-zahlen in Ihrem string.Ich hatte zum erstellen eines DFA zu akzeptieren, floating-point-zahlen in C-es war eine sehr sorgfältige und detaillierte Aufgabe.Denken Sie daran, gültig schwimmende Punkte umfassen:10, 10., 10.123, 9.876 e-5, 1.0 f, .025, etc.Ich nehme an, einige Dispens von diesem (zu Gunsten von simplicty und Kürze) gemacht wurde, im interview.
Ich habe geschrieben wie ein parser mit einigen grundlegenden Techniken wie
Infix -> RPN und
Rangierbahnhof und
Tree Traversals.
Hier ist die Implementierung, die ich habe, kam mit.
Es ist in C++ geschrieben und kompiliert auf Linux-und Microsoft Windows.
Irgendwelche Vorschläge/Fragen sind willkommen.
Also, lassen Sie uns versuchen, um das problem anzugehen alle drei Möglichkeiten.Wie gehen Sie von einem arithmetischen Ausdruck (z.B.in einer Zeichenfolge) wie "2 + (2)", um einen Ausdruck Baum mittels kaskadierter-wenn eine Tabelle von Funktionszeigern und/oder Polymorphie?
Dies ist interessant,aber ich glaube nicht, das gehört in den Bereich der Objekt-orientierten Programmierung...ich denke, es hat mehr zu tun mit parsing-Techniken.
Ich habe irgendwie eingespannt dieser c# - Konsolen-app zusammen, ein wenig wie ein proof of concept.Habe das Gefühl, es könnte viel besser sein (die switch-Anweisung in GetNode ist irgendwie klobig (es ist, es coz ich traf eine leere versuchen, zu Karte der name einer Klasse an einen Betreiber)).Irgendwelche Vorschläge, wie es verbessert werden könnte, sehr willkommen.
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;
}
}
}
}
Ok, hier ist meine naive Implementierung.Sorry, ich habe nicht das Gefühl, Objekte für diese ein, aber es ist einfach zu konvertieren.Ich fühle mich ein bisschen wie böse Willy (von Steve ' s story).
#!/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()
