Time limit: 5000ms
Memory limit: 256mb
Description:
This problem is related to Correcting Brackets 2024 (Required). Given a sequence A that consists of 4 characters '(', ')', '[', ']', we say that A is valid if:
1. If there is a '(' followed by a ')' or a '[' followed by a ']', we can delete them together from the sequence. Repeat this procedure until there is nothing to delete.
2. Finally, if the remaining sequence is empty, we say the original sequence is valid; otherwise, the original sequence is invalid.
For example, ([][()]) is valid, and ([)] is not.
John, a CS undergraduate, is typing bracket sequences using these 4 bracket characters. However, he makes a mistake which makes the sequence invalid. He knows that he added one extra bracket at exactly one position, but he is not sure where the mistake is. In this exercise, we will help John correct his sequence, with the help of a stack. We will list all the possible sequences that John intended to write.
The input consists of a positive integer n, which is the number of characters in the bracket sequence John wrote, and the bracket sequence. Each line of the output is a possible corrected sequence that is valid.
You are required to complete the following function:
void findAllPossibleSeqs(char A[], int A_len, int curr_pos, Boolean mistake_found, Stack* stack_holder, char* curr_seq);
- The input sequence of characters is stored in A[] with length A_len.
- stack_holder holds stack for checking the validity of a bracketting sequence.
- mistake_found denotes if the mistake is found from position 1 to current position (curr_pos).
- A sequence is stored in curr_seq. If it is a valid one after correcting the mistake, it is added to the global variable possible_seqs.
- possible_seqs stores a set of unique sequences.
A stack ADT is already implemented in the template.
Sample Input 1:
5
(()()
Sample Output 1:
Input the number of characters in the sequence:
Input these characters:
All possible sequences:
(())
()()
Sample Input 2:
5
[[]]]
Sample Output 2:
Input the number of characters in the sequence:
Input these characters:
All possible sequences:
[[]]
Sample Input 3:
3
]()
Sample Output 3:
Input the number of characters in the sequence:
Input these characters:
All possible sequences:
()
-------------------------Copy the following code, complete it and submit-------------------------
/*
I, <Your Full Name>, am submitting the assignment for
an individual project.
I declare that the assignment here submitted is original except for
source material explicitly acknowledged, the piece of work, or a part
of the piece of work has not been submitted for more than one purpose
(i.e. to satisfy the requirements in two different courses) without
declaration. I also acknowledge that I am aware of University policy
and regulations on honesty in academic work, and of the disciplinary
guidelines and procedures applicable to breaches of such policy and
regulations, as contained in the University website
http://www.cuhk.edu.hk/policy/academichonesty/.
It is also understood that assignments without a properly signed
declaration by the student concerned will not be graded by the
teacher(s).
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_SEQ_LEN 30
#define MAX_NUM_SEQ 100
typedef enum{FALSE = 0, TRUE = 1} Boolean;
typedef struct{
int size;
int top;
int *stacklist;
} Stack;
Stack *createS(int size){
Stack *s;
s = (Stack*)malloc(sizeof(Stack));
s->size = size;
s->stacklist = (int*)malloc(size * sizeof(int));
s->top = -1;
return s;
}
Boolean isFull(Stack *s){
if (s->top == s->size -1)
return TRUE;
else return FALSE;
}
Boolean isEmpty(Stack *s){
if (s->top == -1)
return TRUE;
else return FALSE;
}
void push(Stack *s, int e){
if (!isFull(s)){
s->top++;
s->stacklist[s->top] = e;
}
}
int pop(Stack *s){
int i;
if (!isEmpty(s)){
i = s-> stacklist[s->top];
s->top--;
return i;
}else{printf("error\n"); return -1;}
}
int top(Stack *s){ return s->stacklist[s->top];}
Boolean isBracket(int character){
if (character == '(' || character == ')' || character == '[' || character == ']') return TRUE;
else return FALSE;
}
int getMatched(int character){
if (character == '(') return ')';
else if (character == '[') return ']';
else if (character == ')') return '(';
else if (character == ']') return '[';
else return -1;
}
typedef struct{
int size;
int top;
int max_seq_len;
char** sequences_list;
} Sequences;
Sequences* createSeqs(int size, int max_seq_len){
Sequences *seqs;
seqs = (Sequences*) malloc(sizeof(Sequences));
seqs->size = size;
seqs->top = 0;
seqs->sequences_list = (char**) malloc(size * sizeof(char*));
seqs->max_seq_len = max_seq_len;
return seqs;
}
Sequences* possible_seqs;
void printSeqs(Sequences* seqs){
int i;
for(i=0; i<seqs->top; i++){
printf ("%s\n", seqs->sequences_list[i]);
}
}
void addToSeqs(Sequences* seqs, char* seq) {
seqs->sequences_list[seqs->top++] = strcpy(malloc(strlen(seq) + 1), seq);
}
void sortSeqs(Sequences* seqs){
char temp[seqs->max_seq_len + 1];
for(int i=0; i<seqs->top; i++){
for(int j=0; j<seqs->top-1-i; j++){
if(strcmp((seqs->sequences_list)[j], (seqs->sequences_list)[j+1]) > 0){
strcpy(temp, (seqs->sequences_list)[j]);
strcpy((seqs->sequences_list)[j], (seqs->sequences_list)[j+1]);
strcpy((seqs->sequences_list)[j+1], temp);
}
}
}
}
void findAllPossibleSeqs(char A[], int A_len, int curr_pos, Boolean mistake_found, Stack* stack_holder, char* curr_seq){
// code here
}
int main(){
char A[MAX_SEQ_LEN];
int A_len;
printf("Input the number of characters in the sequence:\n");
scanf("%d", &A_len);
printf("Input these characters:\n");
scanf("%s", A);
Stack *stack_holder = createS(MAX_SEQ_LEN);
possible_seqs = createSeqs(MAX_NUM_SEQ, MAX_SEQ_LEN);
char* curr_seq = (char*) malloc((A_len + 2) * sizeof(char));
strcpy(curr_seq, "");
findAllPossibleSeqs(A, A_len, 0, FALSE, stack_holder, curr_seq);
sortSeqs(possible_seqs);
printf("All possible sequences:\n");
printSeqs(possible_seqs);
return 0;
}
-------------------------------------------End of Code-------------------------------------------