I am doing a tree in java for data structure. I am trying to read in user input
ID: 3580062 • Letter: I
Question
I am doing a tree in java for data structure. I am trying to read in user input separated by space and insert the values into a tree. Everything is working correctly until I have double digit integers. It seems to be reading each integer char and inserting into the tree when I want it to read both first and then insert the double digit integer into the tree
e.g.
when the user inputs 9 3 + 7 * this works fine, however, when user input 10 3 + 7 *, it will insert 10 as 1 first and then insert 0. I want it to insert 10. (this is the prefix format of the eq)
How do I fix this?
below is my program
class ExpressionTree {
class TreeNode {
char data;
TreeNode left, right;
/** constructor **/
public TreeNode(char data) {
this.data = data;
this.left = null;
this.right = null;
}
}
class StackNode {
TreeNode treeNode;
StackNode next;
public StackNode(TreeNode treeNode) {
this.treeNode = treeNode;
next = null;
}
}
private static StackNode top;
public ExpressionTree() {
top = null;
}
public void clear() {
top = null;
}
private void push(TreeNode ptr) {
if (top == null) top = new StackNode(ptr);
else {
StackNode nptr = new StackNode(ptr);
nptr.next = top;
top = nptr;
}
}
private TreeNode pop() {
if (top == null) throw new RuntimeException("Underflow");
else {
TreeNode ptr = top.treeNode;
top = top.next;
return ptr;
}
}
private TreeNode peek() {
return top.treeNode;
}
private void insert(char val, String eqn, int i) {
try {
if (isDigit(val)) {
//while reading space --> go to next
// if reading char, add to iaa
TreeNode nptr = new TreeNode(val);
push(nptr);
}
else if (isOperator(val)) {
TreeNode nptr = new TreeNode(val);
nptr.left = pop();
nptr.right = pop();
push(nptr);
}
}
catch(Exception e) {
System.out.println("Invalid Expression");
}
}
//if it is a valid digit return true
private boolean isDigit(char ch) {
return ch >= '0' && ch <= '9';
}
//if it is a valid operator return true
private boolean isOperator(char ch) {
return ch == '+' || ch == '-' || ch == '*' || ch == '/';
}
private int toDigit(char ch) {
return ch - '0';
}
//starting from index 0 increment the index after char has been inserted into the tree
//and terminate the for loop once we have reached equation legnth
public void buildTree(String eqn) {
// String [] eqnSubparts = eqn.split(" ");
// System.out.print(" eqnSubparts: " + eqnSubparts);
for (int i = 0; i <= eqn.length() - 1; i++) {
// System.out.print(" eqnSubparts: " + eqnSubparts[i]);
insert(eqn.charAt(i), eqn, i);
}
}
public double evaluate() {
return evaluate(peek());
}
public double evaluate(TreeNode ptr) {
if (ptr.left == null && ptr.right == null) return toDigit(ptr.data);
else {
double result = 0.0;
double left = evaluate(ptr.left);
double right = evaluate(ptr.right);
char operator = ptr.data;
//switch statment for oper
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;
}
}
}
/** class ExpressionTreeTest **/
public class ExpressionTreeTest {
public static void main(String[] args) {
Scanner scan = new Scanner(System. in );
System.out.println("Expression Tree Test");
/** make object of ExpressionTree **/
ExpressionTree et = new ExpressionTree();
System.out.println(" Enter equation in prefix form");
//String line = scan.nextLine();
//System.out.print("First digit : " + line);
et.buildTree(scan.nextLine());
System.out.print(" Input : ");
System.out.println(" Evaluated Result : " + et.evaluate());
}
}
Explanation / Answer
Now I made changes to insert 10 insead of 1. Main mistake is , you are sending data everywhere as char instead of string. Now I am parsing string to chars and processing. Please check. Changes I done are marked as "bold".
/**
*
* @author paramesh
*/
import java.util.Scanner;
class ExpressionTree {
class TreeNode {
String data;
TreeNode left, right;
/**
* constructor *
*/
public TreeNode(String data) {
this.data = data;
this.left = null;
this.right = null;
}
}
class StackNode {
TreeNode treeNode;
StackNode next;
public StackNode(TreeNode treeNode) {
this.treeNode = treeNode;
next = null;
}
}
private static StackNode top;
public ExpressionTree() {
top = null;
}
public void clear() {
top = null;
}
private void push(TreeNode ptr) {
if (top == null) {
top = new StackNode(ptr);
} else {
StackNode nptr = new StackNode(ptr);
nptr.next = top;
top = nptr;
}
}
private TreeNode pop() {
if (top == null) {
throw new RuntimeException("Underflow");
} else {
TreeNode ptr = top.treeNode;
top = top.next;
return ptr;
}
}
private TreeNode peek() {
return top.treeNode;
}
private void insert(String val, String eqn, int i) {
try {
if (isDigit(val)) {
//while reading space --> go to next
// if reading char, add to iaa
TreeNode nptr = new TreeNode(val);
push(nptr);
} else if (isOperator(val)) {
TreeNode nptr = new TreeNode(val);
nptr.left = pop();
nptr.right = pop();
push(nptr);
}
} catch (Exception e) {
System.out.println("Invalid Expression");
}
}
//if it is a valid digit return true
private boolean isDigit(String ch) {
try {
double d = Integer.parseInt(ch);
} catch (NumberFormatException ex) {
return false;
}
return true;
}
//if it is a valid operator return true
private boolean isOperator(String str) {
char ch = str.charAt(0);
return ch == '+' || ch == '-' || ch == '*' || ch == '/';
}
private int toDigit(String str) {
char ch = str.charAt(0);
return ch - '0';
}
//starting from index 0 increment the index after char has been inserted into the tree
//and terminate the for loop once we have reached equation legnth
public void buildTree(String eqn) {
String[] eqnSubparts = eqn.split(" ");
for (int i = 0; i < eqnSubparts.length; i++) {
insert(eqnSubparts[i], eqn, i);
}
}
public double evaluate() {
return evaluate(peek());
}
public double evaluate(TreeNode ptr) {
if (ptr.left == null && ptr.right == null) {
return toDigit(ptr.data);
} else {
double result = 0.0;
double left = evaluate(ptr.left);
double right = evaluate(ptr.right);
String operatorTemp = ptr.data;
char operator = operatorTemp.charAt(0);
//switch statment for oper
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;
}
}
}
/**
* class ExpressionTreeTest *
*/
public class ExpressionTreeTest {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
System.out.println("Expression Tree Test");
/**
* make object of ExpressionTree *
*/
ExpressionTree et = new ExpressionTree();
System.out.println(" Enter equation in prefix form");
String line = scan.nextLine();
//System.out.print("First digit : " + line);
et.buildTree(line);
System.out.println("Input : "+line);
System.out.println(" Evaluated Result : " + et.evaluate());
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.