Problem: Validate Parentheses String

Goal:
Determine if a string consisting of characters (), [], and {} is valid. A string is considered valid if:

• Every open bracket is closed by the same type of bracket.
• Open brackets must be closed in the correct order.

Steps:

1. Use a stack to keep track of the opening brackets.
2. When encountering a closing bracket, check if it matches the most recent opening bracket (the top of the stack).
3. If at any point the brackets do not match, or if a closing bracket is encountered without a corresponding opening bracket, return false.
4. If all brackets are matched and the stack is empty at the end, return true.

Solution:

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

#define MAX_SIZE 100

// Stack structure to keep track of opening brackets
typedef struct {
    char data[MAX_SIZE];
    int top;
} Stack;

// Initialize stack
void init(Stack *stack) {
    stack->top = -1;
}

// Push element onto the stack
void push(Stack *stack, char value) {
    if (stack->top < MAX_SIZE - 1) {
        stack->data[++stack->top] = value;
    } else {
        printf("Stack Overflown");
    }
}

// Pop element from the stack
char pop(Stack *stack) {
    if (stack->top >= 0) {
        return stack->data[stack->top--];
    } else {
        printf("Stack Underflown");
        return '';
    }
}

// Function to validate the string of brackets
bool isValid(char *s) {
    Stack stack;
    init(&stack);

    while (*s) {
        // Push open brackets onto the stack
        if (*s == '(' || *s == '[' || *s == '{') {
            push(&stack, *s);
        } 
        // Check for matching closing brackets
        else if (*s == ')' || *s == ']' || *s == '}') {
            if (stack.top == -1) {
                return false;  // No opening bracket for this closing one
            }

            char top = pop(&stack);
            // Check if the top of the stack matches the closing bracket
            if ((*s == ')' && top != '(') ||
                (*s == ']' && top != '[') ||
                (*s == '}' && top != '{')) {
                return false;  // Mismatched brackets
            }
        }
        s++;
    }

    // If stack is empty, all brackets matched
    return stack.top == -1;
}

int main() {
    char exp[] = "({[]})";  // Example input
    if (isValid(exp)) {
        printf("Validn");
    } else {
        printf("Invalidn");
    }

    return 0;
}

Explanation:

1. Stack Structure:

   • The Stack structure holds an array data to store characters and an integer top to track the top index of the stack.

2. Functions:

   • init(): Initializes the stack by setting top to -1.
   • push(): Adds a character to the top of the stack.
   • pop(): Removes and returns the top character of the stack.

3. Main Validation Logic:

   • Open Brackets: Whenever an open bracket ((, [, or {) is encountered, it’s pushed onto the stack.
   • Close Brackets: When a close bracket (), ], or }) is encountered:
     • If the stack is empty, it means there’s no matching open bracket, so return false.
     • If the stack is not empty, pop the top element and check if it matches the corresponding opening bracket for the current closing one.
     • If there’s a mismatch, return false.
   • Final Check: After processing the string, if the stack is empty, it means all brackets were properly matched and closed. Otherwise, return false.

Example Output:

1. Input: ()
   • Output: Valid
2. Input: ()[]{}
   • Output: Valid
3. Input: (]
   • Output: Invalid
4. Input: ([])
   • Output: Valid

Time Complexity:

• Time complexity: O(n), where n is the length of the string. We go through the string once and perform constant time operations (push/pop) for each character.

Space Complexity:

• Space complexity: O(n), due to the stack storing up to n characters in the worst case.

This solution efficiently handles the problem using a stack to track matching brackets and ensure the correct order and type.