0

私は現在、単純な数式 (定数と単純な算術演算) のインプリータを作成しています。

私が抱えている問題は、後置形式の式から式ツリーを構築することです。私がやったことはほとんどのシナリオでうまくいきますが、ウィキペディアのこの例ではうまくいきません。

式を評価すると、結果が になるはずなのに、結果が得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 に答える