1-Complete the constructor method that convert a given String that represents an
ID: 3577229 • 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
The use of the function here is to implement the code for the evaluation of the expression in the binary tree. The expression can be evaluated starting from the root node of the tree and doing the traverse of the tree by performing the equivalent mathematical operations during the traversal.
working function code will be:
public Object evaluateExpression() {
if (root.Left == null && root.Right == null)
return toDigit(root.data);
else
{
double result = 0.0;
double Left = evaluate(root.Left);
double Right = evaluate(root.Right);
char operator = root.data;
switch (operator)
{
case '+' : result = Left + Right; break;
case '-' : result = Left - Right; break;
case '*' : result = Left * Right; break;
case '/' : result = Left / Right; break;
default : result = Left + Right; break;
}
return result;
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.