Java - data structures P3 Design an algorithm that produces a binary expression
ID: 3827589 • Letter: J
Question
Java - data structures
P3
Design an algorithm that produces a binary expression tree from a given infix expression. You can assume that the infix expression is a string that has only the binary operators +, -, *, / and one-letter operands. Implement the solution as a construction in ExpressionTree that takes a string argument:
public ExpressionTree(String infix)
that calls the private method
private ExpressionTreeInterface formTree(String expr, int first, int last)
to construct the tree. formTree() builds the tree recursively.
ExpressionTree.java
public class ExpressionTree extends BinaryTree<String> {
public ExpressionTree() {
} // end default constructor
public ExpressionTree(String data) {
super(data);
} // end default constructor
public double evaluate() {
return evaluate(root);
} // end evaluate
private double evaluate(BinaryNode<String> rootNode) {
double result;
if (rootNode == null)
result = 0;
else if (rootNode.isLeaf()) {
String variable = rootNode.getData();
result = getValueOf(variable);
}
else {
double firstOperand = evaluate(rootNode.getLeftChild());
double secondOperand = evaluate(rootNode.getRightChild());
String operator = rootNode.getData();
result = compute(operator, firstOperand, secondOperand);
} // end if
return result;
} // end evaluate
private double getValueOf(String variable) { // strings allow multicharacter variables
double result = 0;
if (variable.equals("a"))
result = 1;
else if (variable.equals("b"))
result = 2;
else if (variable.equals("c"))
result = 3;
else if (variable.equals("d"))
result = 4;
else if (variable.equals("e"))
result = 5;
return result;
} // end getValueOf
private double compute(String operator, double firstOperand, double secondOperand)
{
double result = 0;
if (operator.equals("+"))
result = firstOperand + secondOperand;
else if (operator.equals("-"))
result = firstOperand - secondOperand;
else if (operator.equals("*"))
result = firstOperand * secondOperand;
else if (operator.equals("/"))
result = firstOperand / secondOperand;
return result;
} // end compute
} // end ExpressionTree
Incase if you need Binarytree and Binarynode
BinaryTree.java
//package TreePackage;
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Stack ; // for Stack
public class BinaryTree
{
protected BinaryNode root;
public BinaryTree() {
root = null;
} // end default constructor
public BinaryTree(T rootData) {
root = new BinaryNode(rootData);
} // end constructor
public BinaryTree(T rootData, BinaryTree leftTree,
BinaryTree rightTree) {
privateSetTree(rootData, leftTree, rightTree);
} // end constructor
public void setTree(T rootData)
{
root = new BinaryNode(rootData);
} // end setTree
public void setTree(T rootData, BinaryTree leftTree,
BinaryTree rightTree)
{
privateSetTree(rootData, leftTree, rightTree);
} // end setTree
private void privateSetTree(T rootData, BinaryTree leftTree,
BinaryTree rightTree)
{
root = new BinaryNode(rootData);
if (leftTree != null)
root.setLeftChild(leftTree.root);
if (rightTree != null)
root.setRightChild(rightTree.root);
}
public T getRootData () {
T rootData = null;
if (root != null)
rootData = root.getData();
return rootData;
}
public boolean isEmpty () {
return root == null;
}
public void clear (){
root = null;
}
// getHeight and getNumberOfNodes call same functions in BinaryNode
public int getHeight () {
return root.getHeight ();
}
public int getNumberOfNodes () {
return root.getNumberOfNodes ();
}
public void inorderTraversal() {
Stack> nodeStack = new Stack>();
BinaryNode currentNode = root;
while (!nodeStack.empty() || currentNode != null) {
while(currentNode != null) {
nodeStack.push(currentNode);
currentNode = currentNode.getLeftChild();
}
if(!nodeStack.empty()) {
BinaryNode nextNode = nodeStack.pop();
System.out.println(nextNode.getData());
currentNode = nextNode.getRightChild();
}
}
}
public Iterator getPreorderIterator() {
return new PreorderIterator();
}
public Iterator getInorderIterator() {
return new InorderIterator();
}
private class PreorderIterator implements Iterator {
private Stack> nodeStack;
public PreorderIterator() {
nodeStack = new Stack>();
if (root != null)
nodeStack.push(root);
} // end default constructor
public boolean hasNext() {
return !nodeStack.isEmpty();
} // end hasNext
public T next() {
BinaryNode nextNode;
if (hasNext()) {
nextNode = nodeStack.pop();
BinaryNode leftChild = nextNode.getLeftChild();
BinaryNode rightChild = nextNode.getRightChild();
// push into stack in reverse order of recursive calls
if (rightChild != null)
nodeStack.push(rightChild);
if (leftChild != null)
nodeStack.push(leftChild);
}
else {
throw new NoSuchElementException();
}
return nextNode.getData();
} // end next
public void remove() {
throw new UnsupportedOperationException();
} // end remove
} // end PreorderIterator
private class InorderIterator implements Iterator < T >
{
private Stack< BinaryNode< T >> nodeStack;
private BinaryNode< T > currentNode;
public InorderIterator () {
nodeStack = new Stack < BinaryNode< T>> ();
currentNode = root;
} // end default constructor
public boolean hasNext () {
return !nodeStack.isEmpty () || (currentNode != null);
} // end hasNext
public T next ()
{
BinaryNode< T > nextNode = null;
// find leftmost node with no left child
while (currentNode != null) {
nodeStack.push (currentNode);
currentNode = currentNode.getLeftChild ();
} // end while
// get leftmost node, then move to its right subtree
if (!nodeStack.isEmpty ()) {
nextNode = nodeStack.pop ();
currentNode = nextNode.getRightChild ();
}
else
throw new NoSuchElementException ();
return nextNode.getData ();
} // end next
public void remove () {
throw new UnsupportedOperationException ();
} // end remove
} // end InorderIterator
} // end BinaryTree
BinaryNode.java
//package TreePackage;
class BinaryNode<T>
{
private T data;
private BinaryNode<T> left;
private BinaryNode<T> right;
public BinaryNode()
{
this(null); // call next constructor
} // end default constructor
public BinaryNode(T dataPortion)
{
this(dataPortion, null, null); // call next constructor
} // end constructor
public BinaryNode(T dataPortion, BinaryNode<T> leftChild,
BinaryNode<T> rightChild)
{
data = dataPortion;
left = leftChild;
right = rightChild;
} // end constructor
public T getData()
{
return data;
} // end getData
public void setData(T newData)
{
data = newData;
} // end setData
public BinaryNode<T> getLeftChild()
{
return left;
} // end getLeftChild
public void setLeftChild(BinaryNode<T> leftChild)
{
left = leftChild;
} // end setLeftChild
public boolean hasLeftChild()
{
return left != null;
} // end hasLeftChild
public boolean isLeaf()
{
return (left == null) && (right == null);
} // end isLeaf
public BinaryNode<T> getRightChild()
{
return right;
} // end getLeftChild
public void setRightChild(BinaryNode<T> rightChild)
{
right = rightChild;
} // end setLeftChild
public boolean hasRightChild()
{
return right != null;
} // end
public int getHeight()
{
return getHeight(this); // call private getHeight
} // end getHeight
private int getHeight(BinaryNode<T> node)
{
int height = 0;
if (node != null)
height = 1 + Math.max(getHeight(node.left),
getHeight(node.right));
return height;
} // end getHeight
public int getNumberOfNodes()
{
int leftNumber = 0;
int rightNumber = 0;
if (left != null)
leftNumber = left.getNumberOfNodes();
if (right != null)
rightNumber = right.getNumberOfNodes();
return 1 + leftNumber + rightNumber;
} // end getNumberOfNodes
public BinaryNode<T> copy()
{
BinaryNode<T> newRoot = new BinaryNode<T>(data);
if (left != null)
newRoot.left = left.copy();
if (right != null)
newRoot.right = right.copy();
return newRoot;
} // end copy
} // end BinaryNode
Explanation / Answer
JAVA CODE:
import java.io.*;
class Btree_Node
{
public char info;
public Btree_Node Lchild;
public Btree_Node Rchild;
public Btree_Node(char x)
{
info = x;
}
public void displayBtree_Node()
{
System.out.print(info);
}
}
class Infix_Stack
{
private Btree_Node[] a;
private int Stack_top, m;
public Infix_Stack(int Max_stack)
{
m = Max_stack;
a = new Btree_Node[m];
Stack_top = -1;
}
public void Stack_push(Btree_Node key)
{
a[++Stack_top] = key;
}
public Btree_Node Stack_pop()
{
return (a[Stack_top--]);
}
public boolean IsStackEmpty()
{
return (Stack_top == -1);
}
}
class Infix_stack2
{
private char[] a;
private int Stack_top, m;
public Infix_stack2(int Max_stack)
{
m = Max_stack;
a = new char[m];
Stack_top = -1;
}
public void Stack_push(char key)
{
a[++Stack_top] = key;
}
public char Stack_pop()
{
return (a[Stack_top--]);
}
public boolean IsStackEmpty()
{
return (Stack_top == -1);
}
}
class InfixToBtree
{
private Infix_stack2 s;
private String in;
private String out = "";
public InfixToBtree(String Strng)
{
in = Strng;
s = new Infix_stack2(Strng.length());
}
public String inToPost()
{
for (int i = 0; i < in.length(); i++)
{
char ch = in.charAt(i);
switch (ch)
{
case '+':
case '-':
StackgotOperator(ch, 1);
break;
case '*':
case '/':
StackgotOperator(ch, 2);
break;
case '(':
s.Stack_push(ch);
break;
case ')':
InfixgotParenthesis();
break;
default:
out = out + ch;
}
}
while (!s.IsStackEmpty())
out = out + s.Stack_pop();
return out;
}
private void StackgotOperator(char opThis, int prec1)
{
while (!s.IsStackEmpty())
{
char opTop = s.Stack_pop();
if (opTop == '(')
{
s.Stack_push(opTop);
break;
} else
{
int prec2;
if (opTop == '+' || opTop == '-')
prec2 = 1;
else
prec2 = 2;
if (prec2 < prec1)
{
s.Stack_push(opTop);
break;
} else
out = out + opTop;
}
}
s.Stack_push(opThis);
}
private void InfixgotParenthesis()
{
while (!s.IsStackEmpty())
{
char ch = s.Stack_pop();
if (ch == '(')
break;
else
out = out + ch;
}
}
}
class Btree
{
private Btree_Node root;
public Btree()
{
root = null;
}
public void Insert_node(String s)
{
InfixToBtree c = new InfixToBtree(s);
s = c.inToPost();
Infix_Stack stk = new Infix_Stack(s.length());
s = s + "#";
int i = 0;
char symbol = s.charAt(i);
Btree_Node newBtree_Node;
while (symbol != '#')
{
if (symbol >= '0' && symbol <= '9' || symbol >= 'A'
&& symbol <= 'Z' || symbol >= 'a' && symbol <= 'z')
{
newBtree_Node = new Btree_Node(symbol);
stk.Stack_push(newBtree_Node);
} else if (symbol == '+' || symbol == '-' || symbol == '/'
|| symbol == '*')
{
Btree_Node ptr1 = stk.Stack_pop();
Btree_Node ptr2 = stk.Stack_pop();
newBtree_Node = new Btree_Node(symbol);
newBtree_Node.Lchild = ptr2;
newBtree_Node.Rchild = ptr1;
stk.Stack_push(newBtree_Node);
}
symbol = s.charAt(++i);
}
root = stk.Stack_pop();
}
public void traverse(int type)
{
switch (type)
{
case 1:
System.out.print("Preorder Traversal:- ");
preOrder(root);
break;
case 2:
System.out.print("Inorder Traversal:- ");
inOrder(root);
break;
case 3:
System.out.print("Postorder Traversal:- ");
postOrder(root);
break;
default:
System.out.println("Invalid Choice");
}
}
private void preOrder(Btree_Node localRoot)
{
if (localRoot != null)
{
localRoot.displayBtree_Node();
preOrder(localRoot.Lchild);
preOrder(localRoot.Rchild);
}
}
private void inOrder(Btree_Node localRoot)
{
if (localRoot != null)
{
inOrder(localRoot.Lchild);
localRoot.displayBtree_Node();
inOrder(localRoot.Rchild);
}
}
private void postOrder(Btree_Node localRoot)
{
if (localRoot != null)
{
postOrder(localRoot.Lchild);
postOrder(localRoot.Rchild);
localRoot.displayBtree_Node();
}
}
}
public class Infix_Expression_Btree
{
public static void main(String args[]) throws IOException
{
String ch = "y";
DataInputStream inp = new DataInputStream(System.in);
while (ch.equals("y"))
{
Btree t1 = new Btree();
System.out.println("Enter the Expression");
String a = inp.readLine();
t1.Insert_node(a);
t1.traverse(1);
System.out.println("");
t1.traverse(2);
System.out.println("");
t1.traverse(3);
System.out.println("");
System.out.print("Enter y to continue ");
ch = inp.readLine();
}
}
}
Output:
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.