Évaluation d'expression et marche dans les arbres à l'aide du polymorphisme ?(comme Steve Yegge)
https://stackoverflow.com/questions/12516
-
08-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Ce matin, je lisais Celui de Steve Yegge :Quand le polymorphisme échoue, lorsque je suis tombé sur une question qu'un de ses collègues posait à des employés potentiels lorsqu'ils venaient pour leur entretien chez Amazon.
À titre d'exemple de polymorphisme en action, regardons la question de l'interview classique "Eval", qui (pour autant que je sache) a été amenée à Amazon par Ron Braunstein.La question est assez riche, car elle parvient à sonder une grande variété de compétences importantes:Conception de la POT, récursivité, arbres binaires, polymorphisme et typage d'exécution, compétences en codage général et (si vous voulez le rendre très difficile) de la théorie de l'analyse.
À un moment donné, le candidat se rendra compte que vous pouvez représenter une expression arithmétique en tant qu'arbre binaire, en supposant que vous n'utilisez que des opérateurs binaires tels que "+", "-", "*", "/".Les nœuds de feuilles sont tous des nombres et les nœuds internes sont tous des opérateurs.Évaluer l'expression signifie marcher sur l'arbre.Si le candidat ne s'en rend pas compte, vous pouvez le conduire doucement, ou si nécessaire, dites-le simplement.
Même si vous leur dites, c'est toujours un problème intéressant.
La première moitié de la question, que certaines personnes (dont je protégerai les noms à mon souffle mourant, mais leurs initiales sont Willie Lewis) est une exigence d'emploi si vous voulez vous appeler un développeur et travailler chez Amazon, est en fait un peu difficile .La question est:Comment allez-vous d'une expression arithmétique (par exempledans une chaîne) comme "2 + (2)" à un arbre d'expression.Nous pouvons avoir un défi ADJ sur cette question à un moment donné.
La seconde moitié est :Disons qu'il s'agit d'un projet à 2 personnes, et votre partenaire, que nous appellerons "Willie", est responsable de la transformation de l'expression de la chaîne en arbre.Vous obtenez la partie facile:Vous devez décider avec quelles classes Willie doit construire l'arbre.Vous pouvez le faire dans n'importe quelle langue, mais assurez-vous d'en choisir un, ou Willie vous remettra un langage d'assemblage.S'il se sent à l'abri, ce sera pour un processeur qui n'est plus fabriqué en production.
Vous seriez étonné du nombre de candidats Boff celui-ci.
Je ne donnerai pas la réponse, mais une mauvaise solution standard implique l'utilisation d'un interrupteur ou d'une déclaration de cas (ou tout simplement de bonnes IF en cascade à l'ancienne).Une solution légèrement meilleure implique d'utiliser un tableau de pointeurs de fonction, et la meilleure solution implique probablement d'utiliser le polymorphisme.Je vous encourage à y travailler un jour.Truc amusant!
Essayons donc d’aborder le problème de trois manières.Comment passe-t-on d’une expression arithmétique (ex.dans une chaîne) telle que « 2 + (2) » vers un arbre d'expression utilisant des cas en cascade, une table de pointeurs de fonction et/ou un polymorphisme ?
N'hésitez pas à en aborder un, deux ou les trois.
[mise à jour:titre modifié pour mieux correspondre à la plupart des réponses.]
La solution
Marche dans les arbres polymorphes, version 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)
Les tests construisent simplement les arbres binaires en utilisant des constructeurs.
Structure du programme :
classe de base abstraite :Nœud
- tous les nœuds héritent de cette classe
classe de base abstraite :Nœud Binaire
- tous les opérateurs binaires héritent de cette classe
- La méthode process effectue le travail d'évaluation de l'expression et renvoie le résultat.
classes d'opérateurs binaires :Plus, Moins, Mul, Div
- deux nœuds enfants, un pour les sous-expressions du côté gauche et du côté droit
classe de nombres :Numéro
- contient une valeur numérique de nœud feuille, par ex.17 ou 42
Autres conseils
Le problème, je pense, est que nous devons analyser les pérenthèses, et pourtant elles ne sont pas un opérateur binaire ?Devrions-nous prendre (2) comme un jeton unique, qui vaut 2 ?
Les parenthèses n'ont pas besoin d'apparaître dans l'arbre d'expression, mais elles affectent sa forme.Par exemple, l'arbre pour (1+2)+3 est différent de 1+(2+3) :
+
/ \
+ 3
/ \
1 2
contre
+
/ \
1 +
/ \
2 3
Les parenthèses sont un "indice" pour l'analyseur (par exemple, selon superjoe30, pour "descendre de manière récursive")
Cela entre dans la théorie de l'analyse syntaxique/du compilateur, qui est une sorte de terrier de lapin... Le livre des dragons est le texte standard pour la construction d'un compilateur, et il pousse cela à l'extrême.Dans ce cas particulier, vous souhaitez construire un grammaire sans contexte pour l'arithmétique de base, puis utilisez cette grammaire pour analyser un arbre de syntaxe abstraite.Vous pouvez ensuite parcourir l'arbre, en le réduisant de bas en haut (c'est à ce stade que vous appliquerez l'instruction polymorphisme/pointeurs de fonction/switch pour réduire l'arbre).
J'ai trouvé ces notes pour être incroyablement utile dans la théorie du compilateur et de l’analyse syntaxique.
Représenter les nœuds
Si nous voulons inclure des parenthèses, nous avons besoin de 5 types de nœuds :
les nœuds binaires :Ajouter moins Mul Div
ils ont deux enfants, un côté gauche et un côté droit+ / \ node nodeun nœud pour contenir une valeur :Val
pas de nœuds enfants, juste une valeur numériqueun nœud pour garder une trace des parenthèses :Paren
un seul nœud enfant pour la sous-expression( ) | node
Pour une solution polymorphe, nous avons besoin de ce type de relation de classe :
- Nœud
- Nœud Binaire :hériter de Node
- Plus :hériter du nœud binaire
- Moins :hériter du nœud binaire
- Mul :hériter du nœud binaire
- Div :hériter du nœud binaire
- Valeur :hériter de Node
- Paren :hériter du nœud
Il existe une fonction virtuelle pour tous les nœuds appelée eval().Si vous appelez cette fonction, elle renverra la valeur de cette sous-expression.
String Tokenizer + LL(1) Parser vous donnera un arbre d'expression...la méthode du polymorphisme peut impliquer une classe arithmétique abstraite avec une fonction "évaluer (a, b)", qui est remplacée pour chacun des opérateurs impliqués (addition, soustraction, etc.) pour renvoyer la valeur appropriée, et l'arbre contient des entiers et des opérateurs arithmétiques , qui peut être évalué par un parcours post-(?)-ordre de l'arbre.
Je ne donnerai pas la réponse, mais une mauvaise solution standard implique l'utilisation d'un interrupteur ou d'une déclaration de cas (ou tout simplement de bonnes IF en cascade à l'ancienne).Une solution légèrement meilleure implique d'utiliser un tableau de pointeurs de fonction, et la meilleure solution implique probablement d'utiliser le polymorphisme.
Les vingt dernières années d'évolution des interpréteurs peuvent être considérées comme allant dans l'autre sens - du polymorphisme (par exemple, les interpréteurs métacirculaires naïfs Smalltalk) aux pointeurs de fonction (implémentations naïves de Lisp, code threadé, C++) pour basculer (interpréteurs de code d'octet naïfs), puis au-delà. aux JIT, etc. - qui nécessitent soit de très grandes classes, soit (dans les langages polymorphes) une double répartition, ce qui réduit le polymorphisme à un cas de type, et vous êtes de retour à la première étape.Quelle définition du « meilleur » est utilisée ici ?
Pour des choses simples, une solution polymorphe est OK - en voici un que j'ai fait plus tôt, mais soit empiler et bytecode/switch, soit exploiter le compilateur du runtime est généralement préférable si vous tracez, par exemple, une fonction avec quelques milliers de points de données.
Hum...Je ne pense pas que vous puissiez écrire un analyseur descendant pour cela sans revenir en arrière, il doit donc s'agir d'une sorte d'analyseur à réduction de décalage.LR(1) ou même LALR fonctionneront bien sûr très bien avec la définition de langage (ad hoc) suivante :
Démarrer -> E1
E1 -> E1 + E1 | E1-E1
E1 -> E2 * E2 | E2 / E2 | E2
E2 -> nombre | (E1)
Le séparer en E1 et E2 est nécessaire pour maintenir la priorité de * et / sur + et -.
Mais voici comment je procéderais si je devais écrire l'analyseur à la main :
- Deux piles, une stockant les nœuds de l'arbre comme opérandes et une stockant les opérateurs
- Lisez l'entrée de gauche à droite, créez des nœuds feuilles des nombres et placez-les dans la pile d'opérandes.
- Si vous avez >= 2 opérandes sur la pile, affichez-en 2, combinez-les avec l'opérateur le plus haut de la pile d'opérateurs et repoussez cette structure dans l'arborescence des opérandes, sauf si
- L'opérateur suivant a une priorité plus élevée que celui actuellement en haut de la pile.
Cela nous laisse le problème de la gestion des supports.Une solution élégante (je pensais) consiste à stocker la priorité de chaque opérateur sous forme de nombre dans une variable.Donc au départ,
- int plus, moins = 1 ;
- int mul, div = 2 ;
Désormais, chaque fois que vous voyez un crochet gauche, incrémentez toutes ces variables de 2, et chaque fois que vous voyez un crochet droit, décrémentez toutes les variables de 2.
Cela garantira que le + dans 3*(4+5) a une priorité plus élevée que le *, et que 3*4 ne sera pas poussé sur la pile.Au lieu de cela, il attendra 5, appuiera sur 4+5, puis appuiera sur 3*(4+5).
Concernant:Justin
Je pense que l'arbre ressemblerait à ceci :
+
/ \
2 ( )
|
2
Fondamentalement, vous auriez un nœud "eval", qui évalue simplement l'arborescence située en dessous.Cela serait alors optimisé pour être simplement :
+
/ \
2 2
Dans ce cas, les parenthèses ne sont pas obligatoires et n'ajoutent rien.Ils n’ajoutent rien logiquement, donc ils s’en vont.
Je pense que la question est de savoir comment écrire un analyseur, pas un évaluateur.Ou plutôt, comment créer l'arbre d'expression à partir d'une chaîne.
Les instructions Case qui renvoient une classe de base ne comptent pas exactement.
La structure de base d'une solution "polymorphe" (ce qui est une autre façon de dire, peu importe avec quoi vous construisez cela, je veux juste l'étendre en réécrivant le moins de code possible) consiste à désérialiser une hiérarchie d'objets à partir d'un flux avec un ensemble (dynamique) de types connus.
Le point crucial de la mise en œuvre de la solution polymorphe est d'avoir un moyen de créer un objet d'expression à partir d'un outil de correspondance de modèles, probablement récursif.C'est-à-dire mapper un BNF ou une syntaxe similaire à une fabrique d'objets.
Ou peut-être est-ce là la vraie question :comment pouvez-vous représenter (2) comme un BST ?C'est la partie qui me fait trébucher.
Récursion.
@Justin:
Regardez ma note sur la représentation des nœuds.Si vous utilisez ce schéma, alors
2 + (2)
peut être représenté comme
.
/ \
2 ( )
|
2
devrait utiliser un langage fonctionnel imo.Les arbres sont plus difficiles à représenter et à manipuler dans les langages OO.
Comme les gens l'ont mentionné précédemment, lorsque vous utilisez des arbres d'expression, les parenthèses ne sont pas nécessaires.L'ordre des opérations devient trivial et évident lorsque vous examinez un arbre d'expression.Les parenthèses sont des indices pour l'analyseur.
Alors que la réponse acceptée est la solution à la moitié du problème, l’autre moitié – en analysant l’expression – n’est toujours pas résolue.Généralement, ce genre de problèmes peut être résolu à l'aide d'un analyseur de descente récursive.Écrire un tel analyseur est souvent un exercice amusant, mais la plupart outils modernes pour l'analyse linguistique je vais résumer cela pour vous.
L'analyseur est également significativement plus difficile si vous autorisez les nombres à virgule flottante dans votre chaîne.J'ai dû créer un DFA pour accepter les nombres à virgule flottante en C : c'était une tâche très minutieuse et détaillée.N'oubliez pas que les virgules flottantes valides incluent :10, 10., 10.123, 9.876e-5, 1.0f, .025, etc.Je suppose qu'une certaine dérogation à cela (en faveur de la simplicité et de la brièveté) a été faite lors de l'entretien.
J'ai écrit un tel analyseur avec quelques techniques de base commeInfixe -> RPN etGare de triage etTraversées d'arbres.
Voici l'implémentation que j'ai proposée.
Il est écrit en C++ et se compile sous Linux et Windows.
Toutes les suggestions/questions sont les bienvenues.
Essayons donc d’aborder le problème de trois manières.Comment passe-t-on d’une expression arithmétique (ex.dans une chaîne) telle que « 2 + (2) » vers un arbre d'expression utilisant des cas en cascade, une table de pointeurs de fonction et/ou un polymorphisme ?
C'est intéressant, mais je ne pense pas que cela appartienne au domaine de la programmation orientée objet... Je pense que cela a plus à voir avec techniques d'analyse.
J'ai en quelque sorte rassemblé cette application de console C# comme une sorte de preuve de concept.J'ai le sentiment que cela pourrait être bien mieux (cette instruction switch dans GetNode est un peu maladroite (elle est là parce que j'ai frappé un blanc en essayant de mapper un nom de classe à un opérateur)).Toutes les suggestions sur la façon dont cela pourrait être amélioré sont les bienvenues.
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, voici ma mise en œuvre naïve.Désolé, je n'ai pas eu envie d'utiliser d'objets pour celui-là mais c'est facile à convertir.Je me sens un peu comme le méchant Willy (de l'histoire de 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()
