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:


  • – 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.


  • 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: – 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.


public class LinkedBinaryTree<T> {

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

    public void addRoot(char root)

    public void attach(char root,LinkedBinaryTree<T> left,LinkedBinaryTree<T> right)


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);
        int Result = expression.evaluateExpression(tree, tree);
        System.out.println("\n\n the evaluated expression is "+Result);


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>();
        for(int i=0;i<expression.length();i++)
            char e = expression.charAt(i);
                T.attach(T.root, T1, T2);
                    T=new LinkedBinaryTree<>();
        return T;
    public int evaluateExpression(LinkedBinaryTree<T> tree, LinkedBinaryTree<T> v){
            int x = evaluateExpression(tree, v.leftRoot);
            int y = evaluateExpression(tree, v.rightRoot);
            int result =0;
            return result;
                return Integer.parseInt(v.root+"");
    private boolean verifInternalTree(char a) {
            return true;
            return false;

    public void parenthesize(LinkedBinaryTree<T> tree,LinkedBinaryTree<T>p){
        if (verifInternalTree(p.root)){
        else parenthesize(tree, p.leftRoot);
        else    parenthesize(tree, p.rightRoot);