1-Complete the constructor method that convert a given String that represents an
ID: 3573414 • Letter: 1
Question
1-Complete the constructor method that convert a given String that represents an
expression into a Binary Tree that is the parse tree for that expression
public CSC205_Project2_BinaryTree ( String theExpression )
2-For this code you must complete the code of the given method
Object evaluateExpression( );
Which is The method evaluateExpression
returns either an Integer object or a Boolean object, depending on the value of the overall
expression.
import bridges.base.BinTreeElement;
/** Class to represent a binary parse tree
* The leaves contain literal values, either integers or boolean "true" or "false"
* Each non-leaf node contains an operator
*
* @author PUT YOUR NAME HERE
*/
public class CSC205_Project2_BinaryTree {
/** define which characters are valid operators in an expression */
public static final String ALL_OPERATORS = "+-*/><&|";
/** The root of the binary tree */
public BinTreeElementroot;
/** Constructs an empty tree, with no nodes at all. */
public CSC205_Project2_BinaryTree() {
root = null;
}
/** Constructs a parse tree from the given String */
public CSC205_Project2_BinaryTree( String expr ) {
/** YOU MUST COMPLETE THE CODE FOR THIS CONSTRUCTOR METHOD */
// dummy place-holder code
root = new BinTreeElement();
root.setValue( "foobar" );
root.setLabel( "foobar" );
root.getVisualizer().setColor( new bridges.base.Color( 118, 146, 60 ) );
}
/** Constructs a new binary tree with the given data at the root node, leftTree
* as the left subtree and rightTree as the right subtree. */
public CSC205_Project2_BinaryTree (Object theValue,
CSC205_Project2_BinaryTree leftTree,
CSC205_Project2_BinaryTree rightTree) {
root = new BinTreeElement();
root.setValue( theValue );
root.setLabel( theValue.toString() );
root.getVisualizer().setColor( new bridges.base.Color( 118, 146, 60 ) );
if (leftTree != null)
root.setLeft( leftTree.root );
else
root.setLeft(null);
if (rightTree != null)
root.setRight( rightTree.root );
else
root.setRight(null);
}
/** Kick starter method
* @return the value of the expression represented by this parse tree */
public Object evaluateExpression() {
/** YOU MUST COMPLETE THE CODE FOR THIS METHOD */
return null; // dummy place-holder code to guarantee that the code compiles
}
/** Return the data field of the root
* @return the data field of the root, or null if the root is null
*/
public Object getRootData() {
if (root != null)
return root.getValue();
else
return null;
}
}
Import Class :
import bridges.connect.Bridges;
public class Driver
{
public static void main ( String[] args )
{
System.out.println ( "Hello world, from CSC 205 Project 2 on Binary Parse Trees");
Bridges<String, Object> bridges = new Bridges<String, Object>(2, "PUT YOU APIKEY HERE", "PUT YOUR ID HERE");
bridges.setTitle("CSC 205 Project 2 - PUT YOUR NAME HERE");
CSC205_Project2_BinaryTree myTree = new CSC205_Project2_BinaryTree();
/** Construct and then display visually a parse tree with 9 node */
myTree = buildNineNodeTree();
displayTheDataStructure(bridges, myTree);
/** Construct and then display visually a parse tree for the given in-fix expression */
myTree = new CSC205_Project2_BinaryTree ("(83+((9+523)+73))");
displayTheDataStructure(bridges, myTree);
/** Construct and then display visually a parse tree for the given in-fix expression */
myTree = new CSC205_Project2_BinaryTree ("((32<(98+6))|(18>93))");
displayTheDataStructure(bridges, myTree);
/** Test the BinaryTree methods on a variety of test data.
* These test cases will be automatically checked for correctness */
boolean success = passedAllTestCases(bridges);
if ( success )
System.out.println ( "Congratulations! Your code passed all the test cases");
}
/** Test the code on a variety of different expressions
*
* @param bridges - used to visualize the parse trees.
* @return true if all the test cases were successfully completed
*/
private static boolean passedAllTestCases(Bridges<String, Object> bridges)
{
CSC205_Project2_BinaryTree myTree;
int numErrors = 0; /** how many test cases failed? */
String expression = "";
try {
myTree = new CSC205_Project2_BinaryTree("true");
Object result = myTree.evaluateExpression();
if ( ! (result instanceof Boolean) || ! (result.equals(true)) )
throw new InvalidExpressionException( "Invalid return type (or value) on simple boolean literal value - true");
displayTheDataStructure(bridges, myTree);
} catch ( InvalidExpressionException woe ) {
System.out.println ( "Code failed on simple boolean literal value - true" );
numErrors++;
}
try {
myTree = new CSC205_Project2_BinaryTree("false");
Object result = myTree.evaluateExpression();
if ( ! (result instanceof Boolean) || ! (result.equals(false)) )
throw new InvalidExpressionException("Invalid return type (or value) on simple boolean literal value - false");
displayTheDataStructure(bridges, myTree);
} catch ( InvalidExpressionException woe ) {
System.out.println ( "Code failed on simple boolean literal value - false" );
numErrors++;
}
try {
myTree = new CSC205_Project2_BinaryTree("42");
Object result = myTree.evaluateExpression();
if ( ! (result instanceof Integer) || ! (result.equals(42)) )
throw new InvalidExpressionException("Invalid return type (or value) on simple integer literal value");
displayTheDataStructure(bridges, myTree);
} catch ( InvalidExpressionException woe ) {
System.out.println ( "Code failed on simple integer literal value" );
numErrors++;
}
try {
myTree = new CSC205_Project2_BinaryTree ("ab2c7d3e");
System.out.println ( "Code should have failed on invalid literal value, but did not" );
numErrors++; // an Exception should have been thrown
} catch ( InvalidExpressionException woe ) {
; // an InvalidParseTreeException should have been thrown
} catch ( RuntimeException trouble ) {
System.out.println ( "Code should have thrown InvalidParseTreeException for invalid literal value, but did not" );
numErrors++;
}
try {
myTree = new CSC205_Project2_BinaryTree ("(10+20)");
Object result = myTree.evaluateExpression();
if ( ! (result instanceof Integer) || ! (result.equals(30)) )
throw new InvalidExpressionException("Invalid return type (or value) on valid data (10+20)");
displayTheDataStructure(bridges, myTree);
} catch ( InvalidExpressionException woe ) {
System.out.println ( "Code failed on valid data (10+20)" );
numErrors++;
}
try {
myTree = new CSC205_Project2_BinaryTree ("10+20)");
System.out.println ( "Code should have failed on unbalanced parentheses, but did not" );
numErrors++; // an Exception should have been thrown
} catch ( InvalidExpressionException woe ) {
; // an InvalidParseTreeException should have been thrown
} catch ( RuntimeException trouble ) {
System.out.println ( "Code should have thrown InvalidParseTreeException for unbalanced parentheses, but did not" );
numErrors++;
}
try {
myTree = new CSC205_Project2_BinaryTree ("(10+20");
System.out.println ( "Code should have failed on unbalanced parentheses, but did not" );
numErrors++; // an Exception should have been thrown
} catch ( InvalidExpressionException woe ) {
; // an InvalidParseTreeException should have been thrown
} catch ( RuntimeException trouble ) {
System.out.println ( "Code should have thrown InvalidParseTreeException for unbalanced parentheses, but did not" );
numErrors++;
}
try {
myTree = new CSC205_Project2_BinaryTree("10+20");
System.out.println ( "Code should have failed due to lack of parentheses, but did not" );
numErrors++; // an Exception should have been thrown
} catch ( InvalidExpressionException woe ) {
; // an InvalidParseTreeException should have been thrown
} catch ( RuntimeException trouble ) {
System.out.println ( "Code should have thrown InvalidParseTreeException for lack of parentheses, but did not" );
numErrors++;
}
try {
expression = "(14+true)";
myTree = new CSC205_Project2_BinaryTree(expression);
myTree.evaluateExpression();
System.out.println ( "Code should have failed due to mismatched types in " +
expression + ", but did not" );
numErrors++; // an Exception should have been thrown
} catch ( InvalidExpressionException woe ) {
; // an InvalidParseTreeException should have been thrown
} catch ( RuntimeException trouble ) {
System.out.println ( "Code should have thrown InvalidParseTreeException due to mismatched types in"
+ expression + ", but did not" );
numErrors++;
}
try {
expression = "(14&true)";
myTree = new CSC205_Project2_BinaryTree(expression);
myTree.evaluateExpression();
System.out.println ( "Code should have failed due to mismatched types in " +
expression + ", but did not" );
numErrors++; // an Exception should have been thrown
} catch ( InvalidExpressionException woe ) {
; // an InvalidParseTreeException should have been thrown
} catch ( RuntimeException trouble ) {
System.out.println ( "Code should have thrown InvalidParseTreeException due to mismatched types in"
+ expression + ", but did not" );
numErrors++;
}
try {
myTree = new CSC205_Project2_BinaryTree ("(83+((9+523)+73))");
Object result = myTree.evaluateExpression();
if ( ! (result instanceof Integer) || ! (result.equals(688)) )
throw new InvalidExpressionException("Invalid return type (or value) on valid data (83+((9+523)+73))");
displayTheDataStructure(bridges, myTree);
} catch ( InvalidExpressionException woe ) {
System.out.println ( "Code failed on valid data (83+((9+523)+73))" );
numErrors++;
}
try {
myTree = new CSC205_Project2_BinaryTree ("(112<234)");
Object result = myTree.evaluateExpression();
if ( ! (result instanceof Boolean) || ! (result.equals(true)) )
throw new InvalidExpressionException("Invalid return type (or value) on valid data (112<234)");
displayTheDataStructure(bridges, myTree);
} catch ( InvalidExpressionException woe ) {
System.out.println ( "Code failed on valid data (112<234)" );
numErrors++;
}
try {
myTree = new CSC205_Project2_BinaryTree ("(83+((72-41)+(18-5)))");
Object result = myTree.evaluateExpression();
if ( ! (result instanceof Integer) || ! (result.equals(127)) )
throw new InvalidExpressionException("Invalid return type (or value) on valid data (83+((72-41)+(18-5)))");
displayTheDataStructure(bridges, myTree);
} catch ( InvalidExpressionException woe ) {
System.out.println ( "Code failed on valid data (83+((72-41)+(18-5)))" );
numErrors++;
}
try {
myTree = new CSC205_Project2_BinaryTree ("(((1+2)+(3+4))+5)");
Object result = myTree.evaluateExpression();
if ( ! (result instanceof Integer) || ! (result.equals(15)) )
throw new InvalidExpressionException("Invalid return type (or value) on valid data (((1+2)+(3+4))+5)");
displayTheDataStructure(bridges, myTree);
} catch ( InvalidExpressionException woe ) {
System.out.println ( "Code failed on valid data (((1+2)+(3+4))+5)" );
numErrors++;
}
try {
myTree = new CSC205_Project2_BinaryTree ("(5+(4+(3+(2+1))))");
Object result = myTree.evaluateExpression();
if ( ! (result instanceof Integer) || ! (result.equals(15)) )
throw new InvalidExpressionException("Invalid return type (or value) on valid data (5+(4+(3+(2+1))))");
displayTheDataStructure(bridges, myTree);
} catch ( InvalidExpressionException woe ) {
System.out.println ( "Code failed on valid data (5+(4+(3+(2+1))))" );
numErrors++;
}
try {
myTree = new CSC205_Project2_BinaryTree ("(true|true)");
Object result = myTree.evaluateExpression();
if ( ! (result instanceof Boolean) || ! (result.equals(true)) )
throw new InvalidExpressionException("Invalid return type (or value) on valid data (true|true)");
displayTheDataStructure(bridges, myTree);
} catch ( InvalidExpressionException woe ) {
System.out.println ( "Code failed on valid data (true|true)" );
numErrors++;
}
try {
myTree = new CSC205_Project2_BinaryTree ("(false|true)");
Object result = myTree.evaluateExpression();
if ( ! (result instanceof Boolean) || ! (result.equals(true)) )
throw new InvalidExpressionException("Invalid return type (or value) on valid data (false|true)");
displayTheDataStructure(bridges, myTree);
} catch ( InvalidExpressionException woe ) {
System.out.println ( "Code failed on valid data (false|true)" );
numErrors++;
}
try {
myTree = new CSC205_Project2_BinaryTree ("(false&true)");
Object result = myTree.evaluateExpression();
if ( ! (result instanceof Boolean) || ! (result.equals(false)) )
throw new InvalidExpressionException("Invalid return type (or value) on valid data (false&true)");
displayTheDataStructure(bridges, myTree);
} catch ( InvalidExpressionException woe ) {
System.out.println ( "Code failed on valid data (false&true)" );
numErrors++;
}
try {
myTree = new CSC205_Project2_BinaryTree ("(true&true)");
Object result = myTree.evaluateExpression();
if ( ! (result instanceof Boolean) || ! (result.equals(true)) )
throw new InvalidExpressionException("Invalid return type (or value) on valid data (true&true)");
displayTheDataStructure(bridges, myTree);
} catch ( InvalidExpressionException woe ) {
System.out.println ( "Code failed on valid data (true&true)" );
numErrors++;
}
try {
expression = "((32<(98+6))|(18>93))";
myTree = new CSC205_Project2_BinaryTree (expression);
Object result = myTree.evaluateExpression();
if ( ! (result instanceof Boolean) || ! (result.equals(true)) )
throw new InvalidExpressionException("Invalid return type (or value) on valid data: " + expression);
displayTheDataStructure(bridges, myTree);
} catch ( InvalidExpressionException woe ) {
System.out.println ( "Code failed on valid data: " + expression );
numErrors++;
}
try {
expression = "(true|(((4+3)<14)&(245>692)))";
myTree = new CSC205_Project2_BinaryTree (expression);
Object result = myTree.evaluateExpression();
if ( ! (result instanceof Boolean) || ! (result.equals(true)) )
throw new InvalidExpressionException("Invalid return type (or value) on valid data: " + expression);
displayTheDataStructure(bridges, myTree);
} catch ( InvalidExpressionException woe ) {
System.out.println ( "Code failed on valid data: " + expression );
numErrors++;
}
try {
expression = "(true|(((4+3<14)&(245>692)))";
myTree = new CSC205_Project2_BinaryTree (expression);
System.out.println ( "Code should have failed on invalid " + expression + ", but did not" );
numErrors++;
} catch ( InvalidExpressionException woe ) {
; // an InvalidParseTreeException should have been thrown
} catch ( RuntimeException woe ) {
System.out.println ( "Code should have thrown InvalidParseTreeException on invalid expression " +
expression + ", but did not" );
numErrors++;
}
try {
expression = "(false&(((3+28)<53)|(18>(29*4))))";
myTree = new CSC205_Project2_BinaryTree (expression);
Object result = myTree.evaluateExpression();
if ( ! (result instanceof Boolean) || ! (result.equals(false)) )
throw new InvalidExpressionException("Invalid return type (or value) on valid data: " + expression);
displayTheDataStructure(bridges, myTree);
} catch ( InvalidExpressionException woe ) {
System.out.println ( "Code failed on valid data: " + expression );
numErrors++;
}
/** the code was successful if there were no errors */
if ( numErrors == 0 )
return true;
else
return false;
}
/** generate a URL to see a visualization of the tree */
private static void displayTheDataStructure(
Bridges<String, Object> bridges, CSC205_Project2_BinaryTree myTree) {
bridges.setDataStructure(myTree.root);
bridges.visualize();
}
private static CSC205_Project2_BinaryTree buildNineNodeTree( ) {
CSC205_Project2_BinaryTree aLeaf = new CSC205_Project2_BinaryTree ( "19", null, null );
CSC205_Project2_BinaryTree bLeaf = new CSC205_Project2_BinaryTree ( "7", null, null );
CSC205_Project2_BinaryTree cLeaf = new CSC205_Project2_BinaryTree ( "11", null, null );
CSC205_Project2_BinaryTree dLeaf = new CSC205_Project2_BinaryTree ( "18", null, null );
CSC205_Project2_BinaryTree eLeaf = new CSC205_Project2_BinaryTree ( "14", null, null );
CSC205_Project2_BinaryTree multTree = new CSC205_Project2_BinaryTree ( "*", bLeaf, cLeaf );
CSC205_Project2_BinaryTree plusTree = new CSC205_Project2_BinaryTree ( "+", aLeaf, multTree );
CSC205_Project2_BinaryTree subTree = new CSC205_Project2_BinaryTree ( "-", dLeaf, eLeaf );
CSC205_Project2_BinaryTree divTree = new CSC205_Project2_BinaryTree ( "/", plusTree, subTree );
return( divTree );
}
}
Explanation / Answer
/* As per my understanding you need to rewrite the code with*/
/** Represents a arithmetic expression. */ public interface Expression { /** Converts to a string in prefix notation. * This can be accomplished by a preorder traversal of the tree. */ public String prefix(); /** Converts to a string in infix notation. */ public String infix(); /** Converts to a string in postfix notation. */ public String postfix(); /** Finds the value of the expression. */ public double value(); } public class InvalidExpressionException extends Exception { public InvalidExpressionException(String err) { super(err); // just call the general Exception constructor } } Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.