Valid Parentheses - C Solution

1. Introduction

In this post, we tackle a classic problem in stack-based data structures, known as "Valid Parentheses". The challenge is to determine if a string containing various types of brackets is valid based on the rules of bracket closure. This problem is a great exercise in understanding stack operations and string processing in C.

Problem

Given a string s containing characters '(', ')', '{', '}', '[' and ']', the task is to determine if the input string is valid. A string is valid if open brackets are closed by the same type of brackets, the brackets are closed in the correct order, and every close bracket has a corresponding open bracket of the same type.

2. Solution Steps

1. Initialize a stack data structure.

2. Iterate through each character in the string s.

3. If an open bracket is encountered, push it onto the stack.

4. If a closing bracket is encountered, check if it matches the top element of the stack.

5. If it matches, pop the top element from the stack. Otherwise, the string is invalid.

6. After processing all characters, check if the stack is empty.

7. Return true if the stack is empty (valid string), otherwise return false.

3. Code Program

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

// Function to check if the string has valid parentheses
int isValid(char* s) {
    int n = strlen(s);
    char* stack = (char*)malloc(n * sizeof(char));
    int top = -1;

    for (int i = 0; i < n; i++) {
        if (s[i] == '(' || s[i] == '{' || s[i] == '[') {
            stack[++top] = s[i]; // Push to stack
        } else {
            if (top == -1) return 0; // Stack is empty, invalid string
            char c = stack[top--]; // Pop from stack
            if ((s[i] == ')' && c != '(') || (s[i] == '}' && c != '{') || (s[i] == ']' && c != '[')) {
                return 0; // Mismatched parentheses
            }
        }
    }
    free(stack);
    return top == -1; // Valid if stack is empty
}

// Main function to test the isValid function
int main() {
    char s1[] = "()";
    printf("Is Valid (Example 1): %s\n", isValid(s1) ? "true" : "false");

    char s2[] = "()[]{}";
    printf("Is Valid (Example 2): %s\n", isValid(s2) ? "true" : "false");

    char s3[] = "(]";
    printf("Is Valid (Example 3): %s\n", isValid(s3) ? "true" : "false");

    return 0;
}

Output:

Is Valid (Example 1): true
Is Valid (Example 2): true
Is Valid (Example 3): false

Explanation:

1. A stack is used to keep track of the opening brackets.

2. For each closing bracket, the function checks if it correctly matches the last opening bracket on the stack.

3. If any mismatch is found, or the stack is not empty after processing all characters, the string is invalid.

4. The main function tests isValid with three different strings and prints whether they are valid.