XXXXXXXXXX XXXXXXXXXX
XXXXXXXXXX XXXXXXXXXX
XXXXXXXXXX XXXXXXXXXX
XXXXXXXXXX XXXXXXXXXX
XXXXXXXXXX XXXXXXXXXX
XXXXXXXXXX XXXXXXXXXX
XXXXXXXXXX XXXXXXXXXX
XXXXXXXXXX XXXXXXXXXX
XXXXXXXXXX XXXXXXXXXX
XXXXXXXXXX XXXXXXXXXX
XXXXXXXXXX XXXXXXXXXX
XXXXXXXXXX XXXXXXXXXX
XXXXXXXXXX XXXXXXXXXX
XXXXXXXXXX XXXXXXXXXX
XXXXXXXXXX XXXXXXXXXX
XXXXXXXXXX XXXXXXXXXX
XXXXXXXXXX XXXXXXXXXX
XXXXXXXXXX XXXXXXXXXX
XXXXXXXXXX XXXXXXXXXX
XXXXXXXXXX XXXXXXXXXX
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
inary operators +,−, ∗, /, and converts the expression into a binary expression tree. You
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. Preorde
3. Inorde
4. Postorde
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-
esponding traversal order (Note: no parentheses for preorder and postorder traversal
ut 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 e
or 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 a
ay of 20 rows and 10 columns.
The program treats each row of the a
ay as an object, with the sum of the first three integers
eing 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 a
ay representation of heap, and apply the parental node downheap algorithm in
the a
ay representation. The program finally displays the heap as a 20× 10 a
ay, a row fo
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 characte
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 XXXXXXXXXX)*(x1-2.23))/x2) to a program, the argu-
ment should be XXXXXXXXXX\)*\(x1-2.23\)\)/x2\).
Q2 : The 2D a
ay in the second question can be considered as an extension of the 1D a
ay fo
epresenting 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