Constructing a tree from an algebraic equation

Question

How do I take an algebraic expression and construct a tree out of it?

Sample equation:

((2 + x) - (x * 3)) - ((x - 2) * (3 + y))

If somebody can teach me in steps, that would be really helpful!

Answer 1

You are looking for a syntax tree, and that is part of what parsing is all about. This is more suited for http://cs.stackexchange.com or perhaps http://www.stackoverflow.com. The "compiler-compilers" (parser generators) are programs that given a grammar construct programs that (essentially) create such trees. There are plenty...

Answer 2

Each internal node (or vertex) of the tree will be labelled by one of the operators appearing in the expression, and each leaf by one of the operands. The algorithm is quite straightforward. Start with the operation that would be performed last if you were evaluating the expression. In the case of the expression

$$\big((2 + x)-(x*3)\big)\color{red}{-}\big((x-2)*(3+y)\big)$$

that’s the subtraction that I’ve colored red. The node corresponding to this operation will be the root of your tree. Its first operand is the expression $(2+x)-(x*3)$, and its second is the expression $(x-2)*(3+y)$; these correspond to the left and right children of the root. Thus, at this stage we have this tree:

                                      -  
                                     / \  
                                    /   \  
                                   /     \  
                          (2+x)-(x*3)   (x-2)*(3+y)

Repeat the process on each of the two leaves of this little tree. On the left the last operation that we’d perform is the subtraction; on the right it’s the multiplication. Thus, the left node gets the label $-$ and children $2+x$ and $x*3$, and the right node gets the label $*$ and the children $x-2$ and $3+y$:

                                      -  
                                     / \  
                                    /   \  
                                   /     \  
                                  -       *  
                                 / \     / \  
                                /   \   /   \  
                              2+x  x*3 x-2  3+y

Continue in the same way until each node is labelled either with an operation, in which case it has children corresponding to the operands to which that operation is applied, or with an operand, in which case it has no children. Here each leaf requires just one more step, and we end up with the following tree:

                                      -  
                                     / \  
                                    /   \  
                                   /     \  
                                  /       \  
                                 /         \
                                -           *  
                               / \         / \  
                              /   \       /   \  
                             +     *     -     +  
                            / \   / \   / \   / \  
                           2   x x   3 x   2 3   x

In this example the leaves are all on the same level of the tree, but that need not happen. Had the original expression been $\big((2+x)-(x*3)\big)-(x-2)$, for instance, the final tree would have been this one:

                                      -  
                                     / \  
                                    /   \  
                                   /     \  
                                  /       \  
                                 /         \
                                -           -  
                               / \         / \  
                              /   \       /   \  
                             +     *     x     2  
                            / \   / \  
                           2   x x   3

Observe that just as we can systematically construct the tree from the expression, so we can also reverse the procedure. Start at the bottom and combine children according to their parent operation, replacing the operation label with the resulting expression. If you apply this process to the last tree above, for instance, you get the following tree after the first two recombinations:

                                      -  
                                     / \  
                                    /   \  
                                   /     \  
                                  /       \  
                                 /         \
                                -           -  
                               / \         / \  
                              /   \       /   \  
                            2+x   x*3    x     2  

The next two recombinations produce this one:

                                      -  
                                     / \  
                                    /   \  
                                   /     \  
                                  /       \  
                                 /         \
                           (2+x)-(x*3)     x-2  

(Note that when you recombine expressions that aren’t single operands, as on the left side of this tree, you enclose them in parentheses.) And one more step yields a tree consisting only of a root labelled by a single expression, that expression being the one that produced the tree in the first place, namely, $\big((2+x)-(x*3)\big)-(x-2)$.