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

Question

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) {

}

Explanation / Answer

The required functions are implemented and main() function is given to test the correctness of implementation. Output is shown at the end. Please take the 2 functions from below code. Please don't forget to rate the answer if it helped. Thank you very much.

#include <iostream>
using namespace std;
struct Node {
Node(char inVal, Node *inLeft, Node *inRight) : val(inVal), left(inLeft), right(inRight) {
}
char val;
Node *left;
Node *right;
};

// op: an operator to be added
// digit: a right-hand side operand that goes with op
Node *addOp(Node *root, char op2, char digit) {
char op1 = root->val;
Node *n = new Node(op2, NULL, new Node(digit, NULL, NULL));
Node *newRoot = n;
if(op2 == '*' || op2 == '/')
{
//check if op1 is lower precedence operators + -
if(op1 == '+' || op1 == '-')
{
//move the right operand of the input root node as the left operand for the new node
n->left = root->right;
root->right = n;
newRoot = root;
}
else //otherwise the input root will simply be the left operand of new node
{
n->left = root;
}
}
else
{
n->left = root;
}
  
return newRoot;
}

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;
}

int evaluate(Node *root) {
int operand1, operand2;
char val = root->val;
string operators ="+-/*";
if(operators.find(val) != string::npos)//if the root is an operator
{
operand1 = evaluate(root->left); //get value of left operand
operand2 = evaluate(root->right); //get value of right operand
  
if(val == '+')
return operand1 + operand2;
else if(val == '-')
return operand1 - operand2;
else if(val == '/')
return operand1 / operand2;
else
return operand1 * operand2;

}
else
return val - '0'; //subtract ascii value of zero to get number
}

int main()
{
string expr[7] = {"2+3*5", "2*3+5", "3+4-5", "4/2*3", "4*9/3", "5", "1+2+3/4*5-6"};
  
for(int i = 0; i < 7; i++)
{
Node *root = createArithmeticExpTree(expr[i]);
cout << expr[i] << " = " << evaluate(root) << endl;
}
}

output

2+3*5 = 17
2*3+5 = 11
3+4-5 = 2
4/2*3 = 6
4*9/3 = 12
5 = 5
1+2+3/4*5-6 = -3

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.