For this project, you are going to build a converter to transform a numeric expression from...

    

Transcribed Image Text:

For this project, you are going to build a converter to transform a numeric expression from infix notation into a binary expression tree, then build a tree evaluator to evaluate it. For example, if the infix is: 7.8 (2.3 +2.5) The corresponding binary expression tree will be: 7.8 2.3 + 2.5 As you will see, there are quite some similarities between this project and the one we did in HW 6. Although we are using different data structures, as well as algorithms to achieve similar end results. a. Download the attached "Converter.java", "Evaluator.java", "Tokenizer.java", "TreeEvaluator.java", "TreeNode.java". You may also download the sample data file "expressions.txt", or you may use your own input data file. b. First,take a look at the "Tokenizer.java". It is exactly the same as HW 6 and is already written for you (DO NOT MODIFY IT). Its purpose is to read valid tokens one by one from the input string. A token can be either a number, an operator, or parenthesis. Its main interface consists two methods: Boolean hasNext Token() which returns true if there are still tokens remaining, false otherwise. String nextToken () which returns the next token when there are still tokens remaining. In a way, it is very similar to Scanner, which you should be fairly familiar with as of now. You can take a look at its implementation, which uses a queue. c. Now look at the "Converter.java". Its constructor takes in the infix expression. You can assume the input expression is valid. The sample "convert to postfix" implementation, as required in HW 6, is provided as a reference. You can study it a bit - this can be useful when you implement the "build binary expression tree" part, below. The corresponding sample of postfix expression evaluation as required in HW6 is also provided in "Evaluator. java". It is not really needed for this project, so feel free to skip it. d. Take a look at "TreeNode.java". This represents a node in the expression tree. It has a data field (which contains either an operator or a number), a left child, and a right child. A number node must be a leaf node - meaning both children will be null. All the code in this class is already written for you. Please study a bit for its public interface. e. Take a look at "TreeEvaluator.java". Its constructor takes in the root of an expression tree. A large part of it is implemented for you already, especially the print () method - it will print the tree in "vertical format", which will be handy for you to inspect the tree. f. Now go back to "Converter.java", and implement the method: public TreeNode getExpressionTree () It should read the tokens in the infix expression and build a binary expression tree from it, then return the root of the tree. The algorithm is quite similar to the "convert to postfix" one, with some small modifications. You need two stacks, one for the operators (the + */), one for the expressions. Read the tokens one by one from the infix expression; when you see a number, construct a "number" node (i.e. leaf node), and push into the expression stack; when you see an operator (+ -*/), push it into the operator stack; when you see a right parenthesis, you can get the operator by popping the operator stack, and get the two operands by popping from the expression stack, then construct a "operator" node and push it back into the expression stack. In the end, when you run out of tokens, there can be two cases. In one case, the operator stack is empty: now the only one node in the expression stack should be the root of the result expression tree. In the other case, there will be one operator and two expressions left: now you can just construct the final expression node with those and return it. g. Now go back to "TreeEvaluator.java", and implement the method: private double evaluateHelper (TreeNode node) This should be fairly straightforward to implement using recursion. If the node is a number, just return the number as the result. Otherwise, evaluate the left child and right child, then perform the arithmetic operation (+*/) and return the result. h. For this assignment you are limited to language features in Chapter 1-17 of the textbook. Also remember DO NOT change any method signature! For this project, you are going to build a converter to transform a numeric expression from infix notation into a binary expression tree, then build a tree evaluator to evaluate it. For example, if the infix is: 7.8 (2.3 +2.5) The corresponding binary expression tree will be: 7.8 2.3 + 2.5 As you will see, there are quite some similarities between this project and the one we did in HW 6. Although we are using different data structures, as well as algorithms to achieve similar end results. a. Download the attached "Converter.java", "Evaluator.java", "Tokenizer.java", "TreeEvaluator.java", "TreeNode.java". You may also download the sample data file "expressions.txt", or you may use your own input data file. b. First,take a look at the "Tokenizer.java". It is exactly the same as HW 6 and is already written for you (DO NOT MODIFY IT). Its purpose is to read valid tokens one by one from the input string. A token can be either a number, an operator, or parenthesis. Its main interface consists two methods: Boolean hasNext Token() which returns true if there are still tokens remaining, false otherwise. String nextToken () which returns the next token when there are still tokens remaining. In a way, it is very similar to Scanner, which you should be fairly familiar with as of now. You can take a look at its implementation, which uses a queue. c. Now look at the "Converter.java". Its constructor takes in the infix expression. You can assume the input expression is valid. The sample "convert to postfix" implementation, as required in HW 6, is provided as a reference. You can study it a bit - this can be useful when you implement the "build binary expression tree" part, below. The corresponding sample of postfix expression evaluation as required in HW6 is also provided in "Evaluator. java". It is not really needed for this project, so feel free to skip it. d. Take a look at "TreeNode.java". This represents a node in the expression tree. It has a data field (which contains either an operator or a number), a left child, and a right child. A number node must be a leaf node - meaning both children will be null. All the code in this class is already written for you. Please study a bit for its public interface. e. Take a look at "TreeEvaluator.java". Its constructor takes in the root of an expression tree. A large part of it is implemented for you already, especially the print () method - it will print the tree in "vertical format", which will be handy for you to inspect the tree. f. Now go back to "Converter.java", and implement the method: public TreeNode getExpressionTree () It should read the tokens in the infix expression and build a binary expression tree from it, then return the root of the tree. The algorithm is quite similar to the "convert to postfix" one, with some small modifications. You need two stacks, one for the operators (the + */), one for the expressions. Read the tokens one by one from the infix expression; when you see a number, construct a "number" node (i.e. leaf node), and push into the expression stack; when you see an operator (+ -*/), push it into the operator stack; when you see a right parenthesis, you can get the operator by popping the operator stack, and get the two operands by popping from the expression stack, then construct a "operator" node and push it back into the expression stack. In the end, when you run out of tokens, there can be two cases. In one case, the operator stack is empty: now the only one node in the expression stack should be the root of the result expression tree. In the other case, there will be one operator and two expressions left: now you can just construct the final expression node with those and return it. g. Now go back to "TreeEvaluator.java", and implement the method: private double evaluateHelper (TreeNode node) This should be fairly straightforward to implement using recursion. If the node is a number, just return the number as the result. Otherwise, evaluate the left child and right child, then perform the arithmetic operation (+*/) and return the result. h. For this assignment you are limited to language features in Chapter 1-17 of the textbook. Also remember DO NOT change any method signature!

Answer rating: 100% (QA)

SOLUTION import javaio import javautil public class Converter public static void mainString args thr... View the full answer