Data Structure for Representing a Math Expression

Problem Detail: 

I'm looking to improve my object-oriented design skills and I came across a problem which asked to design classes to represent a mathematical expression such as (a + b) * ( c - d / e) in memory so that it could be evaluated (by adding an evaluate method if need be in the class some time later)

The simplest solution I came up with was to store this expression in a stack (push(a), push(+), push(b)....), or may be even in an array (arr[0] = a, arr[1] = +...)

I feel like this is bad design and I read online that a binary tree (expression tree) is better to represent such an expression, but I am not sure why it is better.

Can someone help me understand this? Does the binary expression tree provide some benefits over storing in a stack?

Asked By : Shobit

Answered By : jkff

Different representations are useful for different purposes. Think what kinds of things you might want to do with the expression, and think how each of them would be done using the stack representation and using the binary tree representation, and choose for yourself.

For fun, you may also want to consider something completely different, e.g. the english language representation: e.g. "the product of the sum of a and b, and the difference between c and d over e", or the representation as X86 machine code which would compute this expression, etc.

Things you may want to do with an expression (in any particular program you would probably need only a small subset of these):

• Evaluate it, given certain values of the variables
  • Just once
  • Evaluate the same expression repeatedly for different values, with very high performance requirements
• Perform simple algebraic manipulation, e.g. simplifications such as replacing x - x => 0, x*1 => x, etc.
• Perform sophisticated algebraic manipulation on it, e.g. factorize the polynomials, compute derivatives or integrals.
• Understand the expression stored in a variable when you're debugging the program
• Format it as a string for displaying to the user
• Render it as a mathematical expression to MathML
• Draw it as a mathematical expression on a Javascript canvas
• Compare two expressions for equivalence
• Compare two expressions for equivalence ignoring variable names, e.g. a * a + b being equivalent to p * p + q
• Convert a user-supplied string into an expression, checking it for well-formedness
• ...

Honestly speaking, I can find only one item of these for which the stack representation can possibly make things easier than the binary tree representation, and the array representation seems just completely useless.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/38380