我目前正在为简单的数学表达式(常量和简单的算术)编写一个 impreter。
我遇到的问题是从后缀格式的表达式构建表达式树。我所做的在大多数情况下都可以正常工作,但不适用于 Wikipedia 中的这个示例。
如果我评估表达式,即使结果应该是3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3
,我也会得到结果。原因似乎是表达式树看起来像而不是.3,0001220703125
3,001953125
3+((4*2)/((1-5)^(2^3)))
(3+((4*2)/(((1-5)^2)^3)))
原始表达式的后缀表示法看起来像3 4 2 * 1 5 − 2 3 ^ ^ / +
任何建议如何获得我想要的表达式树?
下面是表达式树代码的后缀和一些 C# 中的测试,但应该是不言自明的。
public MathExpression Parse()
{
var tokens = this.ToPostFix(_tokens);
var stack = new Stack<MathExpression>();
foreach(token in tokens)
{
if(token.IsOperand())
{
// Push the operand on the stack.
stack.Push(new ConstantExpression(token.Value));
}
else
{
Debug.Assert(token.Type == TokenType.Operator, "Expected operator.");
var op = (Operator)token.Value;
var right = stack.Pop();
var left = stack.Pop();
var expression = new ArithmeticExpression(op, left, right);
stack.Push(expression);
}
}
Debug.Assert(stack.Count == 1, "More than one expression on stack.");
return stack.Pop();
}
还有一些测试:
[Test]
public void Wikipedia_Example_Can_Be_Evaluated()
{
var expected = 3+4*2/(1-5)^2^3; // 3,001953125
var actual = MathExpression.Parse("3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3")
.Evaluate(); // 3,0001220703125
Assert.AreEqual(expected, actual); // Not equal :(
}
[Test]
public void Can_Convert_To_Prefix()
{
string expected = "3 4 2 * 1 5 − 2 3 ^ ^ / +"
string actual = MathExpression.ToPostFix("3+4*2/(1-5)^2^3")
Assert.AreEqual(expected, actual); // Works as expected
}