0

我目前正在为简单的数学表达式（常量和简单的算术）编写一个 impreter。

我遇到的问题是从后缀格式的表达式构建表达式树。我所做的在大多数情况下都可以正常工作，但不适用于 Wikipedia 中的这个示例。

如果我评估表达式，即使结果应该是3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3，我也会得到结果。原因似乎是表达式树看起来像而不是.3,00012207031253,0019531253+((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
}
4

1 回答 1

5

维基百科页面包含以下评论：

^从右到左评估

我没有看到您的代码考虑到这一点，^它与其他运算符一样被视为左关联。

这意味着您的解释可能是错误的：

x ^ 2 ^ 3 => x^(2^3)=>x 2 3 ^ ^

并且您的代码和原始答案（3,0001220703125）是正确的。

于 2012-07-04T11:37:38.400 回答