Define a function that generates an arithmetic expression tree, given an infix arithmetic expression.

Assume there are only four binary operators involved (+, -, *, /), and there is no parenthesis, and every number is a single digit. * and / have higher precedence than + and -, and if two consecutive operators have the same precedence, they must be evaluated from left to right. We will write createArithmeticExpTree, a function that takes in a valid arithmetic expression as a string and generates an expression tree. Assume the following structure.

struct Node {

Node(char inVal, Node *inLeft, Node *inRight) : val(inVal), left(inLeft), right(inRight) {

}

char val;

Node *left;

Node *right;

};

Here is an implementation of createArithmeticExpTree, which uses a helper function called addOp.

Node *createArithmeticExpTree(string exp) {

if (exp.empty())

return NULL;

Node *root = new Node(exp[0],NULL, NULL);

for (int i = 1; i < exp.size(); i += 2)

root = addOp(root, exp[i], exp[i + 1]);

return root;

}

(a) On the next page, provide the implementation for addOp.

// op: an operator to be added

// digit: a right-hand side operand that goes with op

Node *addOp(Node *root, char op, char digit) {

}

(b) Write evaluate, which takes in an arithmetic expression tree and returns the evaluated result of the expression. Assume the division (/) is integer division (i.e., decimal points are cut off).

int evaluate(Node *root) {

}