Instructions
Requirements and Specifications
Source Code
//ENGR3440 - Data Structures and Algorithms for Engineers
//Spring 2022
//Assignment #5, Implementing and testing Binary Tree Operations
//Dominic Reagle
// Reading string representation of expression tree from file
// Shows preorder, postorder, inorder traverses of the tree
// Calculates solution of the expression (if necessary, prompts user for variable values)
import java.io.File;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.*;
public class Assignment5 {
/**
* Helper method for checking if given string value represents arithmetic operation
* @param value string value to check
* @return true, if value is arithmetic operation - false, otherwise
*/
private static boolean isOperation(String value) {
return "+".equals(value) || "-".equals(value) || "*".equals(value) || "/".equals(value);
}
/**
* Helper method for checking if given string value represents number
* @param value string value to check
* @return Integer object of corresponding number, if value is integer - null, otherwise
*/
private static Integer isNumber(String value) {
try {
return Integer.parseInt(value);
}
catch (NumberFormatException e) {
return null;
}
}
/**
* Interface method for generating preorder view of given linked-list tree
* @param tree linked-list tree to process
* @return node list in preorder traverse
*/
public static List preorder(List tree) {
List result = new LinkedList<>();
preorderStep(0, tree, result);
return result;
}
/**
* Helper method for making preorder traverse recursively
* @param curr current index in tree
* @param tree linked-list tree to process
* @param result intermediate result list
*/
private static void preorderStep(int curr, List tree, List result) {
String value = tree.get(curr);
result.add(value);
if (isOperation(value)) {
preorderStep(2*curr+1, tree, result);
preorderStep(2*curr+2, tree, result);
}
}
/**
* Interface method for generating postorder view of given linked-list tree
* @param tree linked-list tree to process
* @return node list in postorder traverse
*/
public static List postorder(List tree) {
List result = new LinkedList<>();
postorderStep(0, tree, result);
return result;
}
/**
* Helper method for making postorder traverse recursively
* @param curr current index in tree
* @param tree linked-list tree to process
* @param result intermediate result list
*/
private static void postorderStep(int curr, List tree, List result) {
String value = tree.get(curr);
if (isOperation(value)) {
postorderStep(2*curr+1, tree, result);
postorderStep(2*curr+2, tree, result);
}
result.add(value);
}
/**
* Interface method for generating inorder view of given linked-list tree
* @param tree linked-list tree to process
* @return node list in inorder traverse
*/
public static List inorder(List tree) {
List result = new LinkedList<>();
inorderStep(0, tree, result);
return result;
}
/**
* Helper method for making postorder traverse recursively
* @param curr current index in tree
* @param tree linked-list tree to process
* @param result intermediate result list
*/
private static void inorderStep(int curr, List tree, List result) {
String value = tree.get(curr);
if (isOperation(value)) {
inorderStep(2*curr+1, tree, result);
}
result.add(value);
if (isOperation(value)) {
inorderStep(2*curr+2, tree, result);
}
}
/**
* Interface method for creating a linked-list tree with data, read from given file
* @param filename to read daa from
* @return linked list representation of tree
* @throws IOException
*/
public static List createTree(String filename) throws IOException {
List treeList = new LinkedList<>();
// opening file
try(Scanner inputFileScanner = new Scanner(new File(filename))) {
// getting tokens of file content
String[] parts = inputFileScanner.nextLine().split("\\s+");
int counter = 0;
// iterating over all tokens in file
for (String part : parts) {
if (counter > 0) {
// checking if "counter" index must be empty or not.
// if yes, moving until we found next non-empty position
// only "operation" nodes can have children
while(!isOperation(treeList.get((counter - 1) / 2))) {
counter++;
treeList.add(null);
}
}
// adding current token at next position of the result list
counter++;
treeList.add(part);
}
}
return treeList;
}
/**
* Interface method for evaluating given expression tree.
* If necessary, user is asked to set the assignment of variable
* @param tree linked list expression tree to evaluate
* @param scanner scanner object to read assignment with (if necessary)
* @param log writer object to log message about assignment (if necessary)
* @return integer - evaluation result
*/
public static int solveExpression(List tree, Scanner scanner, PrintWriter log) {
// creating map, which will store assignments, already made
Map assignments = new HashMap<>();
// calling recursive method
return solveExpression(0, tree, assignments, scanner, log);
}
/**
* Helper recursive method for evaluating expression tree
* @param curr current index in tree
* @param tree linked list expression tree to evaluate
* @param assignments assignment map
* @param scanner scanner object to read assignment with (if necessary)
* @param log writer object to log message about assignment (if necessary)
* @return integer - evaluation result of current node
*/
private static int solveExpression(int curr, List tree, Map assignments,
Scanner scanner, PrintWriter log) {
String value = tree.get(curr);
if (isOperation(value)) {
// if value is operation - evaluating node as an arithmetic result of left and right branches
int left = solveExpression(2*curr+1, tree, assignments, scanner, log);
int right = solveExpression(2*curr+2, tree, assignments, scanner, log);
switch (value) {
case "+":
return left + right;
case "-":
return left - right;
case "*":
return left * right;
case "/":
return left / right;
default:
throw new IllegalStateException();
}
}
// if value is number, evaluating node as this number
Integer number = isNumber(value);
if (number != null) {
return number;
}
// if value is variable, trying to get its assignment from map
if (assignments.containsKey(value)) {
return assignments.get(value);
}
// if there is no assignment for variable, asking user for the new assignment
int newAssignment = getAssignment(value, scanner, log);
assignments.put(value, newAssignment);
return newAssignment;
}
/**
* Method for getting string representation of the list
* @param list of strings to build representation for
* @return String value
*/
private static String listToString(List list) {
return String.join(" ", list);
}
/**
* Helper method for asking user for new assignment of given variable
* @param var variable to get assignment for
* @param scanner scanner object to read assignment with
* @param log writer object to log message about assignment
* @return integer - new assignment for given variable
*/
private static int getAssignment(String var, Scanner scanner, PrintWriter log) {
System.out.print("Please, enter value for variable " + var + ": ");
int assignment = Integer.parseInt(scanner.nextLine());
log(log, "Variable " + var + " was assigned to value: " + assignment);
return assignment;
}
/**
* Method for logging any message during program execution
* @param printWriter writer object to print message to
* @param message to log
*/
private static void log(PrintWriter printWriter, String message) {
// duplicating message to print writer and to console
System.out.println(message);
printWriter.println(message);
}
public static void main(String[] args) throws IOException {
Scanner scanner = new Scanner(System.in);
// reading input file
System.out.print("Enter file name: ");
String filename = scanner.nextLine();
// creating tree
List tree = createTree(filename);
// creating output file
PrintWriter printWriter = new PrintWriter("output.txt");
// processing created tree
log(printWriter, "Original tree list: " + listToString(tree));
log(printWriter, "Preorder: " + listToString(preorder(tree)));
log(printWriter, "Postorder: " + listToString(postorder(tree)));
log(printWriter, "Inorder: " + listToString(inorder(tree)));
log(printWriter, "Answer: " + solveExpression(tree, scanner, printWriter));
printWriter.close();
}
}