Assignment #1: Sorting with Binary Search Tree Through this programming assignme
ID: 3754881 • 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 VO. 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 l-cl 1-o output-file-name] [input-file-name] if -c is present, the program needs to compare the strings case sensitive; otherwise, its case insensitive. if the output file name is given with the -o option, the program will output the sorted lines to the given output file; otherwise, the output shall be the standard output. Similarly, if the input file name is given, the program wllread 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. in addition to parsing and processing the command line arguments, your program needs to do the following:Explanation / Answer
PROGRAM:
c++ code:-
#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;
}
hello
good
boy
dude
dude
./a.out sampleInput.txt
boy
dude
dude
good
hello