$29
CS513 DS LAB 1 (6/AUG/22)
Q1.) Given a input file containing the characters '(', ')', '{', '}' , '[' , ']' , and several other, read the input file (input.txt)
and determine if the input file is having valid Parentheses or not. (40 points)
(Note: read file name using command line argument )
An input file is valid if:
Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Example 1:
Input:
Output:
Input file is valid
#include<stdio.h>
Int main( )
Explaination:
{
As the input file contains parantheses in correct order
int a[2];
and opening and closing of brackets are same :<> ( ){ {} }
for(int i=0;i<2;i++)
{
a[i] = i;
}
return 0;
}
Example 2:
Input file:
Output:
class S
Input file is invalid
{
Explaination:
public:
int reverse(int x // ‘)’ is missing
It is invalid because at line no. 4 ‘)’ do not have the same
{
closing bracket and at line 20 do not have same closing
int y=0;
int a[10];
bracket for ‘{ ‘ at line 9.
while(x)
{
if(y>INT_MAX/10 || y<INT_MIN/10)
{
return 0;
}
else
{
y=y*10 +x%10;
x=x/10;
}
)
return y;
}
};
Q2.)Implement set using link list, you have to perform all the below task through function call. The tasks are –(60 points)
1.int makeSet(struct Set *SetA), [To make a head of the link list]
2. int insert (struct Set *SetA, int value), [To insert value ‘d’ in set ‘S’ , if not exist] (8 points)
3. int delete (struct Set *SetA, int value), [To delete value ‘d’ from set ‘S’ if it exists ] (8 points)
4. int printSet (struct Set *SetA), [To print the values of set] (6 points)
5. int Union (struct Set *SetA, struct Set *SetB, struct Set *SetC), [To perform union between two sets S1, S2 and return another set](10 points)
6. int intersection (struct Set *SetA, struct Set *SetB, struct Set *SetC), [To perform intersection between two sets S1,
S2 and return another set] (10 points)
7. int difference(struct Set *SetA, struct Set *SetB, struct Set *SetC), [to perform set difference S1 - S2 and] (10 points)
8. int deleteSet (struct Set *SetA), [To perform delete a set] (8 points)
Note:- Return 1 for successfully call the function, otherwise 0.
Partial code:-
#include<stdio.h>
struct Set
{
int value;
struct Set* next;
};
int makeSet(struct Set *SetA){
//Write your code
}
int insert (struct Set *SetA, int value){ // insert value in the SetA if it is not exist and return 1, otherwise return 0
//Write your code
}
int delete (struct Set *SetA, int value){ // delete value from SetA if it is exist and return 1, otherwise return 0,
//Write your code
}
int printSet (struct Set *SetA){ //Print all the element of the SetA, where SetA is headpointer of link list
//Write your code
}
int Union (struct Set *SetA, struct Set *SetB, struct Set *SetC){ // To perform union between two sets SetA, SatB and //store the result in SetC, , where SetA,SetB,SetC is the head pointer of the link list
//Write your code
}
int intersection (struct Set *SetA, struct Set *SetB){ // To perform intersection between two sets SetA, SatB and //store the result in SetC, , where SetA,SetB,SetC is the head pointer of the link list
//Write your code
}
int difference(struct Set *SetB, struct Set *SetB// To perform difference between two sets SetA, SatB and store the //result in SetC, where SetA,SetB,SetC is the head pointer of the link list
//Write your code
}
int deleteSet(struct Set *SetA){ //Take headpointer of link list SetA and delete all the node from heap.
//Write your code
}
int main(){
// Read text file
//Call accordingly each function
//For each line, first number represent the operation, and remaining are parameter
}
