Simplify Algebraic Expression

Question

Possible duplicate:
Math Simplification Strategies

I have a math expression parser that builds a tree to represent an expression. Say, for example, input 2+y+3+y , the internal representation of this would be:

Now, as humans, we can immediately see that 2+y+3+y = 2y + 5 . The hard part for the computer that I see is that if I stood on the left + , I would not know that I have another add-on on the right in another branch - it does not matter when evaluating, but when simplified, I don’t see how it can be done beautifully.

Here's how the classes fit together:

I tried to do this Google, but did not find anything that could help me here. Only some common waypoint will be evaluated, or a URL or something in general.

EDIT: Please note that for example, I have included only the add-on. The parser supports expressions like: 1 + 2 * (3 ^ 4-4 / 5 * (1 + 2))

Answer 1

Since the set of expressions that can be expressed in your class structure is very limited, you can simply calculate how often each variable happens and summarize all the constants.

 var nodes = tree.Flatten(); var variables = nodes .OfType<Variable>() .GroupBy(x => x.Name) .Select(g => new Multiplication( new Variable(g.Key), new Constant(g.Count()))); var constants = nodes .OfType<Constant>() .Sum(x => x.Value); var result = new Addition( variables.Aggregate((x, y) => new Addition(x, y)), new Constant(constants));