Description

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.
3. Every close bracket has a corresponding open bracket of the same type.
 

Example 1:

Input: s = "()"

Output: true

Example 2:

Input: s = "()[]{}"

Output: true

Example 3:

Input: s = "(]"

Output: false

Example 4:

Input: s = "([])"

Output: true

 

Constraints:

1 <= s.length <= 10^4
s consists of parentheses only '()[]{}'.

Answer & Explaining

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

// 定義一個堆疊(LIFO)
typedef struct {
    char *data;     // 指向堆疊資料的指標
    int top;        // 堆疊頂端索引
    int capacity;   // 堆疊容量
} Stack;

// 初始化堆疊
Stack* createStack(int capacity) {
    //用malloc分配一塊空間為sizeof(Stack)
    Stack *stack = (Stack*)malloc(sizeof(Stack));
    //指向字元的陣列被分配到capacity * sizeof(char)的空間
    stack->data = (char*)malloc(capacity * sizeof(char));
    stack->top = -1;//初始化stack的top
    stack->capacity = capacity;//stack的最大容積為capacity
    return stack;
}

// push函數
void push(Stack *stack, char ch) {
    //如果目前元素(指向頂端)等於最後一個元素(capacity-1)
    if (stack->top == stack->capacity - 1) {
        stack->capacity *= 2;//將容積擴展一倍
        //將data重新分配(reallocate)到新的空間，並重新分配記憶體空間
        stack->data = (char*)realloc(stack->data, stack->capacity * sizeof(char));
    }
    //未滿的情況
    stack->data[++stack->top] = ch;//將下一個stack位置指向top並push char
}

// pop函數
char pop(Stack *stack) {
    if (stack->top == -1) {
        return '\0'; // stack為空時返回空字元
    }
    //非空情況
    return stack->data[stack->top--];//返回data元素並且stack指標向top的前一個
}

// 獲取堆疊頂端元素
char peek(Stack *stack) {
    if (stack->top == -1) { 
        return '\0'; // 堆疊為空時返回空字元
    }
    return stack->data[stack->top];//獲取top元素
}

// 釋放堆疊的記憶體
void freeStack(Stack *stack) {
    free(stack->data);
    free(stack);
}

// 判斷括號字串是否有效
bool isValid(char *s) {
    int len = strlen(s);//字串長度
    Stack *stack = createStack(len);//創造一個大小為len的stack

    for (int i = 0; i < len; i++) {
        char ch = s[i];
        if (ch == '(' || ch == '[' || ch == '{') {
            push(stack, ch);//當不是左括號時，push
        } else { //是左括號時
            char top = peek(stack);//取出top
            //如果是右括號
            if ((ch == ')' && top == '(') || 
                (ch == ']' && top == '[') || 
                (ch == '}' && top == '{')) {
                pop(stack);//從stack中pop出
            } else {
                freeStack(stack);//釋放空間
                return false;//回傳失敗
            }
        }
    }

    bool isValid = (stack->top == -1);//stack為空
    freeStack(stack);//釋放空間
    return isValid;//回傳結果
}

Testing

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

typedef struct {
    char *data;     
    int top;        
    int capacity;   
} Stack;

Stack* createStack(int capacity) {
    Stack *stack = (Stack*)malloc(sizeof(Stack));
    stack->data = (char*)malloc(capacity * sizeof(char));
    stack->top = -1;
    stack->capacity = capacity;
    return stack;
}

void push(Stack *stack, char ch) {
    if (stack->top == stack->capacity - 1) {
        stack->capacity *= 2;
        stack->data = (char*)realloc(stack->data, stack->capacity * sizeof(char));
    }
    stack->data[++stack->top] = ch;
}

char pop(Stack *stack) {
    if (stack->top == -1) {
        return '\0'; // 堆疊為空時返回空字元
    }
    return stack->data[stack->top--];
}

char peek(Stack *stack) {
    if (stack->top == -1) {
        return '\0'; // 堆疊為空時返回空字元
    }
    return stack->data[stack->top];
}

void freeStack(Stack *stack) {
    free(stack->data);
    free(stack);
}

bool isValid(char *s) {
    int len = strlen(s);
    Stack *stack = createStack(len);

    for (int i = 0; i < len; i++) {
        char ch = s[i];
        if (ch == '(' || ch == '[' || ch == '{') {
            push(stack, ch);
        } else {
            char top = peek(stack);
            if ((ch == ')' && top == '(') || 
                (ch == ']' && top == '[') || 
                (ch == '}' && top == '{')) {
                pop(stack);
            } else {
                freeStack(stack);
                return false;
            }
        }
    }

    bool isValid = (stack->top == -1);
    freeStack(stack);
    return isValid;
}

// 測試函數
void test(char *s, bool expected) {
    bool result = isValid(s);
    printf("Input: %s\n", s);
    printf("Output: %s\n", result ? "true" : "false");
    printf("Expected: %s\n", expected ? "true" : "false");
    printf("%s\n\n", result == expected ? "Test passed." : "Test failed.");
}

int main() {
    test("()", true);
    test("()[]{}", true);
    test("(]", false);
    test("([])", true);
    test("{[]}", true);
    test("{[()]}", true);
    test("{[(])}", false);

    return 0;
}