Homework 5

Your task is to evaluate expressions like 3.4-(2.6+5.0) and sin(-1.0)*2.0 and -9.4^log(exp(cos(4.5)-2.3+3.5)). These expressions will be represented in “parse trees” such as the following:

3.4-(2.6+5.0) in tree form:

    -
   / \
  /   \
3.40   +
      / \
     /   \
    /     \
  2.60   5.00

sin(-1.0)*2.0 in tree form:

          *
         / \
        /   \
      sin  2.00
      /
     -
    / \
   /   \
  /     \
0.00   1.00

-9.4^log(exp(cos(4.5)-2.3+3.5)) in tree form:

       -
      / \
     /   \
   0.00   ^
         / \
        /   \
      9.40  log
            /
          exp
          /
         +
        / \
       /   \
      -   3.50
     / \
    /   \
  cos  2.30
  /
4.50

These trees are arbitrarily large; your program should evaluate the expression represented in any such tree. Your algorithm must be recursive (for practice and because recursion is the most effective technique for processing trees).

Tree structure

You must use the following structure to represent a tree. Note: do not add this to your main.cpp; it is already inside math_tree.h which you will already have.

class Tree
{
public:
    std::string op;
    double val;
    Tree *left;
    Tree *right;
};

Notice that this is a recursive definition. Every “node” in the tree (for example, in the first tree above, the nodes are -, +, 5.00, 3.40, and 2.60) is itself a tree. Take any node, such as +: now you have another tree (+ at the top with 2.60 on the left and 5.00 on the right).

Each “node” simply needs to store information about the operation (e.g. +, -, sin) or the value (e.g. 3.40) in addition to pointers to the left and right subtrees. A node cannot be both a value and an operation. We’ll use the following convention to determine if a node is an operation or just a value: the op variable should only be non-empty if the node is an operation; otherwise, the node is a value and the value is stored in val. You can test if the op variable is empty, in a Tree pointer variable named root, with the following expression: if(root->op.empty())

Here is how the tree at the beginning of this homework can be represented:

Tree m;
m.op = "-";
Tree p;
p.op = "+";
Tree v1;
v1.val = 3.4;
Tree v2;
v2.val = 2.6;
Tree v3;
v3.val = 5.0;

m.left = &v1;
m.right = &p;

p.left = &v2;
p.right = &v3;

v1.left = v1.right = v2.left = v2.right = v3.left = v3.right = NULL;

Note that operations (like ‘+’) always have two subtrees; functions (like sin) have only left subtrees, where the right pointer is always NULL. For values, both left and right pointers are always NULL.

Automatic parsing

Writing trees “by hand” in your code is very difficult and does not allow the user to interactively provide new expressions. In order to allow user input, we need to take a string like “3.4-(2.6+5.0)” and turn it into the right tree structure. This task is known as “parsing,” and can be quite difficult to code if you don’t use the right tools. A parser has been coded for you to use in your program.

Set up your editor

You need to download some files (.cpp files and .h files) and load these as your CodeBlocks/Visual Studio/Xcode “project.”

Here is a ZIP package with all the files you need: hw4.zip

In there you’ll also find main.cpp — use that file to begin writing your own code. You’ll see some instructions in the file. In particular, you will see a loop that allows the user to type an expression and have it evaluated (you won’t need to modify that loop; if you provide the rest of the code, the “interactive” parsing feature should work properly).

Videos for setting up Windows IDEs. Watch the CodeBlocks video or the VisualStudio video.

Your task

As mentioned, the main.cpp file found in the zip package has some code but is missing some important functions. You must write the code for these functions, and you must “hand-code” a tree structure at the beginning of the main() function (look at the comments in the file).

The functions you need to code are the following:

double evalOp(string op, double val)
{
    // for evaluating functions like sin, cos, etc.
}

double evalOp(string op, double val1, double val2)
{
    // for evaluating operators like +, -, etc.
}

double eval(Tree *root)
{
    // for (recursively) evaluating a tree; this function will refer
    // back to itself (for evaluating subtrees) and will use the
    // evalOp() functions
}

The eval() function is the primary evaluation function; it accepts a tree pointer and determines its value in a recursive fashion. The other two evalOp functions, which have the same name but different parameters, apply operators (like ‘+’) or functions (like ‘sin’) to their parameters (val1 and/or val2).

Your program must support the following operators: +, -, *, /, and ^ (e.g. 3^2 equals 9). Your program must also support the following functions: sin, cos, tan, log, abs. Add support for more functions if you wish.

User interface

Here is a sample interaction with your program:

Enter expression: 2^3^4

        ^
       / \
      /   \
     ^   4.00
    / \
   /   \
  /     \
2.00   3.00

Result: 4096

Enter expression: log(2.71828^8)

      log
      /
     ^
    / \
   /   \
  /     \
2.72   8.00

Result: 7.99999

Enter expression: sin(tan(cos(sin(tan(cos(3.14159))))))

            sin
            /
          tan
          /
        cos
        /
      sin
      /
    tan
    /
  cos
  /
3.14

Result: 0.564596

Enter expression: sin(4.0)/cos(4.0)

       /
      / \
     /   \
    /     \
  sin     cos
  /       /
4.00    4.00

Result: 1.15782

Enter expression: tan(4.0)

  tan
  /
4.00

Result: 1.15782

Enter expression: sin(3.14159 / 2.0) + cos(3.14159 * 2.0)

              +
             / \
            /   \
           /     \
          /       \
         /         \
        /           \
      sin           cos
      /             /
     /             *
    / \           / \
   /   \         /   \
  /     \       /     \
3.14   2.00   3.14   2.00

Result: 2

Final words

When you give me your code, you only need to send me main.cpp, unless you happened to have modified other files as well.