Homework SourseSIMPLE LOGIC PROBLEM Below is a complete program for impleme
SIMPLE LOGIC PROBLEM Below is a complete program for implementing a binary expression tree. My code works, but it is suppossed to be able to create an expression from variables, double, or operators +,-,*, and /. It currently works for variables, but there is some error in my logic that gives errors when trying to evaluate expressions with doubles. Please find the bug. Here is my source code:
ExpressionTree.java
//
import java.util.HashMap;
import java.util.Iterator;
import java.util.Stack;
public class ExpressionTree extends BinaryTree<String> implements ExpressionTreeInterface<String>{
private HashMap<String, Variable> variables;
private String[] postfix;
public ExpressionTree(String[] args) {
variables = new HashMap<String, Variable>();
postfix = args;
}
public double evaluate() {
return evaluate(postfixToExpressionTree(postfix).getRootNode());
}
public void setVariable(String str, double d){
variables.put(str, new Variable(str, d));
}
private double evaluate(BinaryNode<String> rootNode) {
double result;
if(rootNode == null) {
result = 0;
}else if(rootNode.isLeaf()) {
String root = rootNode.getData();
if(isVariable(root))
result = variables.get(root).getValue();
else
result = Double.parseDouble(root);
}else {
double firstOp = evaluate(rootNode.getLeftChild());
double secondOp = evaluate(rootNode.getRightChild());
String operator = rootNode.getData();
result = compute(operator, firstOp, secondOp);
}
return result;
}
private double compute(String operator, double first, double second){
switch(operator) {
case \"+\":
return first + second;
case \"-\":
return first - second;
case \"*\":
return first * second;
case \"/\":
if (second == 0)
throw new ArithmeticException(\"Cannot divide by zero\");
return first / second;
}
return 0;
}
private BinaryTree<String> postfixToExpressionTree(String[] postfix){
Stack<BinaryTree<String>> stack = new Stack<BinaryTree<String>>();
for(String token : postfix) {
if(isVariable(token) || isDouble(token)) {
stack.push(new BinaryTree<String>(token));
continue;
}else if(!isOperator(token) && !isVariable(token) && !isDouble(token)) {
throw new IllegalArgumentException(\"Variable must be defined.\");
}
else if(isOperator(token)) {
BinaryTree<String> right = stack.pop();
BinaryTree<String> left = stack.pop();
stack.push(new BinaryTree<String>(token, left, right));
}
}
return stack.pop();
}
private boolean isDouble(String str) {
try {
Double.parseDouble(str);
return true;
}catch(NumberFormatException e) {
return false;
}
}
private boolean isVariable(String str) {
return variables.containsKey(str);
}
private boolean isOperator(String str) {
switch(str) {
case \"+\": case \"-\": case \"*\": case \"/\":
return true;
}
return false;
}
public void displayPostfix() {
String post = \"\";
Iterator<String> it = postfixToExpressionTree(postfix).getPostorderIterator();
while(it.hasNext()) {
post += it.next();
if(it.hasNext()) {
post += \" \";
}
}
System.out.println(post);
}
}
ExpressionTreeInterface.java
public interface ExpressionTreeInterface<T> extends BinaryTreeInterface<String> {
public double evaluate();
}
Variable.java
public class Variable {
private String name;
private double value;
public Variable(String name) {
this.name = name;
}
public Variable(String name, double value) {
this.name = name;
this.setValue(value);
}
public String getName() {
return name;
}
public void setName(String newName) {
this.name = newName;
}
public double getValue() {
return value;
}
public void setValue(double value) {
this.value = value;
}
}
BinaryNode.java
public class BinaryNode<T> {
private T data;
private BinaryNode<T> leftChild, rightChild;
public BinaryNode() {
this(null);
}
public BinaryNode(T data) {
this(data, null, null);
}
public BinaryNode(T data, BinaryNode<T> left, BinaryNode<T> right) {
this.data = data;
leftChild = left;
setRightChild(right);
}
public T getData() {
return data;
}
public void setData(T data) {
this.data = data;
}
public BinaryNode<T> getLeftChild(){
return leftChild;
}
public void setLeftChild(BinaryNode<T> left) {
leftChild = left;
}
public BinaryNode<T> getRightChild() {
return rightChild;
}
public void setRightChild(BinaryNode<T> right) {
this.rightChild = right;
}
public boolean hasLeftChild() {
return leftChild != null;
}
public boolean hasRightChild() {
return rightChild != null;
}
public boolean isLeaf() {
return (!hasLeftChild() && !hasRightChild());
}
public BinaryNode<T> copy(){
BinaryNode<T> newRoot = new BinaryNode<T>(data);
if(leftChild != null) {
newRoot.setLeftChild(leftChild.copy());
}
if(rightChild != null) {
newRoot.setRightChild(rightChild.copy());
}
return newRoot;
}
public int getHeight() {
return getHeight(this);
}
private int getHeight(BinaryNode<T> node) {
int height = 0;
if(node != null) {
height = 1 + Math.max(getHeight(node.getLeftChild()), getHeight(node.getRightChild()));
}
return height;
}
public int getNumberOfNodes() {
return getNumberOfNodes(this);
}
private int getNumberOfNodes(BinaryNode<T> node) {
int rightNumber = 0;
int leftNumber = 0;
if(leftChild != null) {
leftNumber = getNumberOfNodes(node.getLeftChild());
}
if(rightChild != null) {
rightNumber = getNumberOfNodes(node.getRightChild());
}
return 1 + leftNumber + rightNumber;
}
}
BinaryTree.java
import java.util.Iterator;
import java.util.Stack;
public class BinaryTree<T> implements BinaryTreeInterface<T> {
private BinaryNode<T> root;
public BinaryTree() {
root = null;
}
public BinaryTree(T rootData) {
root = new BinaryNode<T>(rootData);
}
public BinaryTree(T rootData, BinaryTree<T> leftTree, BinaryTree<T> rightTree) {
privateSetTree(rootData, leftTree, rightTree);
}
public void setTree(T rootData) {
root = new BinaryNode<T>(rootData);
}
public void setTree(T rootData, BinaryTree<T> left, BinaryTree<T> right) {
privateSetTree(rootData, left, right);
}
private void privateSetTree(T rootData, BinaryTree<T> left, BinaryTree<T> right) {
root = new BinaryNode<>(rootData);
if ((left != null) && (!left.isEmpty())) {
root.setLeftChild(left.root.copy());
}
if ((right != null) && (!right.isEmpty())) {
root.setRightChild(right.root.copy());
}
}
public T getRootData() {
return root.getData();
}
public int getHeight() {
return root.getHeight();
}
public int getNumberOfNodes() {
return root.getNumberOfNodes();
}
public boolean isEmpty() {
return root == null;
}
public void clear() {
root = null;
}
protected BinaryNode<T> getRootNode() {
return root;
}
public Iterator<T> getPreorderIterator() {
throw new UnsupportedOperationException(\"Preorder not supported.\");
}
public Iterator<T> getInorderIterator() {
throw new UnsupportedOperationException(\"Inorder not supported.\");
}
public Iterator<T> getPostorderIterator() {
return new PostorderIterator();
}
public Iterator<T> getLevelorderIterator() {
throw new UnsupportedOperationException(\"Level Order not supported.\");
}
private class PostorderIterator implements Iterator<T> {
private Stack<BinaryNode<T>> nodeStack;
private BinaryNode<T> current;
public PostorderIterator() {
nodeStack = new Stack<>();
current = root;
populateStack(current);
}
private void populateStack(BinaryNode<T> node){
nodeStack.add(node);
if(node.hasRightChild()){
populateStack(node.getRightChild());
}
if(node.hasLeftChild()){
populateStack(node.getLeftChild());
}
}
public boolean hasNext() {
return !nodeStack.isEmpty();
}
public T next() {
return nodeStack.pop().getData();
}
}
}
BinaryTreeInterface.java
public interface BinaryTreeInterface<T> extends TreeInterface<T>, TreeIteratorInterface<T>{
public void setTree(T rootData);
public void setTree(T rootData, BinaryTree<T> left, BinaryTree<T> right);
}
TreeIteratorInterface.java
import java.util.Iterator;
public interface TreeIteratorInterface<T> {
public Iterator<T> getPreorderIterator();
public Iterator<T> getInorderIterator();
public Iterator<T> getPostorderIterator();
public Iterator<T> getLevelorderIterator();
}
TreeInterface.java
public interface TreeInterface<T> {
public T getRootData();
public int getHeight();
public int getNumberOfNodes();
public boolean isEmpty();
public void clear();
}
ExpressionTest.java
package TreePackage;
import java.util.InputMismatchException;
import java.util.Scanner;
public class ExpressionTest {
public static boolean isDouble(String value) {
try {
Double.parseDouble(value);
return true;
} catch (NumberFormatException e) {
return false;
}
}
public static void main(String[] args) {
Scanner kb = new Scanner(System.in);
boolean hasExpression = false;
boolean quit = false;
String userInput = null;
ExpressionTree exp = new ExpressionTree(new String[]{\"a\", \"b\", \"2\", \"/\",\"+\"});
while(!quit){
System.out.print(\"\ \ J. Botkin\'s Expression Tree \ \ \");
if(hasExpression){
System.out.println(\"Current Expression: \" + userInput
+ \"\");
}
System.out.println(\"\ 1. Enter New Expression \ \"
+ \"2. Set Expression Variable \ \"
+ \"3. Evaluate Expression \ \"
+ \"4. Display Postfix \ \"
+ \"5. Quit\");
try{
int option = kb.nextInt();
switch (option) {
case 1:
System.out.println(\"Enter Expression seperated by spaces.\");
Scanner b = new Scanner(System.in);
userInput = b.nextLine();
String[] userExp = userInput.split(\" \");
switch (userExp.length){
case 1:
exp = new ExpressionTree(new String[]{userExp[0]});
break;
case 2:
exp = new ExpressionTree(new String[]{userExp[0], userExp[1]});
break;
case 3:
exp = new ExpressionTree(new String[]{userExp[0], userExp[1], userExp[2]});
break;
case 4:
exp = new ExpressionTree(new String[]{userExp[0], userExp[1], userExp[2], userExp[3]});
break;
case 5:
exp = new ExpressionTree(new String[]{userExp[0], userExp[1], userExp[2], userExp[3],userExp[4]});
break;
case 6:
exp = new ExpressionTree(new String[]{userExp[0], userExp[1], userExp[2], userExp[3],userExp[4], userExp[5]});
break;
case 7:
exp = new ExpressionTree(new String[]{userExp[0], userExp[1], userExp[2], userExp[3],userExp[4], userExp[5],userExp[6]});
break;
case 8:
exp = new ExpressionTree(new String[]{userExp[0], userExp[1], userExp[2], userExp[3],userExp[4], userExp[5],userExp[6], userExp[7]});
break;
case 9:
exp = new ExpressionTree(new String[]{userExp[0], userExp[1], userExp[2], userExp[3],userExp[4], userExp[5],userExp[6], userExp[7], userExp[8]});
break;
}
/*for(int i = 0; i < userExp.length; i++){
if(isDouble(userExp[i])){
exp.setVariable(userExp[i], Double.parseDouble(userExp[i]));
}
}
hasExpression = true;*/
break;
case 2:
Scanner k = new Scanner(System.in);
System.out.print(\"Variable name: \");
String name = k.nextLine();
System.out.print(\"Variable value: \");
double value = k.nextDouble();
exp.setVariable(name, value);
break;
case 3:
try{
System.out.println(exp.evaluate());
}
catch (IllegalArgumentException e){
System.out.println(\"Please define all variables.\");
}
break;
case 4:
try{
exp.displayPostfix();
}catch(IllegalArgumentException e){
System.out.println(\"Please define all variables.\");
}
break;
case 5:
quit = true;
break;
default:
System.out.println(\"Enter Correct option.\");
break;
}}catch(InputMismatchException e){
System.out.println(\"Enter Correct option.\");
main(args);
}
}
}
}
Solution
code was working ... output attached
public interface TreeInterface<T> {
public T getRootData();
public int getHeight();
public int getNumberOfNodes();
public boolean isEmpty();
public void clear();
}
-----------------------------------------------------------------------------------------------------------------------------------------------
import java.util.Iterator;
public interface TreeIteratorInterface<T> {
public Iterator<T> getPreorderIterator();
public Iterator<T> getInorderIterator();
public Iterator<T> getPostorderIterator();
public Iterator<T> getLevelorderIterator();
}
-----------------------------------------------------------------------------------------------------------------------------------------
public interface BinaryTreeInterface<T> extends TreeInterface<T>, TreeIteratorInterface<T>{
public void setTree(T rootData);
public void setTree(T rootData, BinaryTree<T> left, BinaryTree<T> right);
}
------------------------------------------------------------------------------------------------------------------------------------------------
import java.util.Iterator;
import java.util.Stack;
public class BinaryTree<T> implements BinaryTreeInterface<T> {
private BinaryNode<T> root;
public BinaryTree() {
root = null;
}
public BinaryTree(T rootData) {
root = new BinaryNode<T>(rootData);
}
public BinaryTree(T rootData, BinaryTree<T> leftTree, BinaryTree<T> rightTree) {
privateSetTree(rootData, leftTree, rightTree);
}
public void setTree(T rootData) {
root = new BinaryNode<T>(rootData);
}
public void setTree(T rootData, BinaryTree<T> left, BinaryTree<T> right) {
privateSetTree(rootData, left, right);
}
private void privateSetTree(T rootData, BinaryTree<T> left, BinaryTree<T> right) {
root = new BinaryNode<>(rootData);
if ((left != null) && (!left.isEmpty())) {
root.setLeftChild(left.root.copy());
}
if ((right != null) && (!right.isEmpty())) {
root.setRightChild(right.root.copy());
}
}
public T getRootData() {
return root.getData();
}
public int getHeight() {
return root.getHeight();
}
public int getNumberOfNodes() {
return root.getNumberOfNodes();
}
public boolean isEmpty() {
return root == null;
}
public void clear() {
root = null;
}
protected BinaryNode<T> getRootNode() {
return root;
}
public Iterator<T> getPreorderIterator() {
throw new UnsupportedOperationException(\"Preorder not supported.\");
}
public Iterator<T> getInorderIterator() {
throw new UnsupportedOperationException(\"Inorder not supported.\");
}
public Iterator<T> getPostorderIterator() {
return new PostorderIterator();
}
public Iterator<T> getLevelorderIterator() {
throw new UnsupportedOperationException(\"Level Order not supported.\");
}
private class PostorderIterator implements Iterator<T> {
private Stack<BinaryNode<T>> nodeStack;
private BinaryNode<T> current;
public PostorderIterator() {
nodeStack = new Stack<>();
current = root;
populateStack(current);
}
private void populateStack(BinaryNode<T> node) {
nodeStack.add(node);
if (node.hasRightChild()) {
populateStack(node.getRightChild());
}
if (node.hasLeftChild()) {
populateStack(node.getLeftChild());
}
}
public boolean hasNext() {
return !nodeStack.isEmpty();
}
public T next() {
return nodeStack.pop().getData();
}
}
}
--------------------------------------------------------------------------------------------------------------------------------------------------
public class BinaryNode<T> {
private T data;
private BinaryNode<T> leftChild, rightChild;
public BinaryNode() {
this(null);
}
public BinaryNode(T data) {
this(data, null, null);
}
public BinaryNode(T data, BinaryNode<T> left, BinaryNode<T> right) {
this.data = data;
leftChild = left;
setRightChild(right);
}
public T getData() {
return data;
}
public void setData(T data) {
this.data = data;
}
public BinaryNode<T> getLeftChild() {
return leftChild;
}
public void setLeftChild(BinaryNode<T> left) {
leftChild = left;
}
public BinaryNode<T> getRightChild() {
return rightChild;
}
public void setRightChild(BinaryNode<T> right) {
this.rightChild = right;
}
public boolean hasLeftChild() {
return leftChild != null;
}
public boolean hasRightChild() {
return rightChild != null;
}
public boolean isLeaf() {
return (!hasLeftChild() && !hasRightChild());
}
public BinaryNode<T> copy() {
BinaryNode<T> newRoot = new BinaryNode<T>(data);
if (leftChild != null) {
newRoot.setLeftChild(leftChild.copy());
}
if (rightChild != null) {
newRoot.setRightChild(rightChild.copy());
}
return newRoot;
}
public int getHeight() {
return getHeight(this);
}
private int getHeight(BinaryNode<T> node) {
int height = 0;
if (node != null) {
height = 1 + Math.max(getHeight(node.getLeftChild()), getHeight(node.getRightChild()));
}
return height;
}
public int getNumberOfNodes() {
return getNumberOfNodes(this);
}
private int getNumberOfNodes(BinaryNode<T> node) {
int rightNumber = 0;
int leftNumber = 0;
if (leftChild != null) {
leftNumber = getNumberOfNodes(node.getLeftChild());
}
if (rightChild != null) {
rightNumber = getNumberOfNodes(node.getRightChild());
}
return 1 + leftNumber + rightNumber;
}
}
---------------------------------------------------------------------------------------------------------------------------------------------------
public class Variable {
private String name;
private double value;
public Variable(String name) {
this.name = name;
}
public Variable(String name, double value) {
this.name = name;
this.setValue(value);
}
public String getName() {
return name;
}
public void setName(String newName) {
this.name = newName;
}
public double getValue() {
return value;
}
public void setValue(double value) {
this.value = value;
}
}
----------------------------------------------------------------------------------------------------------------------------------------------------
public interface ExpressionTreeInterface<T> extends BinaryTreeInterface<String> {
public double evaluate();
}
--------------------------------------------------------------------------------------------------------------------------------------------------
import java.util.HashMap;
import java.util.Iterator;
import java.util.Stack;
public class ExpressionTree extends BinaryTree<String> implements ExpressionTreeInterface<String> {
private HashMap<String, Variable> variables;
private String[] postfix;
public ExpressionTree(String[] args) {
variables = new HashMap<String, Variable>();
postfix = args;
}
public double evaluate() {
return evaluate(postfixToExpressionTree(postfix).getRootNode());
}
public void setVariable(String str, double d) {
variables.put(str, new Variable(str, d));
}
private double evaluate(BinaryNode<String> rootNode) {
double result;
if (rootNode == null) {
result = 0;
} else if (rootNode.isLeaf()) {
String root = rootNode.getData();
if (isVariable(root)) {
result = variables.get(root).getValue();
} else {
result = Double.parseDouble(root);
}
} else {
double firstOp = evaluate(rootNode.getLeftChild());
double secondOp = evaluate(rootNode.getRightChild());
String operator = rootNode.getData();
result = compute(operator, firstOp, secondOp);
}
return result;
}
private double compute(String operator, double first, double second) {
switch (operator) {
case \"+\":
return first + second;
case \"-\":
return first - second;
case \"*\":
return first * second;
case \"/\":
if (second == 0) {
throw new ArithmeticException(\"Cannot divide by zero\");
}
return first / second;
}
return 0;
}
private BinaryTree<String> postfixToExpressionTree(String[] postfix) {
Stack<BinaryTree<String>> stack = new Stack<BinaryTree<String>>();
for (String token : postfix) {
if (isVariable(token) || isDouble(token)) {
stack.push(new BinaryTree<String>(token));
continue;
} else if (!isOperator(token) && !isVariable(token) && !isDouble(token)) {
throw new IllegalArgumentException(\"Variable must be defined.\");
} else if (isOperator(token)) {
BinaryTree<String> right = stack.pop();
BinaryTree<String> left = stack.pop();
stack.push(new BinaryTree<String>(token, left, right));
}
}
return stack.pop();
}
private boolean isDouble(String str) {
try {
Double.parseDouble(str);
return true;
} catch (NumberFormatException e) {
return false;
}
}
private boolean isVariable(String str) {
return variables.containsKey(str);
}
private boolean isOperator(String str) {
switch (str) {
case \"+\":
case \"-\":
case \"*\":
case \"/\":
return true;
}
return false;
}
public void displayPostfix() {
String post = \"\";
Iterator<String> it = postfixToExpressionTree(postfix).getPostorderIterator();
while (it.hasNext()) {
post += it.next();
if (it.hasNext()) {
post += \" \";
}
}
System.out.println(post);
}
}
------------------------------------------------------------------------------------------------------------------------------------------------
import java.util.InputMismatchException;
import java.util.Scanner;
public class ExpressionTest {
public static boolean isDouble(String value) {
try {
Double.parseDouble(value);
return true;
} catch (NumberFormatException e) {
return false;
}
}
public static void main(String[] args) {
Scanner kb = new Scanner(System.in);
boolean hasExpression = false;
boolean quit = false;
String userInput = null;
ExpressionTree exp = new ExpressionTree(new String[]{\"a\", \"b\", \"2\", \"/\", \"+\"});
while (!quit) {
System.out.print(\"\ \ J. Botkin\'s Expression Tree \ \ \");
if (hasExpression) {
System.out.println(\"Current Expression: \" + userInput
+ \"\");
}
System.out.println(\"\ 1. Enter New Expression \ \"
+ \"2. Set Expression Variable \ \"
+ \"3. Evaluate Expression \ \"
+ \"4. Display Postfix \ \"
+ \"5. Quit\");
try {
int option = kb.nextInt();
switch (option) {
case 1:
System.out.println(\"Enter Expression seperated by spaces.\");
Scanner b = new Scanner(System.in);
userInput = b.nextLine();
String[] userExp = userInput.split(\" \");
switch (userExp.length) {
case 1:
exp = new ExpressionTree(new String[]{userExp[0]});
break;
case 2:
exp = new ExpressionTree(new String[]{userExp[0], userExp[1]});
break;
case 3:
exp = new ExpressionTree(new String[]{userExp[0], userExp[1], userExp[2]});
break;
case 4:
exp = new ExpressionTree(new String[]{userExp[0], userExp[1], userExp[2], userExp[3]});
break;
case 5:
exp = new ExpressionTree(new String[]{userExp[0], userExp[1], userExp[2], userExp[3], userExp[4]});
break;
case 6:
exp = new ExpressionTree(new String[]{userExp[0], userExp[1], userExp[2], userExp[3], userExp[4], userExp[5]});
break;
case 7:
exp = new ExpressionTree(new String[]{userExp[0], userExp[1], userExp[2], userExp[3], userExp[4], userExp[5], userExp[6]});
break;
case 8:
exp = new ExpressionTree(new String[]{userExp[0], userExp[1], userExp[2], userExp[3], userExp[4], userExp[5], userExp[6], userExp[7]});
break;
case 9:
exp = new ExpressionTree(new String[]{userExp[0], userExp[1], userExp[2], userExp[3], userExp[4], userExp[5], userExp[6], userExp[7], userExp[8]});
break;
}
/*for(int i = 0; i < userExp.length; i++){
if(isDouble(userExp[i])){
exp.setVariable(userExp[i], Double.parseDouble(userExp[i]));
}
}
hasExpression = true;*/
break;
case 2:
Scanner k = new Scanner(System.in);
System.out.print(\"Variable name: \");
String name = k.nextLine();
System.out.print(\"Variable value: \");
double value = k.nextDouble();
exp.setVariable(name, value);
break;
case 3:
try {
System.out.println(exp.evaluate());
} catch (IllegalArgumentException e) {
System.out.println(\"Please define all variables.\");
}
break;
case 4:
try {
exp.displayPostfix();
} catch (IllegalArgumentException e) {
System.out.println(\"Please define all variables.\");
}
break;
case 5:
quit = true;
break;
default:
System.out.println(\"Enter Correct option.\");
break;
}
} catch (InputMismatchException e) {
System.out.println(\"Enter Correct option.\");
main(args);
}
}
}
}
---------------------------------------------------------------------------------------------------------------------------------------------------
OUTPUT
run:
J. Botkin\'s Expression Tree
1. Enter New Expression
2. Set Expression Variable
3. Evaluate Expression
4. Display Postfix
5. Quit
1
Enter Expression seperated by spaces.
a b *
J. Botkin\'s Expression Tree
1. Enter New Expression
2. Set Expression Variable
3. Evaluate Expression
4. Display Postfix
5. Quit
2
Variable name: a
Variable value: 6.2
J. Botkin\'s Expression Tree
1. Enter New Expression
2. Set Expression Variable
3. Evaluate Expression
4. Display Postfix
5. Quit
2
Variable name: b
Variable value: 2.0
J. Botkin\'s Expression Tree
1. Enter New Expression
2. Set Expression Variable
3. Evaluate Expression
4. Display Postfix
5. Quit
4
a b *
J. Botkin\'s Expression Tree
1. Enter New Expression
2. Set Expression Variable
3. Evaluate Expression
4. Display Postfix
5. Quit
3
12.4
J. Botkin\'s Expression Tree
1. Enter New Expression
2. Set Expression Variable
3. Evaluate Expression
4. Display Postfix
5. Quit
5
BUILD SUCCESSFUL (total time: 44 seconds)
