# Implement Data Structures and Algorithm in Python Assignment Solution.

## Instructions

Objective
Write a program to implement data structures and algorithm in python.

## 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<String> preorder(List<String> tree) {         List<String> 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<String> tree, List<String> 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<String> postorder(List<String> tree) {         List<String> 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<String> tree, List<String> 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<String> inorder(List<String> tree) {         List<String> 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<String> tree, List<String> 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<String> createTree(String filename) throws IOException {         List<String> 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<String> tree, Scanner scanner, PrintWriter log) {         // creating map, which will store assignments, already made         Map<String, Integer> 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<String> tree, Map<String, Integer> 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<String> 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<String> 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();     } }```