Time limit: 2000ms
Memory limit: 256mb

Description:

Given a sequence A that consists of 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.

In this exercise, we use a stack to check if a given sequence is valid or not:
1. If it is valid, please output "valid";
2. If it is invalid:
- If you can append a sequence B that consists of '(', ')', '[' or ']' to A to make the whole sequence valid, then please output the shortest possible B;
- If you cannot find such B, please output "invalid".

For example:
1. if A = "([])", then your program should just output a "valid";
2. if A = "([][(", then your program should output ")])";
3. if A = "([)[", then your program should output "invalid".

You can refer page 3-6 in Stacks slides for the implementation of stack, which is already there in the template. To make this work, you need to revise the stack a little bit.

You are required to implement the following function:

char* isValid(char A[], int A_len); 
Given a sequence of characters in A[], initialize a stack_holder to help check if this sequence is valid or not, you may use isMatching(char, char) to check if two characters match.
1. If it is valid, return "valid";
2. If it is invalid:
- If you can append a sequence B that consists of '(', ')', '[' or ']' to A to make the whole sequence valid, return the shortest possible B;
- If you cannot find such B, return "invalid".


Sample Input 1:
12
(()[])[()]()

Sample Output 1:
valid


Sample Input 2:
6
[()[([

Sample Output 2:
])]]


Sample Input 3:
4
([)[

Sample Output 3:
invalid

-------------------------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 100000

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;
    }
}


char pop(stack *s){
    int i;
    if (!IsEmpty(s)){
        i = s-> stacklist[s->top];
        s->top--;
        return i;
    }else{printf("error\n"); return -1;}
}

char top(stack *s){ return s->stacklist[s->top];}


Boolean isMatching(char character1, char character2)
{
    if (character1 == '(' && character2 == ')')
        return TRUE;
    else if (character1 == '[' && character2 == ']')
        return TRUE;
    else
        return FALSE;
}

char* isValid(char A[], int A_len)
{   
    char* output;
    stack *stack_holder = createS(20000);
    // code here

    return output;
}


int main()
{    
    char value;
    char A[MAX];
    int A_len;
    printf("Input the number of chars in A:\n");
    scanf("%d", &A_len);
    printf("Input these chars:\n");
    scanf("%s", A);
    printf("%s\n", isValid(A, A_len));

    return 0;
}

-------------------------------------------End of Code-------------------------------------------