Kiểm tra chuỗi chứa có ký tự đóng mở ngoặc có hợp lệ?

Cho một chuỗi có thể chứa các ký tự đóng mở ngoặc '[', ']', '(', ')', '{', '}', '<', '>' hãy viết thuật toán kiểm tra xem chuỗi có hợp lệ hay không hợp lệ.

Ví dụ hợp quy:

1. Ký tự đóng mở ngoặc luôn đi theo cặp. Đã có mở, phải có đóng. Hello [World] {This is C}
2. Ký tự đóng mở phải nằm trong nhau, chứ không mở, đóng chen ngang. {Hello [World] this is C}
3. [[Hello World ()]]{There is something else}

Ví dụ phạm quy:

1. Có mở nhưng không có đóng Hello [ World)
2. Ký tự đóng mở giằng lên nhau Hello [ World (] This is C)

Phân tích

Chuỗi hợp quy khi:

• Số lượng, kiểu ngoặc mở phải bằng số lượng, kiểu ngoặc đóng
• Ngoặc không chứa cặp ngoặc khác thì cặp mở và đóng có thể tự cân bằng lẫn nhau.
• Nếu cặp ngoặc bao trọn vẹn môt cặp ngoặc con, rồi cặp ngoặc con chứa cặp ngon nữa bên trong, thì ta lần lượt cân băng cặp ngoặc trong cùng, sau đó ra cặp ngoặc bao kế tiếp, rồi cặp kế tiếp cho đến cặp ngoài cùng.

Thuật toán

Chúng ta sẽ sử dụng cấu trúc dữ liệu dạng stack để quan sát các dấu mở, đóng ngoặc chạy từ đầu (trái) đến cuối (phải) của chuỗi đầu vào.

Khi gặp một ký tự nếu nó nằm trong tập các ký tự đóng mở ngoặc thì sẽ kiểm tra tiếp, nó có cân bằng (đóng lại) ký tự ngoặc mở ngay trước đó. Nếu nó đóng được thì ta không thêm nó vào stack đồng thời loại bỏ ngoặc mở ngay trước đó. Tiếp tục cho đến khi chạy đến cuối mảng ký tự, nếu stack cân bằng được hết nó sẽ rỗng, còn nó không cân bằng được thì nó sẽ còn các ngoặc dôi dư.

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

int checkHopQuy(char *string);

int main() {
    char string1[] = "a[b]c";
    char string2[] = "} abc {";
    char string3[] = "<ok string [good]>";
    char string4[] = "DEF ]<>";
    char string5[] = "Open but not close (///";
    char string6[] = "a[b[c<def>m{n]pq}]()";

    //printf("string1: %d\n", checkHopQuy(string1));
    //printf("string2: %d\n", checkHopQuy(string2));
    //printf("string3: %d\n", checkHopQuy(string3));
    //printf("string4: %d\n", checkHopQuy(string4));
    printf("string6: %d\n", checkHopQuy(string6));
    return 0;
}

/*
return 1 if c is one of parentheses else return 0
*/
int isCharIsParenthese(char c) {
    char *parentheses = "[]<>(){}";
    for (int i = 0; i < strlen(parentheses); i++) {
        if (c == parentheses[i]) {
            return 1;
        }
    }

    return 0;
}

/*
char a left size character
char b right size character
return 1 if a matches b else return 0
*/

int isTwoCharsMatching(char a, char b) {
    if (
            (a == '[' && b == ']') ||
            (a == '<' && b == '>') ||
            (a == '{' && b == '}') ||
            (a == '(' && b == ')')
            ) {
        return 1;
    }
    return 0;
}

int checkHopQuy(char *string) {
    char *stack = malloc(100 * sizeof(char));
    memset(stack, 0, 100);
    int k = 0; //k is stack counter

    for (int i = 0; i < strlen(string); i++) {
        if (isCharIsParenthese(string[i])) {
            if (k > 0 && isTwoCharsMatching(stack[k - 1], string[i])) {
                k = k - 1;
            } else {
                stack[k] = string[i];
                k = k + 1;
            }
        }
    }

    free(stack);
    if (k > 0) {
        return 0; //stack is not empty
    } else {
        return 1;
    }

}