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?

9 Years
Discussion Span
Last Post by ciuchi

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 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.


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.

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.