Sample Data Structures Java Assignment

Data Assignment Instructions

This lab is intended to solidify your knowledge of the definition and use of binary trees. A fully parenthesized arithmetic expression (simple – consisting of single digits and numeric operations) is shown in a corresponding binary tree representation.

The task is to build a set of classes that will convert the expression to that binary tree, to evaluate tree contents generating a numeric answer, and to print a parenthesized representation of the tree – not the string itself.

At a minimum you will need to create the following classes and their methods:

Class: 

  • Expression.java – this will be the class containing tree and stack instance variables that will be used in the conversion of the string to its tree representation.

Methods:

  • public LinkedBinaryTree<T> buildExpression (String expression);
  • public int evaluateExpression (LinkedBinaryTree<T> tree, Position<T> v);
  • public void parenthesize (Tree<T>tree, Position<T>p);

Class:  ExpressionTest.java – the test driver that will define the expression, call buildExpression to build a tree, call evaluateExpression to generate an answer.  Call parenthesize to generate a parenthesized representation of the tree.

Solution

LinkedBinaryTree.java

public class LinkedBinaryTree<T> {

    public char root='a';
    public LinkedBinaryTree<T> leftRoot;
    public LinkedBinaryTree<T> rightRoot;

    public void addRoot(char root)
    {
        this.root=root;
    }

    public void attach(char root,LinkedBinaryTree<T> left,LinkedBinaryTree<T> right)
    {
        this.root=root;
        this.leftRoot=left;
        this.rightRoot=right;
    }

}

ExpressionTest.java

public class ExpressionTest {

    /**
     * @param args
     */
    public static void main(String[] args) {

        String s = new String();
        String exp = "((((3+1)x3)/((9-5)+2))-((3x(7-4))+6))";
        Expression<String> expression = new Expression<String>();

        System.out.println("The original Expression String: %s"+exp);

        LinkedBinaryTree<String> tree= expression.buildExpression(exp);
        System.out.println("\nTree in parentized form");
        expression.parenthesize(tree, tree);
        System.out.println("");
        int Result = expression.evaluateExpression(tree, tree);
        System.out.println("\n\n the evaluated expression is "+Result);
    }

}

Expression.java

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;


public class Expression<T> {

    public LinkedBinaryTree<T> buildExpression(String expression){
        Stack<LinkedBinaryTree>s= new Stack<LinkedBinaryTree>();
        LinkedBinaryTree<T>T=null;
        for(int i=0;i<expression.length();i++)
        {
            
            
            LinkedBinaryTree<T>T1=null;
            LinkedBinaryTree<T>T2=null;
            
            char e = expression.charAt(i);
            if(e==')'){
                T2=s.pop();
                T=s.pop();
                T1=s.pop();
                T.attach(T.root, T1, T2);
                s.push(T);
            }else
                if(e!='(')
                {
                    T=new LinkedBinaryTree<>();
                    T.addRoot(e);
                    s.push(T);
                }
        }
        
        return T;
    }
    
    public int evaluateExpression(LinkedBinaryTree<T> tree, LinkedBinaryTree<T> v){
        
        if(verifInternalTree(v.root))
        {
            int x = evaluateExpression(tree, v.leftRoot);
            int y = evaluateExpression(tree, v.rightRoot);
            int result =0;
            if(v.root=='+')result=x+y;
            if(v.root=='-')result=x-y;
            if(v.root=='x')result=x*y;
            if(v.root=='/')result=x/y;
            
            return result;
        }
            else
                return Integer.parseInt(v.root+"");
    }
    
    private boolean verifInternalTree(char a) {
        if((a=='+')||(a=='-')||(a=='x')||(a=='/'))
            return true;
            return false;
    }

    public void parenthesize(LinkedBinaryTree<T> tree,LinkedBinaryTree<T>p){
    
        if (verifInternalTree(p.root)){
            System.out.print("(");
            if(!verifInternalTree(p.leftRoot.root))
            System.out.print(p.leftRoot.root);
        else parenthesize(tree, p.leftRoot);
        
        System.out.print(p.root);
        
        if(!verifInternalTree(p.rightRoot.root))
            System.out.print(p.rightRoot.root);
        else    parenthesize(tree, p.rightRoot);
        System.out.print(")");
        }
        
    }

}