Question
import java.util.ArrayList; import java.util.Iterator; import java.util.Scanner; // import java.util.Stack; // You will probably want to make use of this // Homework Y: Expression trees. //
import java.util.ArrayList;
import java.util.Iterator;
import java.util.Scanner;
// import java.util.Stack; // You will probably want to make use of this
// Homework Y: Expression trees.
// In the project you need to code one class that extends the abstract class ExpressionTree.
// Your class needs to code one constructor and one output method as well as any helper methods
// that you find useful.
// The goal is to process mathematical expressions that are provided as strings.
// In the main program that tests your class,
// the Utility getInput method reads a mathematical expression that is typed as input.
// The expression can contain any combination of numbers, variable identifiers and mathematical operations.
// These mathematical operations are +, -, *, /, ( and )
// The constructor should turn an input expression into the content of a binary (expression) tree.
// The tree can then be printed in prefix, postfix, or fully parenthesised infix notation.
// The first two of these methods have been coded for you in the abstract class ExpressionTree, you need to code the third.
// For example the expression 5 + (x / y + z * 7) - 2 would be printed as
// - + 5 + / x y * z 7 2 in prefix order
// or 5 x y / z 7 * + + 2 - in postfix order
// or (( 5 + ((x / y) + (z * 7))) - 2) in fully parenthesised infix notation.
// To simplify things in this project the - sign can only be used between 2 quantities that are being subtracted.
// This will prevent you from ever working with a negative number such as -2 which would involve a different
// use for the - character. However the simplification means that your code does not need to work out which meaning
// to attach to any copy of a - character.
// Another simplification for this project is that you may assume that only correct mathematical expressions are entered.
// You do not need to check that an input String from getInput makes sense as an expression.
// If an illegal expression is encountered, your program can behave in any way that is convenient for you.
// You should change the class name Y00000000 so that the last 8 digits are your ID number.
// You should only make changes inside this class.
// You do not need any more than 100 lines of code in the class.
// After you have tested your work on venus (as well as in your development environment,
// cut the file above the class Utility and submit it by email.
// See also the general homework guidelines for other instructions before you submit work.
// The hard part of this assignment is the constructor.
// In terms of planning it, I suggest that you think about which operation is the last to be performed in the expression.
// Can you write down a rule to identify this operation? Deal with the easier case when there are no parentheses first.
//
// Once you accomplish this you can finish quickly using a recursion.
//
// The fullyParenthesised method can also be done using a recursion ---
// this will require an auxiliary recursive method to call on.
// Suggested strategy:
// 1. Make a constructor that deals with expressions without parentheses (1st step partial credit).
// 2. Make a fullyParenthesised output method (2nd step partial credit).
// 3. Adapt the constructor to deal with parentheses. Hint a Stack will help here. (Last part of credit).
public class Y00000000 extends ExpressionTree {
public static void main(String args[]) {
Y00000000 y = new Y00000000("5 + 6 * 7");
Utility.print(y);
y = new Y00000000(Utility.getInput());
Utility.print(y);
}
public String fullyParenthesised() {
// add implementation here
return "";
}
public Y00000000(String s) {
super();
// add implementation here
}
}
//------- cut here. Place your new code above this line and submit only the ------
//------- code above this line as your homework. Do not make any code changes ----
//------- below this line. ---------
class Utility {
public static String getInput() {
System.out.println("Enter an algebraic expression: ");
Scanner s = new Scanner(System.in);
String answer = s.nextLine();
s.close();
return answer;
}
public static void print(ExpressionTree y) {
System.out.println("Prefix: " + y.prefix());
System.out.println("Postfix: " + y.postfix());
System.out.println("Fully parenthesised: " + y.fullyParenthesised());
System.out.println("-----------------");
}
}
abstract class ExpressionTree extends BinaryTree
public ExpressionTree() {
super();
}
public abstract String fullyParenthesised();
public final String postfix() {
String ans = "";
ArrayList
for (Node
return ans;
}
public final String prefix() {
String ans = "";
ArrayList
for (Node
return ans;
}
}
// classes BinaryTree, BNode, Tree and Node exacctly as implemented in our course
class BinaryTree
public BinaryTree() {
super();
}
public void addRoot(T x) throws Exception {
if (root != null) throw new Exception("The tree is not empty");
root = new BNode
size++;
}
public void addLeft(BNode
if (n.getLeft() != null) throw new Exception("Already used");
n.setLeft(new BNode
size++;
}
public void addRight(BNode
if (n.getRight() != null) throw new Exception("Already used");
n.setRight(new BNode
size++;
}
// returns the parent of the removed node
public BNode
if (isLeaf(n)) { // base case
BNode
if (p == null) root = null;
else p.removeChild(n);
size--;
return p;
}
if (n.getLeft() != null) {
BNode
n.setData(m.getData());
return removeNode(m); // recursively remove rightmost left descendant
}
// otherwise n does have a right child
BNode
n.setData(m.getData());
return removeNode(m);
}
public BNode
BNode
while (m.getLeft() != null) m = m.getLeft();
return m;
}
public BNode
BNode
while (m.getRight() != null) m = m.getRight();
return m;
}
public ArrayList
ArrayList
inOrder((BNode
return answer;
}
public void inOrder(BNode
if (n == null) return;
inOrder(n.getLeft(), v);
v.add(n);
inOrder(n.getRight(), v);
}
public ArrayList
return inOrder();
}
}
class BNode
BNode
public BNode(T d, BNode
setData(d);
setParent(p);
left = l;
right = r;
}
public void setLeft(BNode
left = n;
}
public void setRight(BNode
right = n;
}
public BNode
return left;
}
public BNode
return right;
}
public Iterator
ArrayList
if (left != null) v.add(left);
if (right != null) v.add(right);
return v.iterator();
}
public void removeChild(BNode
if (getLeft() == n) setLeft(null);
else setRight(null);
}
public String toString() { // for testing and debugging
return "Node " + data;
}
}
class Tree
protected Node
public int size;
public Tree() {
root = null;
size = 0;
}
public Node
return root;
}
public Node
return v.getParent();
}
public Iterator extends Node
return v.children();
}
public boolean isRoot(Node
return v == root;
}
public boolean isInternal(Node
return children(v).hasNext();
}
public boolean isLeaf(Node
return !isInternal(v);
}
public int size() {
return size;
}
public boolean empty() {
return size == 0;
}
public void replace(Node
v.setData(t);
}
public int depth(Node
if (isRoot(v))
return 0;
return 1 + depth(parent(v));
}
public int height(Node
if (isLeaf(v))
return 0;
int maxChild = 0;
Iterator extends Node
while (c.hasNext()) {
int hc = height((Node
if (hc > maxChild)
maxChild = hc;
}
return maxChild + 1;
}
public int height() {
if (root == null)
return -1;
return height(root);
}
public ArrayList
ArrayList
preOrder(root(), answer);
return answer;
}
public void preOrder(Node
if (n == null)
return;
v.add(n);
Iterator extends Node
while (x.hasNext()) {
Node
preOrder(m, v);
}
}
public ArrayList
ArrayList
postOrder(root(), answer);
return answer;
}
public void postOrder(Node
if (n == null)
return;
Iterator extends Node
while (x.hasNext()) {
Node
postOrder(m, v);
}
v.add(n);
}
public ArrayList
ArrayList
waiting.add(null);
if (root() == null)
return waiting;
waiting.add(root());
int done = 0;
while (done < waiting.size()) {
Node
if (oldNode == null) {
if (done < waiting.size())
waiting.add(null);
continue;
}
Iterator extends Node
while (c.hasNext())
waiting.add(c.next());
}
return waiting;
}
public ArrayList extends Node
return preOrder();
}
public String toString() {
return treePrint(null);
}
public String treePrint(Node
String answer = " ";
Iterator
Iterator extends Node
lev.next(); // skip first new line
while (lev.hasNext()) {
Node
if (o == null) {
answer += " ";
flat = flatOrder().iterator();
} else
while (true) {
boolean atCursor = false;
Node
if (n == cursor)
atCursor = true;
String s = n.getData().toString();
if (atCursor)
s = "* " + s + " *";
if (n == o) {
answer += s + " ";
break;
} else {
for (int i = 0; i < s.length(); i++)
answer += ' ';
answer += ' ';
}
}
}
return answer;
}
}
abstract class Node
protected Node
protected T data;
public abstract Iterator extends Node
public void setParent(Node
parent = n;
}
public void setData(T t) {
data = t;
}
public Node
return parent;
}
public T getData() {
return data;
}
}
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started