La Evaluación de la expresión y el Árbol de la Poca utilización de polimorfismo?(ala Steve Yegge)
https://stackoverflow.com/questions/12516
-
08-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
Esta mañana, estaba leyendo Steve Yegge del:Cuando Polimorfismo Falla, cuando me encontré con una pregunta que un compañero de trabajo de su solía preguntar a los empleados potenciales que cuando ellos vinieron para su entrevista en Amazon.
Como un ejemplo de polimorfismo en acción, veamos el clásico "eval" pregunta de la entrevista, que (como hasta donde yo sé) fue llevado a Amazon por Ron Braunstein.La pregunta es muy rica, como se las arregla para explorar una amplia variedad de importantes habilidades:La programación orientada a objetos diseño, la recursividad, binario los árboles, el polimorfismo y el tiempo de ejecución escribir, general de habilidades de codificación, y (si quieres hacer que sea más difícil) el análisis de la teoría.
En algún punto, el candidato esperemos que se da cuenta de que puede representar un expresión aritmética binaria árbol, suponiendo que sólo está utilizando operadores binarios tales como "+", "-", "*", "/".Los nodos hoja son todos los números, y los nodos internos son todos los operadores.La evaluación de la los medios de expresión pie del árbol.Si el candidato no se dan cuenta de esto, usted puede llevarlos suavemente a ella, o si es necesario, sólo les digo.
Incluso si usted les dice, es todavía un problema interesante.
La primera mitad de la pregunta, que algunas personas (cuyos nombres proteger a mi lecho de muerte, pero su iniciales son Willie Lewis) es un Requisito De Trabajo Si Desea Llamar Usted Mismo Un Desarrollador Y El Trabajo En Amazon, es realmente un poco difícil.El la pregunta es:¿cómo ir de un expresión aritmética (por ejemplo,en un cadena) como "2 + (2)" a un árbol de expresión.Es posible que tenga una ADJ el desafío de esta pregunta en algún punto.
La segunda mitad es:digamos que este es 2 del proyecto, y su pareja, que vamos a llamar "Willie", es responsable de la transformación de la expresión de cadena a un árbol.Usted obtener la parte fácil:usted necesita decidir lo que clases de Willie es la construcción de la árbol con.Usted puede hacerlo en cualquier el lenguaje, pero asegúrese de que usted elija uno, o Willie le entregará la asamblea lenguaje.Si él se siente intratable, se será para un procesador que no es no fabricados en la producción.
Usted se sorprenderá de cómo muchos de los candidatos boff este.
No voy a dar la respuesta, pero una Estándar Mala Solución implica el uso de un interruptor o de un caso de declaración (o simplemente a la vieja usanza en cascada-ifs).Un Ligeramente Mejor Solución consiste en el uso de una tabla de punteros a funciones, y la que Probablemente sea la Mejor Solución implica el uso de polimorfismo.Yo animo a trabajar a través de él en algún momento.La materia de la diversión!
Por lo tanto, vamos a tratar de abordar el problema de las tres formas.¿Cómo ir de una expresión aritmética (por ejemplo,en una cadena), tales como "2 + (2)" a un árbol de expresión utilizando en cascada-si, una tabla de punteros a funciones, y/o polimorfismo?
Siéntase libre de hacer frente a uno, dos o los tres.
[actualización:título modificado para adaptarse mejor a lo que la mayoría de las respuestas han sido.]
Solución
Polimórficos Árbol De Caminar, La 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 son sólo la construcción de los árboles binarios mediante constructores.
estructura del programa:
clase base abstracta:Nodo
- todos los Nodos heredar de esta clase
clase base abstracta:BinaryNode
- todos los operadores binarios heredar de esta clase
- método de proceso hace el trabajo de evaluar la expresión y devolver el resultado
operador binario clases:Más,Menos,Mul,Div
- dos nodos secundarios, uno para el lado izquierdo y el lado derecho subexpresiones
número de clase:Num
- tiene un nodo de hoja valor numérico, por ejemplo,17 o 42
Otros consejos
El problema, creo, es que tenemos que analizar perentheses, y sin embargo no son un operador binario?Debemos tomar (2) como un único token, que evalúa a 2?
Los paréntesis no necesita mostrar en el árbol de expresión, pero sí que afecta a su forma.E. g., el árbol de (1+2)+3 es diferente de 1+(2+3):
+
/ \
+ 3
/ \
1 2
frente a
+
/ \
1 +
/ \
2 3
Los paréntesis son una "pista" para el analizador (por ejemplo, por superjoe30, para que "de forma recursiva descender")
Esto nos lleva a analizar/teoría de compiladores, que es una especie de un agujero de conejo... El Dragón Libro es el texto estándar para el compilador de la construcción, y se lleva esto al extremo.En este caso particular, se desea construir una gramática independiente del contexto para la aritmética básica, a continuación, utilizar ese gramática para analizar una árbol de sintaxis abstracta.Se puede iterar sobre el árbol, la reducción es de abajo hacia arriba (es en este punto que había aplicar el polimorfismo/punteros de función/switch para reducir el árbol).
He encontrado estas notas para ser increíblemente útil en el compilador y el análisis de la teoría.
En representación de los Nodos
Si queremos incluir entre paréntesis, tenemos 5 tipos de nodos:
el binario de nodos:Agregar Menos Mul Div
estos tienen dos hijos, una a la izquierda y a la derecha+ / \ node nodeun nodo para mantener un valor:Val
no hay nodos hijos, sólo un valor numéricoun nodo de seguir la pista de los paréntesis:Paren
un único nodo secundario para la subexpresión( ) | node
Para un polimórficos solución, necesitamos tener este tipo de clase de relación:
- Nodo
- BinaryNode :heredar de Nodo
- Plus :heredar de Nodo Binario
- Menos :heredar de Nodo Binario
- Mul :heredar de Nodo Binario
- Div :heredar de Nodo Binario
- Valor :heredar de Nodo
- Paréntesis :heredar de nodo
Hay una función virtual para todos los nodos, llamados eval().Si usted llama a la función devolverá el valor de la subexpresión.
String Tokenizer + LL(1) Analizador le dará un árbol de expresión...el polimorfismo de la forma en que podría implicar un resumen clase de Aritmética con un "evaluar(a,b)" la función, que es reemplazado por cada uno de los operadores (Suma, Resta, etc.) para devolver el valor apropiado, y el árbol que contiene los números Enteros y de los operadores Aritméticos, los cuales pueden ser evaluadas por un post(?)-orden de recorrido del árbol.
No voy a dar la respuesta, pero una Estándar Mala Solución implica el uso de un interruptor o de un caso de declaración (o simplemente a la vieja usanza en cascada-ifs).Un Ligeramente Mejor Solución consiste en el uso de una tabla de punteros a funciones, y la que Probablemente sea la Mejor Solución implica el uso de polimorfismo.
Los últimos veinte años de evolución en los intérpretes puede ser visto como va la otra manera - polimorfismo (por ejemplo, ingenuo de Smalltalk metacircular intérpretes) a los punteros de función (ingenuo de las implementaciones de lisp, con código C++) para cambiar (ingenuo de código de bytes de intérpretes) y, a continuación, en adelante, de Jit y así sucesivamente - que, o bien requieren muy grandes clases, o (en forma individual polimórficos idiomas) el doble de la expedición, lo que reduce el polimorfismo a un tipo de caso, y estás de vuelta en la etapa uno.Qué definición de "mejor" está en uso aquí?
Para cosas simples un polimórficos solución es ACEPTAR - aquí está uno que hice anteriormente, pero ya sea de la pila y el código de bytes/switch o aprovechando el tiempo de ejecución del compilador suele ser mejor si usted está, digamos, trazando una función con un par de miles de puntos de datos.
Hm...No creo que usted puede escribir un analizador para esto, sin vuelta atrás, así que tiene que ser algún tipo de cambio-reducir el analizador.LR(1) o incluso LALR por supuesto va a funcionar bien con el siguiente (ad-hoc) el lenguaje de definición de:
Inicio -> E1
E1 -> E1+E1 | E1-E1
E1> E2*E2 | E2/E2 | E2
E2 -> número de | (E1)
Apartar E1 y E2 es necesario para mantener el orden de precedencia de * y por encima de + y -.
Pero esto es lo que yo haría si tuviera que escribir el analizador de la mano:
- Dos montones, uno almacenar los nodos del árbol como operandos y un almacenamiento de los operadores
- Leer la entrada de izquierda a derecha, hacer que los nodos hoja de los números y empuje en la pila de operandos.
- Si usted tiene >= 2 operandos en la pila, pop 2, se combinan con el primer operador en el operador de la pila y el empuje de esta estructura para el operando árbol, a menos que
- El siguiente operador tiene mayor prioridad que el que está en la parte superior de la pila.
Esto nos deja con el problema de la manipulación de los soportes.Una elegante (pensé) la solución es almacenar la prioridad de cada operador como un número en una variable.Así pues, inicialmente,
- int plus, minus = 1;
- int mul, div = 2;
Ahora cada vez que vea un corchete izquierdo incremento todas estas variables por 2, y cada vez que vea un corchete de cierre, decremento todas las variables por 2.
Esto asegurará que el + 3*(4+5) tiene mayor prioridad que el * y 3*4 no se inserta en la pila.En lugar de ello se espera para el 5 de empuje 4+5, a continuación, presione 3*(4+5).
Re:Justin
Creo que el árbol sería algo como esto:
+
/ \
2 ( )
|
2
Básicamente, usted tendría una "eval" nodo, que sólo evalúa el árbol debajo de él.Que podría ser optimizado a ser:
+
/ \
2 2
En este caso los paréntesis no son necesarios y no aportan nada.Ellos no aportan nada, lógicamente, por lo que acababa de desaparecer.
Creo que la pregunta es acerca de cómo escribir un analizador, no el evaluador.O más bien, cómo crear el árbol de expresión a partir de una cadena.
El caso de las declaraciones que devuelven una clase base no exactamente contar.
La estructura básica de una "polimórfica" solución (que es otra manera de decir, no me importa lo que se construye esta con el, solo quiero extender con la reescritura de la menor cantidad de código posible) es deserializar un objeto de la jerarquía a partir de una secuencia con un (dinámico) conjunto de los tipos conocidos.
El quid de la aplicación de la polimórficos solución es tener una manera de crear un objeto de expresión de un patrón comparador, probablemente de forma recursiva.I. e., mapa de un BNF o sintaxis similar a un objeto de la fábrica.
O tal vez esta es la verdadera pregunta:¿cómo se puede representar (2) como un BST?Esa es la parte que se me disparo hasta.
La recursividad.
@Justin:
Mira mi nota en la representación de los nodos.Si usar ese esquema, a continuación,
2 + (2)
puede ser representado como
.
/ \
2 ( )
|
2
debe utilizar un lenguaje funcional de la omi.Los árboles son más difíciles de representar y manipular en OO de idiomas.
Como la gente ha ido mencionando anteriormente, cuando el uso de árboles de expresión en paréntesis no son necesarios.El orden de las operaciones vuelve trivial y obvio cuando usted está buscando en un árbol de expresión.Los paréntesis son sugerencias para el analizador.
Mientras que el aceptado la respuesta es la solución a la mitad del problema, la otra mitad - en realidad, el análisis de la expresión - está todavía sin resolver.Normalmente, estos tipos de problemas pueden ser resueltos utilizando un recursiva descenso analizador.Escribir un analizador es a menudo un ejercicio divertido, pero la mayoría de los herramientas modernas para el análisis de idioma se resumen lo que fuera para usted.
El analizador es también significativamente más difícil si usted permite que los números de punto flotante en una cadena.Tuve que crear un DFA para aceptar números de punto flotante en C -- fue una muy minuciosa y detallada de las tareas.Recuerde, flotante válido puntos son:10, 10., 10.123, 9.876 e-5, 1.0 f, .025, etc.Supongo que algunos la dispensa de este (en favor de simplicty y brevedad) se hizo en la entrevista.
He escrito un analizador con algunas técnicas básicas como
Infix -> RPN y
Patio De Maniobras y
Árbol De Los Recorridos De.
Aquí está la aplicación que he venido para arriba con.
Está escrito en C++ y se compila en Linux y Windows.
Cualquier sugerencias/preguntas son bienvenidas.
Por lo tanto, vamos a tratar de abordar el problema de las tres formas.¿Cómo ir de una expresión aritmética (por ejemplo,en una cadena), tales como "2 + (2)" a un árbol de expresión utilizando en cascada-si, una tabla de punteros a funciones, y/o polimorfismo?
Esto es interesante,pero no creo que esto pertenece al reino de la programación orientada a objetos...creo que tiene más que ver con técnicas de análisis.
He tipo de mandril esta consola en c# app juntos como un poco de una prueba de concepto.Tienen la sensación de que podría ser mucho mejor (que el interruptor de la declaración en GetNode es una especie de torpe (que no coz me golpeó en blanco tratando de asignar un nombre de clase para un operador)).Cualquier sugerencias sobre cómo se podría mejorar 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;
}
}
}
}
Ok, aquí está mi ingenuo aplicación.Lo siento, no me siento para el uso de los objetos para que uno, pero es fácil de convertir.Me siento un poco como el mal Willy (en 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()
