La Valutazione dell'espressione e Albero a Piedi uso del polimorfismo?(ala Steve Yegge)
https://stackoverflow.com/questions/12516
-
08-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Questa mattina, stavo leggendo Steve Yegge s:Quando Il Polimorfismo Non Riesce, quando mi sono imbattuto in una domanda che un collaboratore del suo usato per chiedere ai potenziali dipendenti quando sono venuto per la loro intervista su Amazon.
Come un esempio di polimorfismo azione, guardiamo il classico "eval" domanda di intervista, che (come quanto ne so) è stato portato a Amazon da Ron Braunstein.La domanda è: molto ricca, come si riesce a sonda di un'ampia varietà di importante competenze:OOP, design, ricorsione, binario alberi, polimorfismo e runtime digitando, generale capacità di codifica, e (se si vuole fare è molto duro) l'analisi di teoria.
A un certo punto, il candidato si spera si rende conto che è possibile rappresentare un espressione aritmetica come un binario albero, supponendo che si sta utilizzando solo gli operatori binari come "+", "-", "*", "/".I nodi foglia sono tutti numeri e i nodi interni sono tutti gli operatori.Valutare l' l'espressione significa camminare albero.Se il candidato non rendersi conto di questo, si può gentilmente li condurrà, o se necessario, basta dire loro.
Anche se dite loro, è ancora un problema interessante.
La prima metà della domanda, che alcune persone (i cui nomi mi proteggere al mio ultimo respiro, ma il loro iniziali sono Willie Lewis) si sentono è un Requisito Professionale Se Si Desidera Chiamare Te Lo Sviluppatore È Al Lavoro Amazon, in realtà è un po ' difficile.Il la domanda è:come si fa a passare da un espressione aritmetica (ad es.in un stringa) come "2 + (2)" per un struttura ad albero dell'espressione.Si può avere un tasto ADJ sfida su questa domanda a un certo punto.
La seconda metà è:diciamo che questo è per 2 persone, un progetto, e il vostro partner, che chiameremo "Willie", è il compito di trasformare l' espressione stringa in un albero.Si ottiene la parte più facile:è necessario decidere cosa classi di Willie è quello di costruire la albero con.Si può fare in qualsiasi lingua, ma assicuratevi di scegliere uno, o Willie sarà invece il montaggio lingua.Se si sente ornery, si sarà per un processore che non è è più in produzione in produzione.
Si sarebbe stupito di come molti candidati boff questo.
Non voglio dare via la risposta, ma una Standard Cattiva Soluzione prevede l'utilizzo di un interruttore o di un caso statment (o solo il buon vecchio stile a cascata-ifs).Un Leggermente Migliore Soluzione comporta utilizzando una tabella di puntatori a funzione, e Probabilmente la Soluzione Migliore comporta l'uso di polimorfismo.Io incoraggia a lavorare attraverso di essa a volte.Roba di divertimento!
Quindi, cerchiamo di affrontare il problema con tutti e tre i modi.Come si fa a passare da un'espressione aritmetica (ad es.in una stringa, ad esempio "2 + (2)" per un'espressione albero con cascata-di se, una tabella di puntatori a funzione, e/o del polimorfismo?
Sentitevi liberi di affrontare uno, due o tutti e tre.
[aggiornamento:titolo modificato per meglio corrispondere a ciò che la maggior parte delle risposte sono state.]
Soluzione
Polimorfici Albero A Piedi, La versione di 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)
I test sono solo costruire gli alberi binari utilizzando i costruttori.
struttura del programma:
classe di base astratta:Nodo
- tutti i Nodi ereditare da questa classe
classe di base astratta:BinaryNode
- tutti gli operatori binari ereditare da questa classe
- metodo di processo il lavoro di evaluting l'espressione e restituisce il risultato
l'operatore binario classi:Più,Meno,Mul,Div
- due nodi figli, uno ciascuno per il lato sinistro e lato destro sottoespressioni
numero di classe:Num
- contiene un nodo foglia valore numerico, ad esempio17 o 42
Altri suggerimenti
Il problema, credo, è che abbiamo bisogno di analizzare perentheses, ma non sono un operatore binario?Dovremmo prendere (2) come un singolo token, che restituisce 2?
Parens non hanno bisogno di presentarsi nella struttura ad albero dell'espressione, ma lo fanno influenzare la loro forma.E. g., l'albero per (1+2)+3 è diverso da 1+(2+3):
+
/ \
+ 3
/ \
1 2
versus
+
/ \
1 +
/ \
2 3
Le parentesi sono un "suggerimento" del parser (ad esempio, per superjoe30, a "scendere in modo ricorsivo")
Questo si ottiene in analisi/la teoria dei compilatori, che è una specie di buco di coniglio... Il Drago Libro è il testo di riferimento per il compilatore di costruzione, e la assume agli estremi.In questo caso particolare, si vuole costruire un grammatica libera dal contesto per l'aritmetica di base, quindi utilizzare tale grammatica analizzare un albero di sintassi astratta.È quindi possibile scorrere l'albero, riducendo il tutto dal basso verso l'alto (è a questo punto devi applicare il polimorfismo/puntatori a funzione/istruzione switch per ridurre l'albero).
Ho trovato queste note per essere incredibilmente utile nel compilatore e l'analisi di teoria.
Che rappresentano i Nodi
Se si desidera includere le parentesi, abbiamo bisogno di 5 tipi di nodi:
il binario nodi:Aggiungere Meno Mul Div
questi hanno due figli, una di sinistra e di destra+ / \ node nodeun nodo per tenere un valore:Val
no nodi figli, solo un valore numericoun nodo per tenere traccia di parens:Paren
un singolo nodo figlio per la sottoespressione( ) | node
Per polimorfi soluzione, abbiamo bisogno di questo tipo di classe di relazione:
- Nodo
- BinaryNode :eredita dal Nodo
- Plus :eredita dal Nodo Binario
- Meno :eredita dal Nodo Binario
- Mul :eredita dal Nodo Binario
- Div :eredita dal Nodo Binario
- Valore :eredita dal Nodo
- Parentesi :eredita dal nodo
C'è una funzione virtuale per tutti i nodi chiamato la funzione eval().Se si chiama questa funzione restituirà il valore di sottoespressioni.
String Tokenizer + LL(1) Parser vi darà un'espressione albero...il polimorfismo modo potrebbe comportare un abstract Aritmetica classe con un "valutare(a,b)" la funzione, che viene sottoposto a override per ciascuno degli operatori coinvolti (Addizione, Sottrazione, ecc) per restituire il valore appropriato, e l'albero contiene numeri Interi e gli operatori Aritmetici, che possono essere valutati da un post(?)-ordine di attraversamento dell'albero.
Non voglio dare via la risposta, ma una Standard Cattiva Soluzione prevede l'utilizzo di un interruttore o di un caso statment (o solo il buon vecchio stile a cascata-ifs).Un Leggermente Migliore Soluzione comporta utilizzando una tabella di puntatori a funzione, e Probabilmente la Soluzione Migliore comporta l'uso di polimorfismo.
Gli ultimi vent'anni di evoluzione, interpreti, può essere visto come sta andando l'altro modo - polimorfismo (ad esempio, ingenuo Smalltalk metacircular interpreti) di puntatori a funzione (ingenuo lisp implementazioni, filettato codice C++) per passare (ingenuo byte di codice interpreti), e poi dopo a JITs e così via - che richiedono molto grandi classi, o (nel singolarmente polimorfici lingue) a doppia spedizione, che riduce il polimorfismo di un tipo di caso, e sei di nuovo in fase uno.Quale definizione di "migliore" è in uso qui?
Per cose semplici polimorfi soluzione è OK - ecco quello che ho fatto in precedenza, ma uno stack e bytecode/switch o sfruttando il runtime compilatore di solito è meglio se si, dire, tracciando una funzione con poche migliaia di punti dati.
Hm...Io non credo che si possa scrivere un parser per questo senza backtracking, quindi deve essere una sorta di shift-ridurre il parser.LR(1) o anche LALR funziona benissimo con la seguente (ad-hoc) la definizione di lingua:
Start -> E1
E1 -> E1+E1 | E1-E1
E1> E2*E2 | E2/E2 | E2
E2 -> numero | (E1)
La separazione in E1 e E2 è necessario per mantenere il primato del * e / over + e -.
Ma questo è come lo farei se dovessi scrivere il parser mano:
- Due pile, una memorizzazione di nodi dell'albero come operandi e una memorizzazione di operatori
- Leggere l'input da sinistra a destra, fare i nodi foglia di numeri e li spingono in operand stack.
- Se avete >= 2 operandi in pila, pop 2, li combinano con il primo operatore in operatore stack e spingere questa struttura nuovamente l'operando albero, a meno che non
- La prossima operatore ha una precedenza maggiore che quello attualmente in cima alla pila.
Questo lascia a noi il problema di gestire le staffe.Un elegante (ho pensato) la soluzione è quella di memorizzare la priorità di ogni operatore di un numero in una variabile.Quindi, inizialmente,
- int plus, minus = 1;
- int mul, div = 2;
Ora ogni volta che vedi una staffa sinistra incremento di tutte queste variabili da 2, e ogni volta che vedi una staffa destra, il decremento di tutte le variabili da 2.
Questo farà sì che il + 3*(4+5) ha una priorità più alta l' * e 3*4 non sarà inserito nello stack.Invece si dovrà attendere il 5, push 4+5, quindi spingere 3*(4+5).
Re:Justin
Penso che l'albero sarebbe simile a questa:
+
/ \
2 ( )
|
2
In sostanza, si avrebbe un "eval" nodo, che appena valuta l'albero al di sotto di esso.Che poi è ottimizzato per essere solo:
+
/ \
2 2
In questo caso le parentesi non sono necessarie e non aggiungono nulla.Non aggiunge nulla, logicamente, in modo che sarebbe solo andare via.
Penso che la domanda è su come scrivere un parser, non valutatore.O piuttosto, come creare la struttura ad albero dell'espressione da una stringa.
Caso di dichiarazioni che restituiscono una classe base non è esattamente conteggio.
La struttura di base di un "polimorfico" soluzione (che è un altro modo di dire, io non cura ciò che si costruisce con questo, voglio solo estendere con riscrivere la quantità minima di codice possibile) è la deserializzazione di un oggetto gerarchia da un flusso (dinamico) set di tipi conosciuti.
Il punto cruciale dell'attuazione del polimorfici soluzione è avere un modo per creare un oggetto di espressione di un pattern matcher, probabilmente ricorsiva.I. e., mappa un BNF o sintassi simile a un oggetto di fabbrica.
O forse questa è la vera domanda:come si può rappresentare (2) come un BST?Quella è la parte che è inciampare me up.
La ricorsione.
@Justin:
Guarda la mia nota a rappresentare i nodi.Se si utilizza questo schema, quindi
2 + (2)
può essere rappresentato come
.
/ \
2 ( )
|
2
dovrebbe usare un linguaggio funzionale imo.Gli alberi sono più difficili da rappresentare e manipolare in linguaggi OO.
Come le persone hanno mai menzionato in precedenza, quando si utilizza l'espressione alberi parentesi non sono necessarie.L'ordine delle operazioni, diventa banale e scontato quando stai guardando una struttura ad albero dell'espressione.Le parentesi sono suggerimenti per il parser.
Mentre il accettato la risposta è la soluzione per la metà del problema, l'altra metà - analizzare l'espressione - è ancora irrisolto.In genere, questi tipi di problemi possono essere risolti utilizzando un recursive descent parser.Scrivere un parser è spesso un esercizio divertente, ma la maggior parte i moderni strumenti di analisi per la lingua si astratto che fa per voi.
Il parser è anche significativamente più difficile, se ti permetti di numeri in virgola mobile in una stringa.Ho dovuto creare un DFA ad accettare numeri in virgola mobile in C -- è stata molto accurata e dettagliata attività.Ricordate, valido floating point includono:10, 10., 10.123, 9.876 e-5, 1.0 f, .025, etc.Presumo che qualche dispensa da questo (a favore di semplicità e brevità) è stato fatto nell'intervista.
Ho scritto ad un parser con alcune tecniche di base come
Infisso -> RPN e
Manovra Cantiere e
Albero Di Attraversamenti Di.
Qui è l'implementazione che ho venuto con.
È scritto in C++ e compila sia su Linux che su Windows.
Eventuali suggerimenti/domande sono i benvenuti.
Quindi, cerchiamo di affrontare il problema con tutti e tre i modi.Come si fa a passare da un'espressione aritmetica (ad es.in una stringa, ad esempio "2 + (2)" per un'espressione albero con cascata-di se, una tabella di puntatori a funzione, e/o del polimorfismo?
Questo è interessante,ma non credo che questo appartiene al regno della programmazione object-oriented...io penso che abbia più a che fare con l'analisi tecniche.
Ho buttato questa console c# app insieme, come un po ' una prova di concetto.Una sensazione potrebbe essere molto meglio (che istruzione switch in GetNode è una specie di goffo (c'è coz mi ha colpito un vuoto cercando di mappare un nome di classe per l'operatore)).Qualche suggerimento su come potrebbe essere migliorato molto benvenuto.
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, ecco il mio ingenuo attuazione.Scusate, non mi sento di usare gli oggetti per quello, ma è facile da convertire.Mi sento un po ' male Willy (da la storia di Steve).
#!/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()
