ass2.c

/*
Certainly, I can provide you with a solution to the Valid Parentheses Problem in C programming language, along with a report explaining the implementation, thought process, and complexity analysis. Let's start with the code implementation:
*/

#include <stdio.h>
#include <stdbool.h>
#include <string.h>

// Structure to represent a stack
struct Stack {
    char data[100];
    int top;
};

// Function to initialize an empty stack
void initStack(struct Stack* s) {
    s->top = -1;
}

// Function to push an element onto the stack
void push(struct Stack* s, char c) {
    s->data[++s->top] = c;
}

// Function to pop an element from the stack
char pop(struct Stack* s) {
    if (s->top == -1) {
        return '\0';
    }
    return s->data[s->top--];
}

// Function to check if a character is an opening parenthesis
bool isOpening(char c) {
    return (c == '(' || c == '{' || c == '[');
}

// Function to check if a character is a closing parenthesis
bool isClosing(char c) {
    return (c == ')' || c == '}' || c == ']');
}

// Function to check if two characters form a valid pair of parentheses
bool isValidPair(char open, char close) {
    return (open == '(' && close == ')') ||
           (open == '{' && close == '}') ||
           (open == '[' && close == ']');
}

// Function to check the validity of parentheses in a string
bool isValidParentheses(char* str) {
    struct Stack stack;
    initStack(&stack);

    int len = strlen(str);
    for (int i = 0; i < len; i++) {
        char current = str[i];
        if (isOpening(current)) {
            push(&stack, current);
        } else if (isClosing(current)) {
            if (stack.top == -1 || !isValidPair(stack.data[stack.top], current)) {
                return false;  // Unmatched or invalid pair
            } else {
                pop(&stack);
            }
        }
    }

    return (stack.top == -1);  // Stack should be empty if all parentheses are matched.
}

int main() {
    char input[100];
    printf("Enter a string with parentheses: ");
    scanf("%s", input);

    if (isValidParentheses(input)) {
        printf("Valid parentheses\n");
    } else {
        printf("Invalid parentheses\n");
    }

    return 0;
}

/*
Now, let's provide a report explaining the implementation, thought process, and complexity analysis:

Implementation:

We have implemented a C program to check the validity of parentheses in a given string. The program uses a stack data structure to keep track of opening brackets and ensures that closing brackets match the most recent opening bracket.

Thought Process
To solve this problem, we use a stack to keep track of the opening parentheses encountered. Whenever we encounter a closing parenthesis, we check if it matches the most recently encountered opening parenthesis. If it does, we pop the opening parenthesis from the stack; otherwise, the parentheses are not valid. The string is considered valid if the stack is empty at the end.

Algorithm
Initialize an empty stack to store opening parentheses.
Iterate through the input string character by character.
If the current character is an opening parenthesis ('(', '{', '['), push it onto the stack.
If the current character is a closing parenthesis (')', '}', ']'), check if it matches the opening parenthesis at the top of the stack. If it does, pop the opening parenthesis from the stack. If not, the parentheses are not valid.
After processing the entire string, if the stack is empty, the parentheses are valid; otherwise, they are not.

Complexity Analysis
Time Complexity:

The algorithm iterates through the input string once, which takes O(n) time, where n is the length of the input string.
Each character is pushed and popped from the stack at most once, so the push and pop operations are also O(n) in total.
Therefore, the overall time complexity of the algorithm is O(n).
Space Complexity:

The space used by the stack is proportional to the maximum nesting depth of the parentheses in the input string.
In the worst case, when all parentheses are properly nested, the stack's space complexity is O(n).
Therefore, the overall space complexity of the algorithm is O(n).

The space complexity depends on the maximum nesting depth, which means that even in the worst case, the space used by the stack is proportional to the length of the input string.
The algorithm's time and space complexity are both linear, making it an efficient and effective way to solve the Valid Parentheses Problem.

Testing
You should test the program with various input strings, including valid and invalid cases, to ensure it works as expected. For example:

Input: "{[()]}", Output: Valid parentheses
Input: "{[()}", Output: Invalid parentheses
Input: "()", Output: Valid parentheses
Input: "(a+b)", Output: Valid parentheses
Input: "[[[]]]", Output: Valid parentheses
Input: "(()])", Output: Invalid parentheses
Input: "abc", Output: Valid parentheses

Conclusion
In conclusion, the program efficiently solves the Valid Parentheses Problem by using a stack to ensure that not only are the parentheses correctly ordered, but they are also correctly nested. The algorithm's time and space complexities are both O(n), where n is the length of the input string, making it a practical solution for this problem. The code and the report provide a comprehensive understanding of how the problem was approached and solved in C.

*/