You are here:

C++/expression tree


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  

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.



All Answers

Answers by Expert:

Ask Experts


David Spector


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.


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.

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

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

©2017 All rights reserved.