data structures
25 12 17 82 52 53 05 03 68 64 43 27 20 59 04 84 10 42 43 02 81 14 42 21 09 69 05 30 20 91 96 89 75 00 63 24 54 20 20 24 41 62 82 46 69 42 74 68 79 28 50 09 06 44 59 87 32 36 36 46 83 82 43 11 21 04 08 97 93 14 03 60 76 23 14 81 82 00 38 04 09 83 22 90 74 56 64 75 67 55 41 82 53 40 29 84 24 61 87 20 99 37 50 93 57 06 29 91 92 39 25 41 11 88 15 39 88 69 31 49 03 37 97 53 36 54 69 68 38 43 44 27 68 96 70 98 85 13 25 47 51 90 37 86 42 44 48 64 41 01 16 14 27 99 29 99 79 45 59 19 88 56 59 88 39 30 44 59 49 72 49 17 44 32 33 54 60 33 51 87 12 00 68 68 49 68 74 32 09 30 81 30 16 65 40 39 44 49 32 60 CIS2520 Data Structures II Assignment 3 Dr. Charlie Obimbo Due: November 12, 2022 1 Linked Lists 1. (50%) Write a C program that takes as input a fully parenthesized, arithmetic expression of binary operators +,−, ∗, /, and converts the expression into a binary expression tree. Your program should take input from the command line. The entire expression should be in a character string without any space in it. An input string only includes floating numbers in the format of Y.YY, that is, one digit to the left of the decimal point and two digits to the right of the decimal point, and variables of the form of x1, x2, .... Your program shall allow for the leaves in the expression tree not only to store floating values but also to store variables of the form x1, x2, x3, ..., which are initially 0.0 and can be updated interactively by the user. For example, expression (((x1+ 5.12) ∗ (x2− 7.68))/x3) will be converted into a binary expression tree like: / ______|______ | | * x3 ______|______ | | + - ____|____ ____|____ | | | | x1 5.12 x2 7.68 Your program should then show a menu with the following options: 1. Display 2. Preorder 3. Inorder 4. Postorder 5. Update 6. Calculate 7. Exit Description: (a) When option 1 is selected, your program should display the tree in some way so that the tree can be visualized, and also print the name and value of each variable, like “x1:0.0” when x1 initially has value 0.0. 1 (b) If an option of 2, 3 or 4 is selected, your program should print the expression by the cor- responding traversal order (Note: no parentheses for preorder and postorder traversal but fully parenthesized for inorder traversal). (c) Option 5 requires further input from user. A pair of input, namely, variable name, new value will be provided interactively and your program should search for the variable name and replace its value by new value. (d) Arithmetic calculation is invoked by option 6 which shall display the calculation result. Your program should be able to detect an error of divide-by-zero before calculation. (e) Option 7 terminates your program. 2 Heaps 2. (50%) Write a C program. It reads 200 2-digit integers from text file “f.dat” and stores the integers in an array of 20 rows and 10 columns. The program treats each row of the array as an object, with the sum of the first three integers being the key, and the other seven integers being the information content. The program then creates a MAX-HEAP with a node containing an object. You are required to use an array representation of heap, and apply the parental node downheap algorithm in the array representation. The program finally displays the heap as a 20× 10 array, a row for an object. 3 Assignment 3 Guidelines Assignment 3 is due on Nov 12, 2022. Write a makefile that can be used to generate two executables, same as the one for Assignment 2. The information in readme file is the same as before. Other requirements are also the same. Q1 The program for the first question should take input from the command line, same as the second question in Assignment 2. That is, the entire expression should be in a character string without spaces in it. (a) You will need to write a very simple parser to process the input string. (Parsing a string is to analyze its structure and identify the components.) (b) You can parse a string by identifying the nested parenthesis pairs, and the three com- ponents within each pair. (c) Within a pair, there is a binary operator, and a left operand and a right operand. (d) An operand can be a sub-string in a parenthesis pair, a floating number, or a variable. (e) A pair of parentheses can be identified by counting the opening and closing parentheses included by the pair. 2 (f) When creating a tree from a string, you may start with the outer most pair of parenthe- ses, identify the operator of it, create the root node for the operator, and then recursively handle the two operands, which may be a sub-string in an inner pairs of parentheses. (g) To pass an expression as a command line argument, add a \ before each parenthesis. For example, to pass (((1.56+4.26)*(x1-2.23))/x2) to a program, the argu- ment should be \(\(\(1.56+4.26\)*\(x1-2.23\)\)/x2\). Q2 : The 2D array in the second question can be considered as an extension of the 1D array for representing heaps, which we will discuss in classroom. A file of sample data will be provided for your information. Due time: 11:59 pm Nov 12, 2022. 3