oop - ¿Evaluación de expresión y caminata de árbol usando polimorfismo?(ala Steve Yegge)
recursion polymorphism (16)
Esta mañana estaba leyendo Steve Yegge: Cuando falla el polimorfismo , me encontré con una pregunta que un compañero de trabajo solía preguntar a posibles empleados cuando venían a su entrevista en Amazon.
Como un ejemplo de polimorfismo en acción, veamos la clásica pregunta de entrevista "eval", que (hasta donde sé) fue traída a Amazon por Ron Braunstein. La pregunta es bastante rica, ya que logra sondear una amplia variedad de habilidades importantes: diseño OOP, recursión, árboles binarios, polimorfismo y tipado en tiempo de ejecución, habilidades generales de codificación y (si quieres hacerlo más difícil) teoría de análisis .
En algún momento, el candidato se da cuenta de que puede representar una expresión aritmética como un árbol binario, suponiendo que solo está utilizando operadores binarios como "+", "-", "*", "/". Los nodos de hoja son todos números, y los nodos internos son todos operadores. Evaluar la expresión significa caminar por el árbol. Si el candidato no se da cuenta de esto, puede guiarlo suavemente hacia él o, si es necesario, simplemente dígalo.
Incluso si les dices, sigue siendo un problema interesante.
La primera mitad de la pregunta, que algunas personas (cuyos nombres voy a proteger a mi último aliento, pero sus iniciales son Willie Lewis) sienten que es un requisito de trabajo si quieres llamarte desarrollador y trabajar en Amazon, en realidad es un poco difícil . La pregunta es: ¿cómo se pasa de una expresión aritmética (por ejemplo, en una cadena) como "2 + (2)" a un árbol de expresiones. Es posible que tengamos un desafío de ADJ sobre esta cuestión en algún momento.
La segunda mitad es: digamos que este es un proyecto de 2 personas, y su compañero, a quien llamaremos "Willie", es responsable de transformar la expresión de cadena en un árbol. Obtienes la parte fácil: debes decidir con Willie qué clases va a construir el árbol. Puedes hacerlo en cualquier idioma, pero asegúrate de elegir uno o Willie te dará el lenguaje ensamblador. Si se siente malvado, será para un procesador que ya no se fabrica en producción.
Te sorprendería ver cuántos candidatos se quitan esta.
No daré la respuesta, pero una Solución Estándar Malo implica el uso de un interruptor o una declaración de caso (o simplemente buenos anticuados en cascada). Una Solución Ligeramente Mejor implica el uso de una tabla de indicadores de función, y la Solución Probablemente Mejor implica el uso de polimorfismo. Te animo a que lo resuelvas en algún momento. ¡Cosas divertidas!
Entonces, intentemos abordar el problema de las tres maneras. ¿Cómo se pasa de una expresión aritmética (por ejemplo, en una cadena) como "2 + (2)" a un árbol de expresiones usando cascadas-if, una tabla de punteros a las funciones y / o polimorfismo?
Siéntase libre de abordar uno, dos o los tres.
[actualización: título modificado para que coincida mejor con la mayoría de las respuestas].
El problema, creo, es que tenemos que analizar parcelas, y sin embargo, ¿no son un operador binario? ¿Deberíamos tomar (2) como un único token, que evalúa a 2?
Los parens no necesitan aparecer en el árbol de expresiones, pero sí afectan su forma. Por ejemplo, el árbol para (1 + 2) +3 es diferente de 1+ (2 + 3):
+
/ /
+ 3
/ /
1 2
versus
+
/ /
1 +
/ /
2 3
Los paréntesis son una "pista" para el analizador sintáctico (por ejemplo, por superjoe30, para "descender recursivamente")
No daré la respuesta, pero una Solución Estándar Malo implica el uso de un interruptor o una declaración de caso (o simplemente buenos anticuados en cascada). Una Solución Ligeramente Mejor implica el uso de una tabla de indicadores de función, y la Solución Probablemente Mejor implica el uso de polimorfismo.
Los últimos veinte años de evolución en los intérpretes pueden verse como opuestos: polimorfismo (por ejemplo, intérpretes metacirculares Smalltalk ingenuos) a indicadores de función (implementaciones ingeniosas de ceceo, código subprocesado, C ++) para cambiar (intérpretes de código de bytes ingenuos) y luego en adelante a JIT, etc., que requieren clases muy grandes o (en idiomas polimórficos únicos) doble envío, lo que reduce el polimorfismo a un tipo de caso y vuelves a la etapa uno. ¿Qué definición de "mejor" está en uso aquí?
Para cosas simples, una solución polimórfica está bien; esta es una que hice anteriormente , pero apilar, codificar / cambiar byte o explotar el compilador del tiempo de ejecución suele ser mejor si estás, por ejemplo, trazando una función con algunos miles de puntos de datos.
O tal vez esta es la verdadera pregunta: ¿cómo se puede representar (2) como BST? Esa es la parte que me está haciendo tropezar.
Recursion
@Justin:
Mira mi nota sobre la representación de los nodos. Si usa ese esquema, entonces
2 + (2)
puede ser representado como
.
/ /
2 ( )
|
2
Como la gente ha mencionado anteriormente, cuando usas árboles de expresión, los parens no son necesarios. El orden de las operaciones se vuelve trivial y obvio cuando estás mirando un árbol de expresiones. Los parens son pistas para el analizador.
Si bien la respuesta aceptada es la solución a la mitad del problema, la otra mitad, en realidad analizar la expresión, sigue sin resolverse. Típicamente, este tipo de problemas se pueden resolver usando un analizador de descenso recursivo . Escribir un analizador de este tipo es a menudo un ejercicio divertido, pero la mayoría de las herramientas modernas para analizar el lenguaje lo abstraeran por usted.
El analizador también es significativamente más difícil si permite números de punto flotante en su cadena. Tuve que crear un DFA para aceptar números de coma flotante en C: era una tarea muy minuciosa y detallada. Recuerde, los puntos flotantes válidos incluyen: 10, 10., 10.123, 9.876e-5, 1.0f, .025, etc. Supongo que se hizo alguna dispensa de esto (a favor de la simplicidad y brevedad) en la entrevista.
Creo que la pregunta es sobre cómo escribir un analizador sintáctico, no el evaluador. O más bien, cómo crear el árbol de expresiones a partir de una cadena.
Las declaraciones de casos que devuelven una clase base no cuentan exactamente.
La estructura básica de una solución "polimórfica" (que es otra forma de decir, no me importa con qué se construya esto, solo quiero extenderla con la reescritura de la menor cantidad de código posible) es deserializar una jerarquía de objetos de una transmitir con un conjunto (dinámico) de tipos conocidos.
El punto crucial de la implementación de la solución polimórfica es tener una forma de crear un objeto de expresión a partir de un patrón de emparejamiento, probablemente recursivo. Es decir, mapear una sintaxis BNF o similar a una fábrica de objetos.
De alguna manera, he tirado la aplicación de la consola c # como una prueba de concepto. Tengo la sensación de que podría ser mucho mejor (esa declaración de cambio en GetNode es un poco torpe (está ahí porque me tocó un espacio en blanco al intentar asignar un nombre de clase a un operador)). Cualquier sugerencia sobre cómo podría mejorarse muy bienvenida.
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;
}
}
}
}
Esto entra en la teoría de análisis / compilación, que es como un agujero de conejo ... El Libro del Dragón es el texto estándar para la construcción del compilador, y lleva esto a extremos. En este caso particular, quiere construir una gramática libre de contexto para la aritmética básica, luego use esa gramática para analizar un árbol de sintaxis abstracta . A continuación, puede iterar sobre el árbol, reduciéndolo de abajo hacia arriba (en este punto aplicará la instrucción de polimorfismo / indicadores de función / cambio para reducir el árbol).
He encontrado que estas notas son increíblemente útiles en la teoría de compilación y análisis.
He escrito un analizador así con algunas técnicas básicas como Infix -> RPN y Shunting Yard y Tree Traversals . Aquí está la implementación que se me ocurrió .
Está escrito en C ++ y se compila tanto en Linux como en Windows.
Cualquier sugerencia / pregunta es bienvenida.
Entonces, intentemos abordar el problema de las tres maneras. ¿Cómo se pasa de una expresión aritmética (por ejemplo, en una cadena) como "2 + (2)" a un árbol de expresiones usando cascadas-if, una tabla de punteros a las funciones y / o polimorfismo?
Esto es interesante, pero no creo que esto pertenezca al ámbito de la programación orientada a objetos ... Creo que tiene más que ver con las técnicas de análisis sintáctico .
Hm ... No creo que puedas escribir un analizador de arriba hacia abajo sin retroceder, así que tiene que ser una especie de analizador de reducción de cambios. LR (1) o incluso LALR por supuesto funcionarán bien con la siguiente definición de lenguaje (ad-hoc):
Inicio -> E1
E1 -> E1 + E1 | E1-E1
E1 -> E2 * E2 | E2 / E2 | E2
E2 -> número | (E1)
Separarlo en E1 y E2 es necesario para mantener la precedencia de * y / sobre + y -.
Pero así es como lo haría si tuviera que escribir el analizador a mano:
- Dos pilas, una almacenando nodos del árbol como operandos y una almacenando operadores
- Lea la entrada de izquierda a derecha, cree nodos hoja de los números y empújelos a la pila de operandos.
- Si tiene> = 2 operandos en la pila, pop 2, combínelos con el operador más alto en la pila del operador y vuelva a colocar esta estructura en el árbol de operandos, a menos que
- El siguiente operador tiene una precedencia mayor que la que se encuentra actualmente en la parte superior de la pila.
Esto nos deja el problema de manejar los corchetes. Una solución elegante (pensé) es almacenar la precedencia de cada operador como un número en una variable. Entonces, inicialmente,
- int más, menos = 1;
- int mul, div = 2;
Ahora, cada vez que vea un paréntesis izquierdo, incremente todas estas variables en 2, y cada vez que vea un paréntesis derecho, disminuya todas las variables en 2.
Esto asegurará que el + en 3 * (4 + 5) tenga una precedencia mayor que el *, y 3 * 4 no se insertarán en la pila. En su lugar, esperará 5, presione 4 + 5, luego presione 3 * (4 + 5).
Ok, aquí está mi implementación ingenua. Lo siento, no sentí la necesidad de usar objetos para eso, pero es fácil de convertir. Me siento un poco como el malvado Willy (de la historia 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()
Re: Justin
Creo que el árbol se vería así:
+
/ /
2 ( )
|
2
Básicamente, tendrías un nodo "eval", que simplemente evalúa el árbol debajo de él. Eso luego sería optimizado para ser solo:
+
/ /
2 2
En este caso, los paréntesis no son necesarios y no agregan nada. No agregan nada lógicamente, por lo que simplemente desaparecerían.
Representando los Nodos
Si queremos incluir paréntesis, necesitamos 5 tipos de nodos:
los nodos binarios: Add Minus Mul Div
estos tienen dos hijos, un lado izquierdo y otro derecho+ / / node nodeun nodo para contener un valor: Val
no hay nodos secundarios, solo un valor numéricoun nodo para realizar un seguimiento de los parens: Paren
un único nodo hijo para la subexpresión( ) | node
Para una solución polimórfica, necesitamos tener este tipo de relación de clase:
- Nodo
- BinaryNode: hereda del nodo
- Además: hereda del nodo binario
- Menos: heredar del nodo binario
- Mul: heredar del nodo binario
- Div: heredar del nodo binario
- Valor: heredar del nodo
- Paren: heredar del nodo
Hay una función virtual para todos los nodos llamada eval (). Si llama a esa función, devolverá el valor de esa subexpresión.
String Tokenizer + LL (1) El analizador le dará un árbol de expresiones ... el modo de polimorfismo podría implicar una clase aritmética abstracta con una función "evaluar (a, b)", que se anula para cada uno de los operadores implicados (además, Resta, etc.) para devolver el valor apropiado, y el árbol contiene enteros y operadores aritméticos, que se pueden evaluar mediante una publicación (?): Ordena el recorrido del árbol.
debe usar un lenguaje funcional imo. Los árboles son más difíciles de representar y manipular en los lenguajes OO.
Árbol polimórfico que camina , versión de 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)
Las pruebas solo están construyendo los árboles binarios mediante el uso de constructores.
estructura del programa:
clase base abstracta: nodo
- todos los nodos heredan de esta clase
clase base abstracta: BinaryNode
- todos los operadores binarios heredan de esta clase
- El método de proceso hace el trabajo de evaluar la expresión y devolver el resultado
clases de operadores binarios: Plus, Minus, Mul, Div
- dos nodos secundarios, uno para las subexpresiones del lado izquierdo y del lado derecho
clase numérica: Num
- tiene un valor numérico de nodo de hoja, por ejemplo, 17 o 42