Implement Data Structures and Algorithm in Python Assignment Solution
.webp)
- Instructions
- Objective
- Requirements and Specifications
Instructions
Objective
Write a python homework to implement data structures and algorithm.
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();
}
}
Similar Samples
Dive into our curated collection of programming assignment samples at ProgrammingHomeworkHelp.com. Explore practical solutions across various programming languages and topics, showcasing our expertise in algorithms, data structures, and application development. Each sample reflects our commitment to delivering high-quality, tailored assistance for your academic needs. Discover how our solutions can guide you towards mastering programming concepts and achieving academic success.
Python
Python
Python
Python
Python
Python
Python
Python
Python
Python
Python
Python
Python
Python
Python
Python
Python
Python
Python
Python