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> l = postOrder();

for (Node b:l) ans += b.getData() + " ";

return ans;

}

public final String prefix() {

String ans = "";

ArrayList> l = preOrder();

for (Node b:l) ans += b.getData() + " ";

return ans;

}

}

// classes BinaryTree, BNode, Tree and Node exacctly as implemented in our course

class BinaryTree extends Tree {

public BinaryTree() {

super();

}

public void addRoot(T x) throws Exception {

if (root != null) throw new Exception("The tree is not empty");

root = new BNode(x, null, null, null);

size++;

}

public void addLeft(BNode n, T x) throws Exception {

if (n.getLeft() != null) throw new Exception("Already used");

n.setLeft(new BNode(x, n, null, null));

size++;

}

public void addRight(BNode n, T x) throws Exception {

if (n.getRight() != null) throw new Exception("Already used");

n.setRight(new BNode(x, n, null, null));

size++;

}

// returns the parent of the removed node

public BNode removeNode(BNode n) {

if (isLeaf(n)) { // base case

BNode p = (BNode) parent(n);

if (p == null) root = null;

else p.removeChild(n);

size--;

return p;

}

if (n.getLeft() != null) {

BNode m = rightmostLeftDescendant(n);

n.setData(m.getData());

return removeNode(m); // recursively remove rightmost left descendant

}

// otherwise n does have a right child

BNode m = leftmostRightDescendant(n);

n.setData(m.getData());

return removeNode(m);

}

public BNode leftmostRightDescendant(BNode n) {

BNode m = n.getRight();

while (m.getLeft() != null) m = m.getLeft();

return m;

}

public BNode rightmostLeftDescendant(BNode n) {

BNode m = n.getLeft();

while (m.getRight() != null) m = m.getRight();

return m;

}

public ArrayList> inOrder() {

ArrayList> answer = new ArrayList>();

inOrder((BNode) root(), answer);

return answer;

}

public void inOrder(BNode n, ArrayList> v) {

if (n == null) return;

inOrder(n.getLeft(), v);

v.add(n);

inOrder(n.getRight(), v);

}

public ArrayList> flatOrder() {

return inOrder();

}

}

class BNode extends Node {

BNode left, right;

public BNode(T d, BNode p, BNode l, BNode r) {

setData(d);

setParent(p);

left = l;

right = r;

}

public void setLeft(BNode n) {

left = n;

}

public void setRight(BNode n) {

right = n;

}

public BNode getLeft() {

return left;

}

public BNode getRight() {

return right;

}

public Iterator> children() {

ArrayList> v = new ArrayList<>();

if (left != null) v.add(left);

if (right != null) v.add(right);

return v.iterator();

}

public void removeChild(BNode n) {

if (getLeft() == n) setLeft(null);

else setRight(null);

}

public String toString() { // for testing and debugging

return "Node " + data;

}

}

class Tree {

protected Node root;

public int size;

public Tree() {

root = null;

size = 0;

}

public Node root() {

return root;

}

public Node parent(Node v) {

return v.getParent();

}

public Iterator> children(Node v) {

return v.children();

}

public boolean isRoot(Node v) {

return v == root;

}

public boolean isInternal(Node v) {

return children(v).hasNext();

}

public boolean isLeaf(Node v) {

return !isInternal(v);

}

public int size() {

return size;

}

public boolean empty() {

return size == 0;

}

public void replace(Node v, T t) {

v.setData(t);

}

public int depth(Node v) {

if (isRoot(v))

return 0;

return 1 + depth(parent(v));

}

public int height(Node v) {

if (isLeaf(v))

return 0;

int maxChild = 0;

Iterator> c = children(v);

while (c.hasNext()) {

int hc = height((Node) c.next());

if (hc > maxChild)

maxChild = hc;

}

return maxChild + 1;

}

public int height() {

if (root == null)

return -1;

return height(root);

}

public ArrayList> preOrder() {

ArrayList> answer = new ArrayList<>();

preOrder(root(), answer);

return answer;

}

public void preOrder(Node n, ArrayList> v) {

if (n == null)

return;

v.add(n);

Iterator> x = children(n);

while (x.hasNext()) {

Node m = x.next();

preOrder(m, v);

}

}

public ArrayList> postOrder() {

ArrayList> answer = new ArrayList>();

postOrder(root(), answer);

return answer;

}

public void postOrder(Node n, ArrayList> v) {

if (n == null)

return;

Iterator> x = children(n);

while (x.hasNext()) {

Node m = x.next();

postOrder(m, v);

}

v.add(n);

}

public ArrayList> levelOrder() {

ArrayList> waiting = new ArrayList<>();

waiting.add(null);

if (root() == null)

return waiting;

waiting.add(root());

int done = 0;

while (done < waiting.size()) {

Node oldNode = waiting.get(done++);

if (oldNode == null) {

if (done < waiting.size())

waiting.add(null);

continue;

}

Iterator> c = children(oldNode);

while (c.hasNext())

waiting.add(c.next());

}

return waiting;

}

public ArrayList> flatOrder() {

return preOrder();

}

public String toString() {

return treePrint(null);

}

public String treePrint(Node cursor) {

String answer = " ";

Iterator> lev = levelOrder().iterator();

Iterator> flat = flatOrder().iterator();

lev.next(); // skip first new line

while (lev.hasNext()) {

Node o = lev.next();

if (o == null) {

answer += " ";

flat = flatOrder().iterator();

} else

while (true) {

boolean atCursor = false;

Node n = flat.next();

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 parent;

protected T data;

public abstract Iterator> children();

public void setParent(Node n) {

parent = n;

}

public void setData(T t) {

data = t;

}

public Node getParent() {

return parent;

}

public T getData() {

return data;

}

}