# 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 formula`3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3` I get the outcome.`3,0001220703125` even while the outcome ought to`3,001953125` . The expression tree seems to be the cause of issue, since it looks like`3+((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

#### Fastest Entity Framework Extensions

`^` 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

Prime Library

More Projects...