You are here:

C++/expression tree

Advertisement


Question
Hi again.
I did it . It was an easy program but if we have two expresion tree  " x = * "
1-" a x (b+c) "
2-" a x b + a x c"
these two tree are the same.
how can we compair these two trees?
We know that root node of these tree are not the same.
for example for tree 1 root node is " * " and for tree 2 is "+"
now how can I compair these two tree>?
thanks alot
siyavash khojasteh  

Answer
siyavash khojasteh, You have given examples of two expression trees, however, they are not expression trees. Recall that you defined an expression tree recursively as an operator with two operands, each of which were constants, variables, or expression trees. Such an expression tree cannot represent parenthesized operations unless you include parentheses as operators.

If your program scans expressions and builds up expression trees, one way to do what you are asking is to look for this specific pattern during the recursive tree walk, for example by expanding parenthesized products.

This means that the program will "rewrite" the input as an "expanded" tree. Then the pattern matching is done as usual on the expanded tree.

The inputs "a * (b + c)" and "(a * b) + (a * c)" would result in the same expanded tree under such a rewriting program, because the first would be rewritten as the second.

David

C++

All Answers


Answers by Expert:


Ask Experts

Volunteer


David Spector

Expertise

Highly knowledgeable in the C++ language, Visual C++ (MSVC), Windows API, documentation and other quality-assurance techniques, and debugging. Knowledgeable in MFC, COM, GUI design, and object-oriented design.

Experience

I have been a software engineer since 1965. I have been published. My specializations have been: biomedical programming, compiler implementation, and many kinds of Windows programming. I don't do Databases or other business-oriented stuff.

Publications
Windows?/DOS Developer's Journal, ACM SIGPLAN Notices, and Computer Science Press.

Education/Credentials
ICCP Systems Programming Certification
Master's degree equivalent in Computer Science

©2016 About.com. All rights reserved.