8

Possible Duplicate:
Strategies for simplifying math expressions

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

enter image description here

Now, we, as humans, can immediately see that 2+y+3+y = 2y + 5. The tricky part for the computer that I see, is that if I would be standing on the left +, I would have no idea that I have another addition to the right in the other branch - this doesn't matter when evaluating but when simplifying i don't see how this can be done nicely.

This is how the classes fit together: enter image description here

I have tried to google this, but have found nothing that could help me here. Just some general waypoint, or an url or something at all would be appreciated

EDIT: Note that for the example i have only included addition. The parser supports expressions like : 1+2*(3^4-4/5*(1+2))

Community
  • 1
  • 1
ErikTJ
  • 2,001
  • 3
  • 21
  • 38
  • Addition is transitive. From the root +, can it not see that both children are also addition: meaning it can rearrange the constants and variables as it sees fit? – Colin D May 09 '12 at 20:28
  • 2
    Could you make `+` have more than 2 children? I believe symbolic math languages like Mathematica would store your example as a list `[2,y,3,y]` with a head of `Plus`, which would then get simplified automatically using some rules. – JohnPS May 09 '12 at 20:31
  • 2
    Is that really how your parse tree gets built? I bet it isn't. – Novak May 09 '12 at 20:32
  • 1
    @Novak you're probably right. I would guess the left branch just consists of the constant 2. – ErikTJ May 09 '12 at 20:37
  • @ColinD I have many more operators and functions than just addition. It wouldn't fit in the width of SO. – ErikTJ May 09 '12 at 20:39
  • Since a+b+c = c+b+a why not let addition have a list of SymbolicExpression's. That's one step. But then you have that 2y is a multiplication of a constant 2 and a variable y. And 2y+3y = 5y might be somewhat harder... – erikH May 09 '12 at 20:43
  • I think the hardest part of your problem then is with the parts you don't show, i.e. precedence and scope (grouping with parentheses), and determining what CAN be combined that correctly respects those. Wouldn't an answer helpful to you need to consider that? – hatchet - done with SOverflow May 09 '12 at 20:45
  • Explicit parentheses output is done by SymbolicExpression having a int Priority-getter, which the childs override. + having a lower priority than * for example. So if addition is a child of multiplication the addition gets a parenthesis – ErikTJ May 09 '12 at 20:51
  • 4
    Have you seen http://stackoverflow.com/questions/7540227/strategies-for-simplifying-math-expressions? – ie. May 09 '12 at 20:51
  • I just found something called _prefix notation_. Seems promising – ErikTJ May 09 '12 at 20:56
  • @ie. that looks horrible. There must be a better way. – ErikTJ May 09 '12 at 20:56
  • Please ignore my previous answer and accept my apology for dropping such a brain-fart on your question. – Vivian River May 09 '12 at 21:06
  • @ErikTJ that looks perfect! just like the musik for the eyes ;) – ie. May 09 '12 at 21:22
  • Yep, that ruleset looks exactly what you'll want. – dtb May 09 '12 at 21:27
  • 1
    I guess I'm also uncertain as to why you want to do this: Is it intended to be a compiler optimization to get the compiled code to run faster? Is it part of a symbolic package meant to display information to humans? Something else> – Novak May 10 '12 at 00:26
  • @Novak No, it's just for fun. – ErikTJ May 10 '12 at 08:28
  • Object oriented programming is the wrong tool for the job here. Symbolic computations are much more easily solved using algebraic data types (sums and products) and pattern matching. Try using a language like Standard ML, OCaml, Haskell, F#, Mathematica or even Scala. – J D Mar 17 '17 at 22:14

1 Answers1

0

Since the set of expressions that can be expressed with your class structure is quite limited, you can simply count how often each variable occurs and sum 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));
dtb
  • 213,145
  • 36
  • 401
  • 431
  • I included a limited number of operators and functions. I have + - * / log pow exp ( ). – ErikTJ May 09 '12 at 20:37
  • 4
    @ErikTJ: But you asked only about addition. A generic solution for arbitrary algebraic expression is something you're likely to find in CS text books; IMO it's too much to ask for here. – dtb May 09 '12 at 20:42