Part II- Once your environment is set up to use the TreeNode class, let\'s turn
ID: 3692967 • Letter: P
Question
Part II- Once your environment is set up to use the TreeNode class, let's turn our attention to how we build expression trees in the first place. You will be writing code to build an expression from a String. In the ExpressionTree.java class, create the following method header:
public static TreeNode buildTreeFromString(String expr)
This method will take an expression written in postfix notation (as described above) as a String and return back the root node of an expression tree built from that String. How will it go about doing this? The algorithm for building an expression tree from a String is a non-recursive algorithm that uses a Stack to direct the building of a tree: Turn the String into an array of operands and operators Start with an empty Stack of TreeNodes named exprStack For each element of that array, moving from left to right: If the element is an operator: Create a new TreeNode containing that operator Pop the first element off exprStack, make it the right child of the new TreeNode Pop the next element off exprStack, make it the left child of the new TreeNode Push the new TreeNode you just built onto the exprStack Otherwise (if the element is an operand): Create a new TreeNode containing that operand Push the new TreeNode onto the exprStack Once the entire expression has been parsed, there should be ONLY one item in the exprStack. That item will be the root of the new expression tree, and should be popped off and returned by the method. Your implementation should return a null under the following circumstances: If the final exprStack contains more than one TreeNode, return null. This indicates that the expression was not properly formatted in postfix notation If during the process of building an operator node, the stack does not have at least two elements in it to pop off and make children of the operator node, return null. This also indicates that the expression was not properly formatted in postfix notation. You need to handle this error because otherwise your method will crash when it goes to pop a nonexistant item off the Stack. Remember that you can turn a String into an array of Strings by using the split() method. The following line of code will split up a String based on "whitespace" between operators and operands: String[] exprArr = expr.split("\s+"); Your method can assume that input Strings will always be formatted with spaces between each element. For example the following expression is properly formatted for this method: "5 10 15 - * 7 +" And should result in a correct expression tree. While this expression is not properly formatted and therfore your method is not required to handle it: "5 10 15-*7+" You should use JUnit to test your method. Come up with a number of different test cases to run against your method, and remember that the toString() method of the TreeNode class returns a String where the nodes are visited inorder. So the expression: "5 10 15 - * 7 +" Should provide an output like this when the root node of the expression tree is printed: "5 * 10 - 15 + 7" Note that this is NOT the proper conversion of this expression to an inorder representation because no parentheses are added. We will deal with this shortcoming in Part III. Write up the test plan you come up with for your method in a text file named buildTreeFromStringTests.txt and include it with your final submission. Your test plan must test expressions up to at least 5 operands in length (i.e. up to five different numbers in the expression).
Part III - Displaying Expressions Once Part II is finished, you will need to use it to build expression trees to use to test your results for Part III. You will need to write a method named toPostfixString() that has the following signature: public static String toPostfixString(TreeNode expr) This method takes the root node of an expression tree and generates a String holding the expression represented by that tree in postfix notation. In other words, given an expression tree, this method should give you back the expression you built that tree from in the first place. This method will be a recursive method, and build the expression using an post-order traversal of the tree. The algorithm for a post-order traversal of a tree is: Get the postorder representation of the left child (if it is not null) Append to that the postorder representation of the right child (if it is not null) Append to that the value of the element at the root node Again, you must build JUnit tests to test this code. This should be fairly easy, because the result of a call to the method should be exactly like the String you used to build the expression tree in the first place. Create a text file named toPostfixStringTests.txt that contains your test plan for this method and include it with your final submission. Again, your test plan must account for expressions with up to 5 different operands in them. After getting toPostfixString() working, write a method with the following signature: public static String toInfixString(TreeNode expr) This method should display expression trees in infix notation. This means that the method needs to properly handle the placement of parentheses. You need to follow the algorithm for an in-order traversal, but also place parentheses appropriately to get the right expression out. The algorithm for an in-order traversal is: Get the inorder representation of the left child (if it is not null) Append to that the value of the element at the root node Append to that the inorder representation of the right child (if it is not null) Parentheses should go around the above if the element at the root node is an operator. Otherwise there should be no parentheses. Again, you must build JUnit tests to test this code. Create a text file named toInfixStringTests.txt that contains your test plan for this method and include it with your final submission. Again, your test plan must account for expressions with up to 5 different operands in them. Finally, just to complete our set of expression display methods, you will need to write a method with the following signature: public static String toPrefixString(TreeNode expr) This method takes the root node of an expression tree and generates a String holding the expression represented by that tree in prefix notation. Prefix notation is similar to postfix notation, except that operators come before their operands. For example, the following expression in postfix notation: 5 10 15 - * 7 + Would be written in prefix notation as: + * 5 - 10 15 7 This method will be a recursive method, and build the expression using an post-order traversal of the tree. The algorithm for a post-order traversal of a tree is: Start with the value of the element at the root node Append to that the preorder representation of the left child (if it is not null) Append to that the preorder representation of the right child (if it is not null) As with the above methods, you must build JUnit tests to test this code. Create a text file named toPrefixStringTests.txt that contains your test plan for this method and include it with your final submission. Again, your test plan must account for expressions with up to 5 different operands in them. Part IV - Evaluating Expressions Once part III is finished, you will need to write the method that is the "meat" of this project - the expression tree evaluation method. Use the following method signature: public static int evaluate(TreeNode expr) This method should evaluate the expression stored in your expression tree. This is a recursive method that uses the following algorithm: If the element at the current node is an operator: Evaluate the left child Evaluate the right child Perform the operation given by the element at the current node ( left op right) and return the result If the element at the current node is an operand: Return the integer value of the element at the current node. Remember - you can use the method Integer.parseInt() to convert a String containing an numeric value into an int. Build JUnit tests to test this code. Create a text file named toPrefixStringTests.txt that contains your test plan for this method and include it with your final submission. Again, your test plan must account for expressions with up to 5 different operands in them. Part V - Putting it all together Once you have all of the above parts finished, you should be able to use the ExpressionTree library you created to build a calculator program. This will be an interactive program that allows a user to enter expressions in postfix notation, see them displayed using the notation of their choice, and then see the result. You will write this program as Project06.java. This program should: Prompt the user with a menu, giving them the choice of setting the output format, entering a new expression, or exiting the program. If they choose to set the ouput format, it should prompt them to have the output displayed in prefix, infix, or postfix notation. It should require that they enter one of these choices and continue prompting until they enter a valid choice. Then it should return to the main menu. If they choose to enter a new expression, the program should prompt them to enter a new expression in postfix notation. If the expression that they entered is not a valid postfix expression, the program should print an error message that the format was incorrect and return to the main menu. If the expression that they entered was valid, the program should display the expression using the output format they have currently set (with a default of postfix notation if they haven't chosen anything) and display the result as well. It should then return them to the main program. If the user chooses to exit the program, the program should display a goodbye message and then end.
Explanation / Answer
import java.lang.*;
import java.util.*;
import java.io.*;
class Infixconv
{
public static String rdstrng()
{
try
{
InputStreamReader ipt = new InputStreamReader(System.in);
BufferedReader rdr = new BufferedReader(ipt);
return rdr.readLine();
}
catch (Exception e)
{
e.printStackTrace();
return "";
}
}
public static int rdIntgr()
{
try
{
InputStreamReader ipt = new InputStreamReader(System.in);
BufferedReader rdr = new BufferedReader(ipt);
return Integer.parseInt(rdr.readLine());
}
catch (Exception e)
{
e.printStackTrace();
return 0;
}
}
//Method to convert infix to postfix
public static String InfixToPostfixConvert(String infixBuffer)
{
int priority = 0;
String postfixBuffer = "";
Stack s1 = new Stack();
for (int i = 0; i < infixBuffer.length(); i++)
{
char ch = infixBuffer.charAt(i);
if (ch == '+' || ch == '-' || ch == '*' || ch == '/')
{
// check the precedence
if (s1.size() <= 0)
s1.push(ch);
else
{
Character chTop = (Character) s1.peek();
if (chTop == '*' || chTop == '/')
priority = 1;
else
priority = 0;
if (priority == 1)
{
if (ch == '+' || ch == '-')
{
postfixBuffer += s1.pop();
i--;
}
else
{ // Same
postfixBuffer += s1.pop();
i--;
}
}
else
{
if (ch == '+' || ch == '-')
{
postfixBuffer += s1.pop();
s1.push(ch);
}
else
s1.push(ch);
}
}
}
else
{
postfixBuffer += ch;
}
}
int len = s1.size();
for (int j = 0; j < len; j++)
postfixBuffer += s1.pop();
return postfixBuffer;
}
public static void main(String[] args)
{
String infixBuffer = "";
String postfixBuffer = "";
if(args.length == 1)
{
infixBuffer = args[0];
postfixBuffer = InfixToPostfixConvert(infixBuffer);
//printing infixbuffer
System.out.println( infixBuffer);
//Printing potfixbuffer
System.out.println( postfixBuffer);
}
else
{
infixBuffer = "a+b*c/d-e";
postfixBuffer = InfixToPostfixConvert(infixBuffer);
//printing infixbuffer
System.out.println(infixBuffer);
//Printing potfixbuffer
System.out.println(postfixBuffer);
System.out.println();
}
}
}