Я пытаюсь оценить список, представляющий выражение в префиксной записи. Вот пример такого списка:
[+, [sin, 3], [- 10 5]]
Как лучше всего оценить значение списка
Я пытаюсь оценить список, представляющий выражение в префиксной записи. Вот пример такого списка:
[+, [sin, 3], [- 10 5]]
Как лучше всего оценить значение списка
Было бы проще, если бы вы использовали постфикс вместо префикса. См. обратную польскую нотацию (RPN). Имея выражение в RPN, его легко вычислить, используя только один стек.
Но поскольку вы попросили способ оценить выражения prefix без рекурсии и с использованием стеков (возможно, более простой способ, см. РЕДАКТИРОВАТЬ: ниже), вот один из способов:
Мы можем сделать это, используя два стека.
Один стек (назовем его Evaluation) содержит операторы (например, +, sin и т. д.) и операнды (например, 3,4 и т. д.), а другой стек (назовем его Count) содержит кортеж из числа оставшихся операндов + число операндов, ожидаемых оператором.
Каждый раз, когда вы видите оператор, вы помещаете его в стек Evaluation, а соответствующий кортеж — в стек Count.
Каждый раз, когда вы видите операнд (например, 3,5 и т. д.), вы проверяете верхний кортеж стека Count и уменьшаете количество операндов, оставшихся для просмотра в этом кортеже.
Если количество оставшихся операндов становится равным нулю, вы извлекаете кортеж из стека Count. Затем из стека Evaluation вы выталкиваете необходимое количество операндов (вы знаете это из-за другого значения кортежа), выталкиваете оператор и выполняете операцию, чтобы получить новое значение (или операнд).
Теперь поместите новый операнд обратно в стек вычислений. Этот новый ввод операнда заставляет вас еще раз взглянуть на вершину стека Count и сделать то же самое, что мы только что сделали (уменьшить количество видимых операндов, сравнить с нулем и т. д.).
Если количество операндов не становится равным нулю, вы продолжаете со следующей лексемы на входе.
Например, вам нужно было оценить + 3 + 4 / 20 4
Стеки будут выглядеть так (слева — вершина стека)
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
РЕДАКТИРОВАТЬ:
Друг предложил способ сделать это без нескольких стеков:
Начните с конца, идите к первому оператору. Токены справа от этого будут операндами. Оценить и повторить. Кажется намного проще, чем делать это с двумя стеками. Мы можем использовать двусвязный список для представления входных данных, которые мы изменяем во время обработки. При оценке вы удаляете узлы, а затем вставляете результат. Или вы могли бы просто использовать один стек.
KISS, оценивайте в обратном порядке как постфиксное выражение.
Как я вижу, у вас есть два варианта. Либо идите слева направо, либо справа налево (как Павел предложил выше). Оба метода демонстрируются в приведенном ниже коде.
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];
}
}
}
Некоторые тесты:
[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"));
}