C语言实现括号序列有效性判断

本文介绍了使用C语言判断括号序列是否有效的算法和代码实现。通过栈数据结构，代码能够有效地识别括号匹配情况，并判断括号序列是否合法。

问题描述：

给定一个字符串所表示的括号序列，包含以下字符： '(', ')', 判定是否是有效的括号序列。

括号必须依照 '( )' 顺序表示， '( )' 是有效的括号，但 ')(' 则是无效的括号。

代码实现：

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

bool isValid(char* s) {
    int len = strlen(s);
    char* stack = (char*)malloc(sizeof(char) * len);
    int top = -1;
    
    for (int i = 0; i < len; i++) {
        if (s[i] == '(') {
            stack[++top] = s[i];
        } else if (s[i] == ')') {
            if (top < 0 || stack[top] != '(') {
                free(stack);
                return false;
            }
            top--;
        }
    }
    
    free(stack);
    return top == -1;
}

int main() {
    char* s = "( )()";
    if (isValid(s)) {
        printf("Valid\n");
    } else {
        printf("Invalid\n");
    }
    
    return 0;
}

算法解释：

该代码中的isValid函数用于判断一个括号序列是否有效。首先，我们创建一个栈（数组）来存储括号，然后遍历字符串中的每个字符。如果遇到左括号，我们将其压入栈中。如果遇到右括号，我们检查栈顶是否为左括号，如果不是，则说明括号序列无效，直接返回false。如果栈为空或栈顶元素为左括号，则将栈顶元素弹出。最后，检查栈是否为空，如果为空，则说明括号序列有效，返回true；否则，返回false。

在main函数中，我们给定了一个括号序列字符串s，并调用isValid函数进行判断。如果返回值为true，则打印"Valid"；否则，打印"Invalid"。