Mathematical expression reducing algorithm

[ciuchi]

I have been searching for a solution to this problem:
I'm given an expression in infix which can contain *,/,-,+ and I have to find the reduced form of this expression.
Ex: Input: ((A+45)*16+(B-C)*D/4 )/8+ 55
Output: A*2+B*D/32-C*D/32 +145

All that can be calculated must be calculated and the simplest form must be returned.
A,B,C,D do NOT have numeric values. They are name of variables.
The expressions that have to be calculated can be more complicated.
I have found on the net algorithms that only evaluate expressions that have numerical values in them(or variables that are replaced by numerical values).

What I have done: I have translated the expression into expression tree form and now I'm a bit lost.

Can you help?

[Rashakil Fol]

First, you have to formally define reduced form. Does this mean converted to a polynomial?

Okay. Then convert all divisions by a real number to multiplications by the real number's reciprocal.

Then, to simplify an expression tree, do the following:

1. If combined by addition, simplify the subtrees, and then check for similar polynomial terms (with the same combination of variables) and combine them.

2. If combined by multiplication, simplify the subtrees, then use the distributive property if necessary and resimplify all the children of your addition operations, then recombine like terms. If the distributive property can't be exploited, combine whatever constants/variables you have in the multiplication.

It might be worthwhile to have (while simplifying) a direct representation for associative chained additions and multiplications.

This version's not necessarily the most efficient way...

[iamthwee]

All you need to do is consider how you are going to represent and handle your multivariate polynomial class.

http://www.cs.tamu.edu/academics/tr/tamu-cs-tr-2004-7-4

Simple it is - and it doesn't handle trignometric functions or more complex expressions.

However, once you have that in place you can use whatever you want to parse through it.

http://www.daniweb.com/code/snippet599.html

Using trees, is another option.

[Rashakil Fol]

iamthwee has a good point. Just make a multivariate polynomial class that describes polynomials as a list of terms, then implement addition and multiplication on them. That's a better way of describing it.

[ciuchi]

Thanks alot.
I just browsed through the document with the multivariable polynom and I think it's just what I need.
This was something I was thinking about in a very simplified maner.
Thanks again and if there's somebody with a different solution please don't hesitate to post.