Problems building expression tree from postfix notation

algorithm expression-trees language-agnostic postfix-notation

Question

For basic mathematical expressions (constants and simple arithmetic), I'm presently building an impreter.

Building an expression tree from a postfix-formatted expression is where I'm having trouble. Most of the time, what I've done is fine, but not with this Wikipedia example..

If I assess the formula3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3 I get the outcome.3,0001220703125 even while the outcome ought to3,001953125 . The expression tree seems to be the cause of issue, since it looks like3+((4*2)/((1-5)^(2^3))) in place of(3+((4*2)/(((1-5)^2)^3))) .

The original expression's postfix notation appears as follows:3 4 2 * 1 5 − 2 3 ^ ^ / +

Any ideas on how I can get the expression tree the way I want it?
The postfix to the expression tree code and some tests are below; they are written in C#, but they should be fairly 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();
}

further 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
}
1
0
7/4/2012 11:49:05 AM

Accepted Answer

This statement is on the WikiPedia page:

^ is evaluated right-to-left

Your code doesn't seem to take it into consideration.^ is considered as left-associative, the same as the other operators.

This suggests that your understanding may be incorrect:

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

3,0001220703125, your code, and the original response, are both accurate.

5
7/5/2012 4:10:16 PM


Related Questions





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