Problems building expression tree from postfix notation

algorithm expression-trees language-agnostic postfix-notation

Question

I'm currently writing an impreter for simple mathematical expressions (constants and simple arithmetic).

The problem I'm having is with building an expression tree from a postfix formatted expression. What I've done works fine in most scenarios, but not with this example from Wikipedia.

If I evaluate the expression 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3, I get the result 3,0001220703125 even though the result should be 3,001953125. The reason for this seems to be that the expression tree looks like 3+((4*2)/((1-5)^(2^3))) instead of (3+((4*2)/(((1-5)^2)^3))).

The postfix notation of the original expression looks like 3 4 2 * 1 5 − 2 3 ^ ^ / +

Any suggestions how to get the expression tree as I want it to be?
Below is the postfix to expression tree code and some tests which is in C# but should be pretty self-explanatory.

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();
}

And some tests:

[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
}

Accepted Answer

The WikiPedia page contains this remark:

^ is evaluated right-to-left

I don't see your code taking that into account, ^ is treated the same as the other operators, as left-associative.

That means that your interpretation might be wrong:

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

and your code and original answer (3,0001220703125) are correct.



Licensed under: CC-BY-SA with attribution
Not affiliated with Stack Overflow
Licensed under: CC-BY-SA with attribution
Not affiliated with Stack Overflow