Assignment #1: Sorting with Binary Search Tree Through this programming assignme
ID: 3722885 • Letter: A
Question
Assignment #1: Sorting with Binary Search Tree Through this programming assignment, the students will learn to do the following: 1. Know how to process command line arguments. 2. Perform basic file I/O. 3. Use structs, pointers, and strings. 4. Use dynamic memory. This assignment asks you to sort the lines of an input file (or from standard input) and print the sorted lines to an output file (or standard output). Your program, called bstsort (binary search tree sort), will take the following command line arguments: % bstsort [-c] [-o output-file-name] [input file-name] If-c is present, the program needs to compare the strings case sensitive; otherwise, it's case insensitive. If the output_file_name is given with the -o option, the program will output the sorted ines to the given output file; otherwise, the output shall be the standard output. Similarly, if the input_file_name is given, the program will read from the input file; otherwise, the input will be from the standard input. You must use getopt() to parse the command line arguments to determine the cases. All strings will be no more than 100 characters long.Explanation / Answer
C PROGRAMME :
#include <string.h>
#include <stdbool.h>
#include <getopt.h>
#include <unistd.h>
#include <stdlib.h>
#include <stdio.h>
typedef struct Node{
char* key;
int value;
struct Node* left;
struct Node* right;
}Node;
void removeEnterLine(char* line){
char* ptr=&(line[0]);
while(ptr!=NULL){
if((*ptr)==' '){
*ptr='';
break;
}
ptr++;
}
}
int strcmpCaseSensitive(char str1,char str2){
char* ptr1=str1;
char* ptr2=str2;
while(ptr1!='' && ptr2!=''){
if((*ptr1)>(*ptr2))
return 1;
else if((*ptr1)<(*ptr2))
return -1;
ptr1++;
ptr2++;
}
if(ptr1=='' && ptr2=='')
return 0;
else if(ptr1=='')
return -1;
else
return 1;
}
int strcmpCaseInsensitive(char str1,char str2){
char* ptr1=str1;
char* ptr2=str2;
while(ptr1!='' && ptr2!=''){
char ch1=*ptr1;
char ch2=*ptr2;
ch1=tolower(ch1);
ch2=tolower(ch2);
if(ch1>ch2)
return 1;
else if(ch1<ch2)
return -1;
ptr1++;
ptr2++;
}
if(ptr1=='' && ptr2==''){
return 0;
}
else if(ptr1=='')
return -1;
else
return 1;
}
int compareStrings(char str1,char str2,bool caseSensitive){
if(caseSensitive==true){
return strcmpCaseSensitive(str1,str2);
}else{
return strcmpCaseInsensitive(str1,str2);
}
}
void insert(char tmp,Node root,bool caseSensitive){
Node* temp=root;
Node* parent=NULL;
while(temp!=NULL){
if(compareStrings(temp->key,tmp,caseSensitive)==0){
temp->value=temp->value+1;
return;
}else if(compareStrings(temp->key,tmp,caseSensitive)>0){
parent=temp;
temp=temp->left;
}else{
parent=temp;
temp=temp->right;
}
}
Node* newest=(Node*)malloc(sizeof(Node)*1);
newest->left=NULL;
newest->right=NULL;
newest->key=tmp;
newest->value=1;
if(compareStrings(parent->key,tmp,caseSensitive)>0){
//printf("left ");
parent->left=newest;
}else{
//printf("right ");
parent->right=newest;
}
}
void inorder(Node* root){
if(root==NULL)
return;
inorder(root->left);
int i;
for(i=1;i<=root->value;i++)
printf("%s ", root->key);
inorder(root->right);
}
int main(int argc,char** argv){
bool caseSensitive=false;
char* output="";
char* input="";
int c;
while((c=getopt(argc,argv,"co:"))!=-1){
switch(c){
case 'c':
caseSensitive=true;
break;
case 'o':
output=optarg;
break;
}
}
int size=100000;
char** arr=(char**)(malloc(sizeof(char*)*size));
int index;
for (index = optind; index < argc; index++){
input=argv[index];
}
int ind=0;
if(strcmp(input,"")==0){ //std input
size_t line_size;
printf("Enter strings line by line ");
char* line=(char*)malloc(sizeof(char)*100);
while(getline(&line,&line_size,stdin)!=-1){
if(strcmp(line," ")==0)
break;
removeEnterLine(line);
arr[ind++]=line;
line=(char*)malloc(sizeof(char)*100);
}
}else{
FILE *file = fopen(input, "r");
char* line=(char*)malloc(sizeof(char)*100);
size_t line_size;
while(getline(&line,&line_size,file)!=-1){
removeEnterLine(line);
arr[ind++]=line;
line=(char*)malloc(sizeof(char)*100);
}
}
int j;
// for(j=0;j<ind;j++)
// printf("%s ", arr[j]);
int sizeTree=0;
Node* root;
for(j=0;j<ind;j++){
char* tmp=arr[j];
if(sizeTree==0){
Node* newest=(Node*)malloc(sizeof(Node)*1);
newest->key=tmp;
newest->value=1;
newest->left=NULL;
newest->right=NULL;
root=newest;
}else{
insert(tmp,root,caseSensitive);
}
sizeTree++;
}
inorder(root);
return 0;
}
SAMPLE INPUT :
hello
good
boy
dude
dude
SAMPLE OUTPUT :
boy
dude
dude
good
hello