C语言算法-有效的括号

1 题目

2 代码实现

1 字符数组 stack 作为栈来辅助判断括号的有效性，而不直接操作原始字符串。
2 程序通过遍历字符串，每当遇到**左**括号时将其**入栈**，每当遇到**右**括号时与栈顶元素进行匹配，如果匹配成功则出栈。
3 最后，检查栈是否为空，以确定括号是否有效。

// 检查字符串是否有效
bool isValid(char* s) {
    int len = strlen(s);
    
    // 使用栈来匹配括号
    char stack[len];
    int top = -1;

    for (int i = 0; i < len; i++) {
        if (s[i] == '(' || s[i] == '{' || s[i] == '[') {
            stack[++top] = s[i];
        } else if (s[i] == ')' && top != -1 && stack[top] == '(') {
            top--;
        } else if (s[i] == '}' && top != -1 && stack[top] == '{') {
            top--;
        } else if (s[i] == ']' && top != -1 && stack[top] == '[') {
            top--;
        } else {
            return false; // 括号不匹配
        }
    }

    return top == -1; // 如果栈为空，说明括号匹配
}

3 完整测试代码

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

// 检查字符串是否有效
bool isValid(char* s) {
    int len = strlen(s);
    
    // 使用栈来匹配括号
    char stack[len];
    int top = -1;

    for (int i = 0; i < len; i++) {
        if (s[i] == '(' || s[i] == '{' || s[i] == '[') {
            stack[++top] = s[i];
        } else if (s[i] == ')' && top != -1 && stack[top] == '(') {
            top--;
        } else if (s[i] == '}' && top != -1 && stack[top] == '{') {
            top--;
        } else if (s[i] == ']' && top != -1 && stack[top] == '[') {
            top--;
        } else {
            return false; // 括号不匹配
        }
    }

    return top == -1; // 如果栈为空，说明括号匹配
}

int main() {
    char s[100];
    printf("输入一个包含括号的字符串: ");
    scanf("%s", s);

    if (isValid(s)) {
        printf("字符串有效\n");
    } else {
        printf("字符串无效\n");
    }

    return 0;
}

4 不完全解法

这个方法思想是删除已经配对的括号，最后看字符串是否为空，从而得到结果，但是直接对原字符串做删除操作会导致意想不到的问题。代码在下面，供拓展思路使用

// 检查字符串是否有效
int isValid(char* s) {
    int len = strlen(s);

    // 通过迭代删除匹配的括号
    for (int i = 0; i < len; i++) {
        if ((s[i] == '(' && s[i + 1] == ')') ||
            (s[i] == '{' && s[i + 1] == '}') ||
            (s[i] == '[' && s[i + 1] == ']')) {
            // 删除匹配的括号
            for (int j = i; j < len - 2; j++) {
                s[j] = s[j + 2];
            }
            len -= 2;
            i = -1; // 重新从字符串开头开始检查
        }
    }

    return len == 0; // 如果字符串为空，则括号有效
}
// "(){}}{" 测试用例-得到错误结果

迭代过程中修改了字符串可能导致问题，因为它会改变字符串的长度，而循环变量 i 的增加并不一定会正确地遍历整个字符串。这样的修改可能导致跳过一些字符或者重复检查某些字符。