Home

HW05: Mathtree

Copy the code in /home/jeckroth/csci221/homework/HW05/mathtree and finish writing the file mathtree.cpp. That’s it!!1

Grader script

/home/jeckroth/csci221/homework/HW05/grader.pl

Note, the ASCII trees need not be printed. You can comment out that code in main.cpp (but leave the cout’s).

The test script handles some variability with parentheses and spaces. However, you might want to compare your output to the “gold standard” program mathtree-comparison.

Background

I wrote a parser that builds a binary tree representing a mathematical expression. I also adapted someone else’s work on printing trees in ASCII. The mathtree program reads a mathematical expression from the user, prints the ASCII tree version of it, then both simplifies and finds the derivative (and simplifies the derivative). These results are printed as well, both in ASCII tree form and normal math notation.

Your task

You need to write all the functions that have “TODO” markers in mathtree.cpp. These functions are:

Hint

Use clone() in other parts of your code to ensure you never restructure a tree by just modifying its pointers. Always use a clone, and (possibly) delete the original. The functions derive() and simplify_rec() must always return an entirely new tree and share no nodes with any other trees. If you do not heed this advice, good luck to you in your future endeavors!

About the tree structure

These trees have left/right subtrees, which might be NULL, and some other values:

There are convenience functions is_var(), is_val(), is_unary_op(), and is_binary_op() that determine the nature of a tree.

Simplification rules

During simplification, produce a new tree according to the following rules.

If those rules don’t apply, return a clone of the original tree.

Derivative rules

Etc. I’ll leave the rest up to you. You must implement these derivation rules:

Example 1

Enter expression: 5 + 2 * 3

Original tree:

    +
   / \
  /   \
5.00   *
      / \
     /   \
    /     \
  2.00   3.00

Simplified tree:

11.00

Printed in order:
11


Derivative tree:

         +
        / \
       /   \
     0.00   +
           / \
          /   \
         /     \
        /       \
       /         \
      /           \
     *             *
    / \           / \
   /   \         /   \
  /     \       /     \
2.00   0.00   0.00   3.00

Printed in order:

(0 + ((2 * 0) + (0 * 3)))

Simplified derivative tree:

0.00

Printed in order:

0

Example 2

Enter expression: x

Original tree:

x

Simplified tree:

x

Printed in order:
x


Derivative tree:

1.00

Printed in order:

1

Simplified derivative tree:

1.00

Printed in order:

1

Example 3

Enter expression: 5^x

Original tree:

    ^
   / \
  /   \
5.00   x

Simplified tree:

    ^
   / \
  /   \
5.00   x

Printed in order:
(5 ^ x)


Derivative tree:

         *
        / \
       /   \
      /     \
     /       \
    ^         +
   / \       / \
  /   \     /   \
5.00   x   /     \
          /       \
         /         \
        *           *
       / \         / \
      /   \       /   \
    0.00   /    1.00  ln
          / \         /
         /   \      5.00
        x   5.00

Printed in order:

((5 ^ x) * ((0 * (x / 5)) + (1 * ln(5) )))

Simplified derivative tree:

       *
      / \
     /   \
    ^   1.61
   / \
  /   \
5.00   x

Printed in order:

((5 ^ x) * 1.60944)

Example 4

Enter expression: sin(cos(x))

Original tree:

   sin
   /
 cos
 /
x

Simplified tree:

   sin
   /
 cos
 /
x

Printed in order:
sin(cos(x) ) 


Derivative tree:

       *
      / \
     /   \
   cos    *
   /     / \
 cos    /   \
 /     -   1.00
x     / \
     /   \
   0.00  sin
         /
        x

Printed in order:

(cos(cos(x) )  * (-sin(x)  * 1))

Simplified derivative tree:

       *
      / \
     /   \
   cos    -
   /     / \
 cos    /   \
 /    0.00  sin
x           /
           x

Printed in order:

(cos(cos(x) )  * -sin(x) )

Example 5

Enter expression: sin(x) + cos(5 * ln(x))

Original tree:

     +
    / \
   /   \
 sin   cos
 /     /
x     *
     / \
    /   \
  5.00  ln
        /
       x

Simplified tree:

     +
    / \
   /   \
 sin   cos
 /     /
x     *
     / \
    /   \
  5.00  ln
        /
       x

Printed in order:
(sin(x)  + cos((5 * ln(x) )) )


Derivative tree:

           +
          / \
         /   \
        /     \
       /       \
      /         \
     *           *
    / \         / \
   /   \       /   \
 cos  1.00    /     \
 /           /       \
x           /         \
           /           \
          /             \
         -               +
        / \             / \
       /   \           /   \
     0.00  sin        /     \
           /         /       \
          *         /         \
         / \       *           *
        /   \     / \         / \
      5.00  ln   /   \       /   \
            /  5.00   /    0.00  ln
           x         / \         /
                    /   \       x
                  1.00   x

Printed in order:

((cos(x)  * 1) + (-sin((5 * ln(x) ))  * ((5 * (1 / x)) + (0 * ln(x) ))))

Simplified derivative tree:

       +
      / \
     /   \
   cos    *
   /     / \
  x     /   \
       /     \
      /       \
     /         \
    -           *
   / \         / \
  /   \       /   \
0.00  sin   5.00   /
      /           / \
     *           /   \
    / \        1.00   x
   /   \
 5.00  ln
       /
      x

Printed in order:

(cos(x)  + (-sin((5 * ln(x) ))  * (5 * (1 / x))))
CSCI 221 material by Joshua Eckroth is licensed under a Creative Commons Attribution-ShareAlike 3.0 Unported License. Source code for this website available at GitHub.