PART 3 EXPRESSION TREE and in prefix notation, the operator is placed before the operands. In both of these notations, each operation is sequentially written in its correct order of precedence, liberating us from the necessity to use parentheses. There are a lot of tools online, like this to help you play with and internalize these different notations. 7. By the end, the stack will only have one tree left. This will be our completed expression tree! If the optimal flag is set to true, the tree would be: and returns the value of the passed currNode and its descendants. variables is a vector of the struct Variable that stores the variable names and their corresponding values. An important application of trees is calculating expressions. Take for example the following expression: (a*(b+2)/(7-c/d). The infix notation corresponding to this tree should (b+4)/(a*2). As another example, let's take the tree made by the postfix expression a5+b+a+6-1-d+. This tree will have an infix expression of (((((a+5)+b)+a)-6)-1)+d. In this part of the assignment, we will explore the use of expression trees. Let's head right in! Instructions: While calculating, divisions should not be integer divisions. . You should assume that all variables used in the expression are provided in the variables vector If the expression tree is NULL, -99 should be returned This expression has varying levels of precedence as defined by PEMDAS. To calculate such an expression with the right precedence, we can build a binary expression tree: Instructions: Our postfix expression will only contain the operators + -*/, numeric values from 0 to 9, and variables with lowercase names of length 1 from 'a' to 'z. This means that values in each node of our expression tree are one character long in length. You should use the standard C++ stack class. Its documentation is available here, and this is a helpful guide. An empty postfix expression should be set to NULL. We will assume that the given postfix expression is valid. e.g. the following is not a valid postfix expression: abc+. You will be implementing the ExpTree class in exp_tree.cpp, defined in exp_tree.hpp. Instructions: If the expression tree is NULL, an empty string should be returned. 3.1 Building the Expression Tree from Postfix Notation: 3.3 Outputting the Infix Notation with Parentheses: Parsing a conventional infix expression to build an expression tree is a really fun problem. Unfortunately for us, it is out of the scope of this course. We will instead be building our expression tree from a postfix notation given to the following function: If you have implemented everything above correctly while ignoring the optimal flag, great work! You have secured 7 marks. Let's now look into the optimal boolean flag for the rest of the 3 marks Lastly, you would be implementing a function that generates the infix notation of the expression tree while adding parenthesis. Note that the right subtree of the root was all calculated and stored as a single node with a value of 9/(1+3)=2. void buildTree(string postfix_exp, bool optimal) This is the definition of the function you are going to implement: When this flag is set to true, the subtrees not containing any variables are computed and their result is stored in the tree as only one node. This can save us memory space. string getInfixRecurse (shared_ptr currNode) This function takes a postfix expression and a boolean flag named optimal, builds the corresponding expression tree, and stores it in the class's private variable root. We'll discuss the optimal boolean flag later. As an example, let's consider the postfix expression x2*913+/+. This will generate the following tree when the optimal flag is false Instructions: While calculating, the divisions will be integer divisions. You should assume that at every stage of the calculation, the result will be between 0 to 9 i.e. one character long in length. Be wary of correctly converting characters to integers, and vice versa where need be This is a function called on the root of the tree by string getInfix(). getInfixRecurse recursively returns the infix notation of the currNode and its descendants while adding parentheses. b 2 For example take the following tree: You will be using a renowned algorithm for generating the expression tree from a postfix notation. The algorithm is as follows: 1. Initialize an empty stack. 2. Go to the start of the postfix expression. 3. Read the next character. 4. If the character is a numeric value or a variable: a. Create a new expression tree with a single node having the numeric value 3.2 Calculating Value for the Expression Tree: This tree representation motivates three ways to write this expression: Infix: a*b+2/7-c/d Postfix: ab2+*7cd/-/ Prefix: /*a+b2-7/cd These are the inorder, postorder and preorder traversals of the tree respectively. or variable In this part you will implement calculating and outputting the value of the expression tree, given the values of the variables. 2 9 This is the definition of the function you are going to implement: b. Push this new tree into the stack. 5. If the character is an operator: a. Pop two trees (T, and T, respectively) out of the stack. b. Create a new expression tree with the operator at the root and trees T, and T, to its right and left respectively. c. Push this new tree into the stack. 6. Keep repeating from step 3 until the whole postfix expression is read. double calculateRecurse (shared_ptr currNode, vector variables) b 3 2 The infix notation is our conventional way to write expressions where the operator is placed between the operands. This necessitates addition of parenthesis to denote precedence. On the contrary, in postfix notation, the operator is placed after the operands; This is a function called on the root of the tree by double calculate(vector variables). calculateRecurse recursively calculates PART 3 EXPRESSION TREE and in prefix notation, the operator is placed before the operands. In both of these notations, each operation is sequentially written in its correct order of precedence, liberating us from the necessity to use parentheses. There are a lot of tools online, like this to help you play with and internalize these different notations. 7. By the end, the stack will only have one tree left. This will be our completed expression tree! If the optimal flag is set to true, the tree would be: and returns the value of the passed currNode and its descendants. variables is a vector of the struct Variable that stores the variable names and their corresponding values. An important application of trees is calculating expressions. Take for example the following expression: (a*(b+2)/(7-c/d). The infix notation corresponding to this tree should (b+4)/(a*2). As another example, let's take the tree made by the postfix expression a5+b+a+6-1-d+. This tree will have an infix expression of (((((a+5)+b)+a)-6)-1)+d. In this part of the assignment, we will explore the use of expression trees. Let's head right in! Instructions: While calculating, divisions should not be integer divisions. . You should assume that all variables used in the expression are provided in the variables vector If the expression tree is NULL, -99 should be returned This expression has varying levels of precedence as defined by PEMDAS. To calculate such an expression with the right precedence, we can build a binary expression tree: Instructions: Our postfix expression will only contain the operators + -*/, numeric values from 0 to 9, and variables with lowercase names of length 1 from 'a' to 'z. This means that values in each node of our expression tree are one character long in length. You should use the standard C++ stack class. Its documentation is available here, and this is a helpful guide. An empty postfix expression should be set to NULL. We will assume that the given postfix expression is valid. e.g. the following is not a valid postfix expression: abc+. You will be implementing the ExpTree class in exp_tree.cpp, defined in exp_tree.hpp. Instructions: If the expression tree is NULL, an empty string should be returned. 3.1 Building the Expression Tree from Postfix Notation: 3.3 Outputting the Infix Notation with Parentheses: Parsing a conventional infix expression to build an expression tree is a really fun problem. Unfortunately for us, it is out of the scope of this course. We will instead be building our expression tree from a postfix notation given to the following function: If you have implemented everything above correctly while ignoring the optimal flag, great work! You have secured 7 marks. Let's now look into the optimal boolean flag for the rest of the 3 marks Lastly, you would be implementing a function that generates the infix notation of the expression tree while adding parenthesis. Note that the right subtree of the root was all calculated and stored as a single node with a value of 9/(1+3)=2. void buildTree(string postfix_exp, bool optimal) This is the definition of the function you are going to implement: When this flag is set to true, the subtrees not containing any variables are computed and their result is stored in the tree as only one node. This can save us memory space. string getInfixRecurse (shared_ptr currNode) This function takes a postfix expression and a boolean flag named optimal, builds the corresponding expression tree, and stores it in the class's private variable root. We'll discuss the optimal boolean flag later. As an example, let's consider the postfix expression x2*913+/+. This will generate the following tree when the optimal flag is false Instructions: While calculating, the divisions will be integer divisions. You should assume that at every stage of the calculation, the result will be between 0 to 9 i.e. one character long in length. Be wary of correctly converting characters to integers, and vice versa where need be This is a function called on the root of the tree by string getInfix(). getInfixRecurse recursively returns the infix notation of the currNode and its descendants while adding parentheses. b 2 For example take the following tree: You will be using a renowned algorithm for generating the expression tree from a postfix notation. The algorithm is as follows: 1. Initialize an empty stack. 2. Go to the start of the postfix expression. 3. Read the next character. 4. If the character is a numeric value or a variable: a. Create a new expression tree with a single node having the numeric value 3.2 Calculating Value for the Expression Tree: This tree representation motivates three ways to write this expression: Infix: a*b+2/7-c/d Postfix: ab2+*7cd/-/ Prefix: /*a+b2-7/cd These are the inorder, postorder and preorder traversals of the tree respectively. or variable In this part you will implement calculating and outputting the value of the expression tree, given the values of the variables. 2 9 This is the definition of the function you are going to implement: b. Push this new tree into the stack. 5. If the character is an operator: a. Pop two trees (T, and T, respectively) out of the stack. b. Create a new expression tree with the operator at the root and trees T, and T, to its right and left respectively. c. Push this new tree into the stack. 6. Keep repeating from step 3 until the whole postfix expression is read. double calculateRecurse (shared_ptr currNode, vector variables) b 3 2 The infix notation is our conventional way to write expressions where the operator is placed between the operands. This necessitates addition of parenthesis to denote precedence. On the contrary, in postfix notation, the operator is placed after the operands; This is a function called on the root of the tree by double calculate(vector variables). calculateRecurse recursively calculates