Como avaliar uma expressão em notação de prefixo
-
13-09-2020 - |
Pergunta
Eu estou tentando avaliar uma lista que representa uma expressão em notação de prefixo.Aqui está um exemplo de uma lista:
[+, [sin, 3], [- 10 5]]
Qual é a melhor forma de avaliar o valor da lista
Solução
Será mais simples se você usou o postfix, em vez de prefixo.Ver Reverse Polish Notation (RPN).Dada uma expressão em RPN, é fácil avaliar que utilizando apenas uma pilha.
Mas já que você pediu uma maneira de avaliar a prefixo expressões sem recursão e usando pilhas (para possivelmente uma forma mais simples, consulte EDITAR:abaixo), aqui está uma maneira:
Podemos fazer isso usando duas pilhas.
Uma pilha (chamá-lo de Avaliação), que detém os operadores (como +, o pecado, etc) e operandos (como 3,4 etc) e a outra pilha (chamá-lo de Contagem), que detém uma cadeia de identificação do número de operandos esquerda para ser visto + o número de operandos de um operador de espera.
Sempre que você ver um operador, você aperta o operador para a Avaliação de pilha e empurre a tupla correspondente para a Contagem de pilha.
Quando você ver um operando (como 3,5 etc), você verificar o topo tupla da Contagem de pilha e decrementa o número de operandos esquerda para ser vistos na tupla.
Se o número de operandos esquerda para ser visto se torna zero, você insere a tupla a partir da Contagem de pilha.Em seguida, a partir da Avaliação de pilha pop fora o número de operandos necessários (você sabe disso porque um dos outros valor da tupla), pop fora da operadora e fazer a operação para obter um novo valor (ou operando).
Agora empurre o novo operando de volta na Avaliação de pilha.Este novo operando empurrar faz com que você tomar um outro olhar para o topo da Contagem de fichas e fazer a mesma coisa que nós fizemos (diminuir os operandos visto, compare com zero, etc.).
Se o operando de contagem não se tornar zero, que você continue com o próximo token da entrada.
Por exemplo, dizer que você tinha para avaliar + 3 + 4 / 20 4
As pilhas vai olhar como (da esquerda é o topo da pilha)
Count Evaluation Input
+ 3 + 4 / 20 4
(2,2) + 3 + 4 / 20 4
(2,1) 3 + + 4 / 20 4
(2,2) (2,1) + 3 + 4 / 20 4
(2,1) (2,1) 4 + 3 + / 20 4
(2,2) (2,1) (2,1) / 4 + 3 + 20 4
(2,1) (2,1) (2,1) 20 / 4 + 3 + 4
(2,0) (2,1) (2,1) 4 8 / 4 + 3 +
Since it has become zero, you pop off two operands, the operator /
and evaluate and push back 5. You pop off (2,0) from the Count stack.
(2,1) (2,1) 5 4 + 3 +
Pushing back you decrement the current Count stack top.
(2,0) (2,1) 5 4 + 3 +
Since it has become zero, you pop off 5,4 and + and evaluate and push back 9.
Also pop off (2,0) from the count stack.
(2,0) 9 3 +
12
EDITAR:
Um amigo sugeriu uma maneira de fazer isso sem várias pilhas:
Iniciar a partir do fim, vá para o primeiro operador.Os tokens para a direita do que vai ser operandos.Avaliar e refazer.Parece muito mais simples do que fazê-lo com duas pilhas.Podemos usar uma lista duplamente vinculada para representar a entrada que podemos mudar durante o processamento.Quando você avaliar, eliminar os nós e, em seguida, insira o resultado.Ou talvez você poderia usar apenas uma pilha.
Outras dicas
BEIJO, avaliar inversa, como um postfix expressão.
A forma como eu vejo você tem duas opções.Quer ir para a esquerda, para a direita ou da direita para a esquerda (como paulo sugerido acima).Ambos os métodos são demonstrado no código abaixo.
public static class Evaluator
{
public static double EvaluatePrefix(string expr)
{
if (expr == null) throw new ArgumentNullException("expr");
var symbols = expr.Split(',');
var stack = new Stack<Symbol>();
foreach (var symbol in symbols)
{
double operand;
if (!double.TryParse(symbol, out operand)) //encountered an operator
{
stack.Push(new Operator(symbol));
continue;
}
//encountered an operand
if (stack.Count == 0) throw new ArgumentException("Invalid expression");
double right = operand;
var leftOperand = stack.Peek() as Operand;
while (leftOperand != null)
{
stack.Pop(); //pop left operand that we just peeked
if (stack.Count == 0) throw new ArgumentException("Invalid expression");
double result = Calculate(leftOperand.Value, right, ((Operator)stack.Pop()).OperatorChar);
right = result;
leftOperand = (stack.Count == 0) ? null : stack.Peek() as Operand;
}
stack.Push(new Operand(right));
}
if (stack.Count != 1) throw new ArgumentException("Invalid expression");
var operandSymbol = stack.Pop() as Operand;
if (operandSymbol == null) throw new ArgumentException("Invalid expression");
return operandSymbol.Value;
}
public static double EvaluatePrefixAlternative(string expr)
{
if (expr == null) throw new ArgumentNullException("expr");
double d;
var stack = new Stack<Symbol>(
expr.Split(',').Select(s => double.TryParse(s, out d) ? (Symbol) new Operand(d) : new Operator(s)));
var operands = new Stack<double>();
while (stack.Count > 0)
{
var symbol = stack.Pop();
var operand = symbol as Operand;
if (operand != null)
{
operands.Push(operand.Value);
}
else
{
if (operands.Count < 2) throw new ArgumentNullException("expr");
operands.Push(Calculate(operands.Pop(), operands.Pop(), ((Operator) symbol).OperatorChar));
}
}
if (operands.Count != 1) throw new ArgumentNullException("expr");
return operands.Pop();
}
private static double Calculate(double left, double right, char op)
{
switch (op)
{
case '*':
return (left * right);
case '+':
return (left + right);
case '-':
return (left - right);
case '/':
return (left / right); //May divide by zero !
default:
throw new ArgumentException(string.Format("Unrecognized operand {0}", op), "op");
}
}
abstract class Symbol
{
}
private class Operand : Symbol
{
public double Value { get; private set; }
public Operand(double value)
{
Value = value;
}
}
private class Operator : Symbol
{
public char OperatorChar { get; private set; }
public Operator(string symbol)
{
if (symbol.Trim().Length != 1) throw new ArgumentException("Invalid expression");
OperatorChar = symbol[0];
}
}
}
Alguns testes:
[TestMethod]
public void TestPrefixEvaluation()
{
Assert.AreEqual(5, Evaluator.EvaluatePrefix("-,*,/,15,-,7,+,1,1,3,+,2,+,1,1"));
Assert.AreEqual(4, Evaluator.EvaluatePrefix("/,-,*,2,5,*,1,2,-,11,9"));
Assert.AreEqual(5, Evaluator.EvaluatePrefixAlternative("-,*,/,15,-,7,+,1,1,3,+,2,+,1,1"));
Assert.AreEqual(4, Evaluator.EvaluatePrefixAlternative("/,-,*,2,5,*,1,2,-,11,9"));
}