A Avaliação da expressão e o percurso da Árvore usando polimorfismo?(ala Steve Yegge)
https://stackoverflow.com/questions/12516
-
08-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Esta manhã, eu estava lendo Steve Yegge a:Quando Polimorfismo Falha, quando me deparei com uma pergunta que um co-trabalhador do seu usado para pedir empregados em potencial quando eles vieram para a sua entrevista no site da Amazon.
Como um exemplo de polimorfismo em ação, vamos olhar para o clássico "eval" pergunta da entrevista, que (como até onde eu sei) foi trazido para a Amazônia por Ron Braunstein.A questão é muito rica, como consegue sonda de uma grande variedade de importante competências:Design OOP, recursividade, binário árvores, polimorfismo e tempo de execução digitação, codificação geral de competências, e (se você deseja torná-lo rígido extra) a análise da teoria.
Em algum momento, o candidato que espero percebe que pode representar uma expressão aritmética como um binário árvore, supondo que você está apenas usando os operadores binários, tais como "+", "-", "*", "/".Os nós folha são todos números e os nós internos são todos os operadores.Avaliar o a expressão significa percorrer a árvore.Se o candidato que não percebe isso, você pode gentilmente levá-los a ele, ou se necessário, apenas diga-o.
Mesmo se você disser a elas, ainda é um problema interessante.
A primeira metade da questão, o que algumas pessoas (cujos nomes eu vou proteger meu último suspiro, mas a sua iniciais são Willie Lewis) sinto é um Emprego Exigência, Se Você Quiser Chamá - Se Um Desenvolvedor E Trabalho Em Amazon, na verdade, é meio difícil.O a pergunta é:como você ir de um expressão aritmética (e.g.em um seqüência de caracteres), tais como "2 + (2)" para uma árvore de expressão.Podemos ter uma ADJ o desafio esta pergunta em algum ponto.
A segunda metade é:vamos dizer que esta é 2-pessoa projeto, e o seu parceiro, que nós vamos chamar de "Willie", é responsável por transformar a expressão de seqüência de caracteres em uma árvore.Você começa a parte mais fácil:você precisa decidir o que classes de Willie é construir o árvore com.Você pode fazê-lo em qualquer a linguagem, mas certifique-se de que você escolha um, ou Willie vai entregar-lhe assembleia idioma.Se ele está sentindo ornery, ele será para um processador que não é mais fabricado na produção.
Você ficaria surpreso como muitos candidatos boff este.
Eu não vou dar a resposta, mas uma Padrão Má Solução envolve o uso de um interruptor ou caso politica (ou apenas o bom e velho em cascata-ifs).Um Um pouco Melhor Solução envolve usando uma tabela de ponteiros de função, e, Provavelmente, a Melhor Solução envolve o uso de polimorfismo.Eu encorajamos você a trabalhar com ele em algum momento.Diversão!
Então, vamos tentar abordar o problema de todas as três formas.Como você vai fazer a partir de uma expressão aritmética (e.g.em uma seqüência de caracteres), tais como "2 + (2)" para uma árvore de expressão em cascata usando-se uma tabela de ponteiros de função, e/ou polimorfismo?
Sinta-se livre para fazer face a um, dois ou todos os três.
[update:título modificado para melhor corresponder ao que a maioria das respostas foram.]
Solução
Polimórficos Árvore De Pé, Versão do 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)
Os testes são apenas de construção até as árvores binárias utilizando construtores.
estrutura do programa:
classe base abstrata:Nó
- todos Nós herdam desta classe
classe base abstrata:BinaryNode
- todos os operadores binários herdam desta classe
- método do processo faz o trabalho de evaluting a expressão e devolver o resultado
operador binário classes:Sinal De Adição,Subtração,Mul,Div
- filho de dois nós, um de cada lado esquerdo e lado direito subexpressões
número da classe:Num
- contém uma folha de nó de valor numérico, por exemplo,17 ou 42
Outras dicas
O problema, penso eu, é que precisamos analisar perentheses, e ainda eles não são um operador binário?Devemos tomar (2) como um único token, que avalia a 2?
O parens não precisa aparecer na árvore de expressão, mas eles afetam a sua forma.E. g., a árvore (1+2)+3 é diferente de 1+(2+3):
+
/ \
+ 3
/ \
1 2
versus
+
/ \
1 +
/ \
2 3
Os parênteses são uma "dica" para o analisador (por exemplo, por superjoe30, para "recursivamente descer")
Isso entra na análise/compilador de a teoria, que é uma espécie de um buraco de coelho... O Dragão Livro é o texto padrão para o compilador de construção, e leva isso ao extremo.Neste caso específico, pretende construir um gramática livre de contexto para aritmética básica e, em seguida, usar o que a gramática para analisar um abstract syntax tree.Em seguida, você pode iterar sobre a árvore, reduzindo-o de baixo para cima (é neste ponto que você gostaria de aplicar o polimorfismo/ponteiros de função/instrução switch para reduzir a árvore).
Eu encontrei estas notas para ser extremamente útil no compilador de análise e teoria.
Representando os Nós
Se queremos incluir parênteses, temos 5 tipos de nós:
o binário nós:Adicionar Menos Mul Div
estas têm dois filhos, um dos lados direito e esquerdo+ / \ node nodeum nó para segurar um valor:Val
não nós filhos, apenas um valor numéricoum nó para acompanhar o parens:Paren
um único nó filho para a subexpressão( ) | node
Para um polimórfico solução, precisamos ter esse tipo de relação de classe:
- Nó
- BinaryNode :herdar do Nó
- Mais :herdar do Nó Binário
- Menos :herdar do Nó Binário
- Mul :herdar do Nó Binário
- Div :herdar do Nó Binário
- Valor :herdar do Nó
- Paren :herdar do nó
Há uma função virtual para todos nós chamada eval().Se você chamar essa função, ele irá retornar o valor de que subexpressão.
Cadeia de Lexemas + LL(1) Parser irá dar-lhe uma árvore de expressão...o polimorfismo forma pode envolver um resumo Aritmética classe com um "avaliar(a,b) função", o qual é substituído para cada um dos operadores envolvidos (Adição, Subtração, etc) para retornar o valor apropriado, e a árvore que contém números Inteiros e operações Aritméticas, o que pode ser avaliada por um post(?)-ordem transversal da árvore.
Eu não vou dar a resposta, mas uma Padrão Má Solução envolve o uso de um interruptor ou caso politica (ou apenas o bom e velho em cascata-ifs).Um Um pouco Melhor Solução envolve usando uma tabela de ponteiros de função, e, Provavelmente, a Melhor Solução envolve o uso de polimorfismo.
Os últimos vinte anos de evolução em intérpretes pode ser visto como ir a outra maneira - polimorfismo (por exemplo, ingênua Smalltalk metacircular intérpretes) para ponteiros de função (naive implementações de lisp, código de thread, C++) para alternar (ingênua de código de byte intérpretes) e, em seguida, partir para JITs e assim por diante - que exigem muito grande de classes, ou (no isoladamente polimórficos línguas) duplo-dispatch, o que reduz o polimorfismo para um tipo de caso, e você está de volta ao palco.O que a definição de "melhor" é usado aqui?
Para coisas simples um polimórfico solução é OK - aqui está o que eu fiz anteriormente, mas de qualquer pilha e bytecode/switch ou exploração, o tempo de execução do compilador normalmente é melhor se você está, digamos, a plotagem de uma função com alguns milhares de pontos de dados.
Hm...Eu não acho que você pode escrever um top-down analisador para esta, sem retrocesso, por isso tem que ser algum tipo de um shift-reduce analisador.LR(1) ou até mesmo LALR naturalmente irá funcionar bem com o seguinte (ad-hoc) linguagem de definição:
Iniciar -> E1
E1 -> E1+E1 | E1-E1
E1 -> E2*E2 | E2/E2 | E2
E2 -> número | (E1)
Separando-as em E1 e E2 é necessário para manter a precedência de * e / sobre + e -.
Mas isso é como eu faria isso se eu tivesse que escrever o analisador de mão:
- Duas pilhas, uma armazenar os nós da árvore como operandos e um armazenamento de operadores
- Ler a entrada da esquerda para a direita, fazer de nós folhas dos números e empurrá-los para a pilha operando.
- Se você tem >= 2 operandos na pilha pop 2, combiná-los com o primeiro operador a operador de pilha e empurre esta estrutura de volta para o operando árvore, a menos que
- O próximo operador tem maior precedência que não o que estiver no topo da pilha.
Isso nos deixa com o problema de tratamento entre parênteses.Um elegante (eu pensei) é a solução para armazenar a precedência de cada operador como um número em uma variável.Assim, inicialmente,
- int plus, minus = 1;
- int mul, div = 2;
Agora toda vez que você ver um um colchete esquerdo incremento de todas estas variáveis, por 2, e toda vez que você ver um colchete direito, diminuir todas as variáveis por 2.
Isto irá assegurar que a + 3*(4+5) tem precedência maior do que o * e 3*4 não vai ser empurrado para a pilha.Em vez disso, ele deverá aguardar 5, empurre 4+5, em seguida, pressione 3*(4+5).
Re:Justin
Eu acho que a árvore seria algo parecido com isto:
+
/ \
2 ( )
|
2
Basicamente, você teria uma "eval" nó, que apenas avalia a árvore abaixo.Que seria, então, ser otimizado fora, assim sendo:
+
/ \
2 2
Neste caso, o parens não são necessários e não acrescentam nada.Eles não acrescentam nada logicamente, de modo que eles tinham acabado de ir embora.
Eu acho que a questão é sobre como escrever um parser, não o avaliador.Ou, ao invés, como criar a árvore de expressão de uma seqüência de caracteres.
Caso declarações que retornam uma classe base não exatamente contagem.
A estrutura básica de um "polimórfico" solução (que é outra maneira de dizer, eu não me importo com o que você construir isso, eu só quero estendê-lo com a regravação de o mínimo de código possível) é anular a serialização de uma hierarquia de objetos a partir de uma sequência com um (dinâmico) conjunto de tipos conhecidos.
O ponto crucial para a implementação de polimórfico solução é ter uma forma de criar uma expressão do objeto a partir de um vericador de modelos, provavelmente recursiva.I. e., mapa de uma BNF ou sintaxe semelhante a uma fábrica de objeto.
Ou talvez essa é a verdadeira questão:como você pode representar (2) como um BST?Essa é a parte que é tropeçar em mim até.
A recursividade.
@Justin:
Olhar minha nota em que representa a nós.Se você usar esse esquema, em seguida,
2 + (2)
pode ser representado como
.
/ \
2 ( )
|
2
deve utilizar uma linguagem funcional imo.Árvores são mais difíceis de representar e manipular em linguagens OO.
Como as pessoas têm sido mencionar anteriormente, quando você usa árvores de expressão parens não são necessárias.A ordem das operações torna-se trivial e óbvio quando você está olhando para uma árvore de expressão.O parens são dicas para o analisador.
Enquanto o aceite resposta é a solução para metade do problema, a outra metade - na verdade, a análise da expressão - ainda está sem solução.Normalmente, esses tipos de problemas podem ser resolvidos usando uma recursiva descida analisador.A escrita como um analisador é muitas vezes um exercício divertido, mas a maioria ferramentas modernas de análise idioma vai abstrato que longe para você.
O analisador também é significativamente mais difícil se você permitir que números de ponto flutuante em sua cadeia.Eu tinha que criar um DFA para aceitar números de ponto flutuante em C -- era muito minucioso e detalhado, tarefa.Lembre-se, válido pontos flutuantes incluem:10, 10., 10.123, 9.876 e-5, 1.0 f, .025, etc.Eu suponho que alguns dispensação de este (a favor de simplicty e brevidade) foi feita na entrevista.
Eu escrevi como um analisador com algumas técnicas básicas como
O Infix -> RPN e
Manobras De Quintal e
Árvore Transversais.
Aqui é a implementação que eu já veio até com.
Ele é escrito em C++ e compilado tanto no Linux quanto no Windows.
Todas as sugestões/perguntas são bem-vindas.
Então, vamos tentar abordar o problema de todas as três formas.Como você vai fazer a partir de uma expressão aritmética (e.g.em uma seqüência de caracteres), tais como "2 + (2)" para uma árvore de expressão em cascata usando-se uma tabela de ponteiros de função, e/ou polimorfismo?
Isso é interessante,mas eu não acho que isso pertence ao domínio de programação orientada a objeto...eu acho que tem mais a ver com técnicas de análise.
Eu tenho uma espécie de atirado este c# aplicativo de console em conjunto, como um pouco de uma prova de conceito.Ter a sensação de que poderia ser muito melhor (que a instrução switch em GetNode é uma espécie de estranha (é lá pq eu bati uma em branco tentando mapear um nome de classe para um operador)).Todas as sugestões sobre como ela poderia ser melhorada muito bem-vindo.
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, aqui está a minha ingênua implementação.Desculpe, eu não sinto usar objetos para que um, mas é fácil converter-se.Me sinto um pouco mal Willy (a partir de Steve história).
#!/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()
