首页 > 试题广场 >

有效括号序列

[编程题]有效括号序列
  • 热度指数：371291 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
\hspace{15pt}给出一个仅包含字符仅由括号字符 \texttt{`['}、\texttt{`]'}、\texttt{`('}、\texttt{`)'}、\texttt{`\{'}、\texttt{`\}'} 的括号序列字符串 s（0 \leqq |s| \leqq 10^4），你需要判断给出的括号序列字符串 s 是否是有效的括号序列。

\hspace{15pt}有效括号序列的定义如下：
\hspace{23pt}\bullet\,空序列是有效括号序列；
\hspace{23pt}\bullet\,如果 A 是有效括号序列，则 \texttt{(A)}、\texttt{[A]} 和 \texttt{{A}} 都是有效括号序列；
\hspace{23pt}\bullet\,如果 A 和 B 都是有效括号序列，则它们的拼接 AB 也是有效括号序列。

\hspace{15pt}如果括号序列字符串 s 是有效的括号序列，返回一个布尔值 \texttt{true}；否则返回一个布尔值 \texttt{false}。
示例1

输入

"["

输出

false
示例2

输入

"[]"

输出

true

备注:
\hspace{15pt}要求：空间复杂度 ，时间复杂度 。
算法知识视频讲解
查看答案及解析
添加回答
C
牛客37235123号头像 牛客37235123号
会员，就这个讲解？语言组织不通顺，不重新录制一遍的吗？
发表于 2025-06-26 16:57:57 回复(0)
C
牛客747050659号头像 牛客747050659号 
bool isValid(char* s) {
    int top=0;
    for(int i=0;s[i];i++){
        char c=s[i];
        if(c=='('){
            s[top++]=')';
        }else if(c=='['){
            s[top++]=']';
        }else if(c=='{'){
            s[top++]='}';
        }else if(top==0||s[--top]!=c){//否则就是右括号才成功匹配了
            return false;
        }
    }
    return top==0;//栈为空就返回true
}

发表于 2025-03-15 22:30:34 回复(0)
C
小米zsy头像 小米zsy 
typedef struct stack {
    char arr[10000];
    int index;
} stack;
stack st;
void push(char ch) {
    st.arr[++st.index] = ch;
}
char pop(void) {
    if (st.index == -1)
        return 0;
    else
        return st.arr[st.index--];
}
char check(void) {
    if (st.index == -1)
        return 0;
    else
        return st.arr[st.index];
}
bool isValid(char* s ) {
    st.index = -1;
    int i = -1;
    while (i++, s[i]) {
        switch (s[i]) {
            case '(':
            case '[':
            case '{': push(s[i]); break;
            case ')': 
                if (check() == '(') pop(); 
                else return false;  
                break;
            case ']': 
                if (check() == '[') pop(); 
                else return false;  
                break;
            case '}': 
                if (check() == '{') pop(); 
                else return false;  
                break;
        }
    }
    if (check()) return false;
    else return true;
}
发表于 2024-10-09 19:05:49 回复(0)
C
75666666头像 75666666
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param s string字符串 
 * @return bool布尔型
 */
bool isValid(char* s ) {
    // write code here
    int top = -1; //栈顶指针
…    if(top == -1)
    {
        return true;
    }
    else {
    return false;
    }
}
发表于 2024-04-28 12:08:29 回复(0)
C
迷茫的小章鱼在开会头像 迷茫的小章鱼在开会
#include<stdio.h>
#include <stdlib.h>


struct node {
    char data;
    struct node* next;
};


struct node* youxu(char* p) {
    struct node* tail = malloc(sizeof(struct node));
    tail->next = NULL;
    int i = 0;
    while (*(p + i) != '\0') {
        if (*(p + i) == '{' || *(p + i) == '[' || *(p + i) == '(') {
            struct node* pnew = malloc(sizeof(struct node));

            pnew->data = *(p + i);
            pnew->next = tail->next;
            tail->next = pnew;
            i++;
        }

        if (*(p + i) == '}' || *(p + i) == ']' || *(p + i) == '\0') {
            if (tail->next == NULL || ((tail->next->data)) != *(p + i) - 2) {
                printf("false\n");
                break;
            }
            if (tail->next != NULL && (tail->next->data == *(p + i) - 2)) {
                //出栈
                struct node* k = tail->next;
                printf("%c ", tail->next->data);
                tail->next = k->next;
                k->next = NULL;
                free(k);
                k = tail->next;
                i++;
            }

        } else if (*(p + i) == ')') { //选择判断
            if (tail->next == NULL || ((tail->next->data)) != *(p + i) - 1) {
                printf("false\n");
                break;
            }
            if (tail->next != NULL && ((tail->next->data)) == *(p + i) - 1) {
                //出栈
                struct node* k = tail->next;
                printf("%c ", tail->next->data);
                tail->next = k->next;
                k->next = NULL;
                free(k);
                k = tail->next;
                i++;
            }
        }

    }
    if (tail->next == NULL) {
        printf("\nture\n");
    }


    return tail;
}


int main() {

    // char a[10];//只是给他分配了这么多的大小的空间，真实长度与用户输入有关

    // struct node *t=init();
    char a[10];
    scanf("%s", a);
    char* p = a;
    struct node* t = youxu(p);


}

发表于 2024-04-09 22:10:09 回复(0)
C
一个优雅的程序猿头像 一个优雅的程序猿 
int stack[10000]={0}, pointStack=0;
void push(int node ) {
    int i;
    if(pointStack+1>=sizeof(stack))
        return;
    stack[pointStack++]=node;
}

int pop() {
    int node=0;
    if(pointStack<=0)
        return 0;
    node = stack[pointStack-1];
    stack[pointStack-1]=0;
    pointStack--;
    return node;
}

int top() {
    return stack[pointStack-1];
}

int len() {
    return pointStack;
}

bool isValid(char* s ) {
    int i;
    for(i=0;i<strlen(s);i++) {
        if(s[i]=='(' || s[i]=='{' || s[i]=='[')
            push(s[i]);
        else if(s[i]==')' || s[i]=='}' || s[i]==']') {
            switch (s[i]) {
                case ')':   if(top()=='(')
                                pop();
                            else
                                return false;
                            break;
                case '}':   if(top()=='{')
                                pop();
                            else
                                return false;
                            break;
                case ']':   if(top()=='[')
                                pop();
                            else
                                return false;
                            break;
                default:    return false;
            }
        }
        else
            return false;
    }
    if(len()!=0)
        return false;
    return true;
}

编辑于 2024-03-17 17:50:11 回复(0)
C
牛客844606059号头像 牛客844606059号
将判断左右括号阴藏, 使代码更简洁

#define BRA_TYPE(bra) ( bra >> 5 ) - 1
char arrLeftBracket[3] = { '(', '[', '{' };
static inline int IsLeftBracket(char cBracket) {
    if (cBracket == arrLeftBracket[BRA_TYPE(cBracket)])
        return 1;

    return 0;
}

int isValid(char *szBracket) {
    struct {int top; char arrStack[10000];}
    unStack = {
        .top = -1,
        .arrStack = { 0 }
    };

    int cBracket;
    for (int i = 0; szBracket[i] != '\0'; i++) {
        cBracket = szBracket[i];
       
        if (! IsLeftBracket(cBracket)) {
            if (unStack.top == -1) return 0;

            if (BRA_TYPE(cBracket) == BRA_TYPE(unStack.arrStack[unStack.top]))
                unStack.top--;
            else return 0;
        }
        else
            unStack.arrStack[++unStack.top] = cBracket;
    }

    return unStack.top == -1;
}
发表于 2024-02-18 13:51:08 回复(0)
C
喜欢吃火锅的熊猫在评审头像 喜欢吃火锅的熊猫在评审 
#include <stdio.h>
#include <malloc.h>
#include <string.h>

//stdlib.h
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param s string字符串
 * @return bool布尔型
 */
char trans(char char_r) {
    if (char_r == ')')return '(';
    if (char_r == ']')return '[';
    if (char_r == '}')return '{';
    return 0;
}

bool isValid(char* s ) {
    // write code here
    char* p;
    int index_qian[10000] = {0};
    int i = 0, j = 0;
    p = (char*)malloc(sizeof(char) * strlen(s));
    p = s;
    //  printf("s长度%d\r\n",strlen(s));

    for (i = 0; i < strlen(s); i++) {
        if (p[i] == '(' || p[i] == '{' || p[i] == '[') {
            index_qian[j] = i;
            j++;//printf("正括号%c\r\n",p[i]);
            continue;
        }


        if (p[i] == ')' || p[i] == '}' || p[i] == ']')
            if (trans(p[i]) == p[index_qian[(j - 1)]]) {
                j--;//printf("反括号%c\r\n",p[i]);
            } else { //free(p);
                return 0;
            }

    }
    //printf("j为%d\r\n",j);
    //free(p);
    if (j > 0) return 0;
    return 1;
}
求助大佬为什么一用free()就卡住了
发表于 2023-12-06 12:34:15 回复(0)
C
慕林悠头像 慕林悠 
typedef struct lnode {
    char c;
    struct lnode* next;
} node, * stack;

void Push(stack* p, char a) {
    node* cur = (node*)malloc(sizeof(node));
    if (cur == NULL) return;
    cur->c = a;
    cur->next = *p;
    *p = cur;
}
void Pop(stack* p) {
    *p = (*p)->next;
}

bool  isValid(char* s) {
    // write code here
    stack top = NULL;
    for (int i = 0; s[i] != '\0'; i++) {//左括号时入栈
        if ((s[i] == '(') || (s[i] == '[') ||(s[i] == '{'))  
        Push(&top, s[i]);

        else {//右括号时，有匹配的左括号则出栈没有则返回false
            if(top == NULL) return false;
            else if ((top->c == '(' && s[i] == ')') 
                    || (top->c == '[' && s[i] == ']') 
                    ||(top->c == '{' && s[i] == '}'))
                    Pop(&top);
            else return false;
        }
    }
    if (top) return false;
    return true;
}

发表于 2023-11-23 00:48:43 回复(0)
C
fatzard头像 fatzard 
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param s string字符串 
 * @return bool布尔型
 */
#include <stdbool.h>
#include <stdio.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]=='('||s[i]=='['||s[i]=='{')
        {
            s[++top]=s[i];
        }
        else{
            if(top==-1)return false;
            if(s[i]==')'){
                if(s[top]=='(')top--;
                else return false;
            }
            else if(s[i]==']')
            {
                if(s[top]=='[')top--;
                else return false;
            }
            else if(s[i]=='}'){
                if(s[top]=='{')top--;
                else return false;
            }
        }
    }
    if(top==-1)return true;
    else return false;
}

发表于 2023-11-08 15:30:02 回复(0)
C
小西呀头像 小西呀
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param s string字符串
 * @return bool布尔型
 */

bool isValid(char* s )
{
    // write code here
    int len = strlen(s);             // 获取字符串s的长度
    if (len == 0) return true;       // 如果字符串s为空，则返回true
    if (len == 1) return false;     // 如果字符串s的长度为1，则返回false，因为一个括号无法构成有效的括号序列
    if (len % 2 != 0) return false; // 如果字符串s的长度是奇数，显然无法构成有效的括号序列，返回false
                               
    char* left = NULL;                 // 定义一个左括号的指针
    left = (char*)malloc(sizeof(char) * len); // 分配空间
    if (left == NULL) return false;     // 如果分配空间失败，则返回false
    char* p = s;                        // 定义一个指针指向字符串s
    int m = 0, count = 0;               // 定义一个指向left数组的指针m和计数器count
    while (*p != '\0') {                // 当指针p不指向字符串s的结束符时
        printf("m:%d\n", m); // 输出m的值
        if (*p == '(' || *p == '[' || *p == '{')  // 如果p指向的字符是左括号
        {      
            if (*p == '(') left[m++] = ')';//如果是左括号'('，则在left数组中保存')'                          
            if (*p == '[') left[m++] =']';                            
            if (*p == '{') left[m++] ='}';                            
            printf("left[m-1]:%c\n", left[m - 1]);  // 输出left数组中最后一个元素
        }
        if (*p == ')' || *p == ']' || *p == '}')  // 如果p指向的字符是右括号
        {
            count++; // 计数器加一
            if (*p != left[m - 1]) return false; // 如果左右括号不匹配，则返回false
            else m--;                            // 否则左括号指针往前移一位
        }
        p++; // 指针p往前移一位
    }
    if (count == 0) return false;               // 如果全都是左括号，则返回false
    return true;                                // 括号配对完毕，返回true
}
发表于 2023-09-29 00:49:29 回复(0)
C
陈让然头像 陈让然
要用到栈思想，也就是字符串前半段与后半段一一对应 
#include <stdbool.h>
bool isValid(char* s ) {
    // write code here
    //如果字符串为空，返回false
    if(!s)
    {
        return false;
    }
    //定义p指针指向字符串，求字符串长度len
    char*p=s;
    int len=0;
    while(*(p++)!='\0')
    {
        len++;
    }
    //如果字符串len不为偶数，即不合法
    if(len%2)
    {
        return false;
    }
    //重新定义p，指向后半段第一个字符
    p=s+(len/2);
    //定义数组，模拟栈
    char stack[10000];
    int count=0;
    //字符串后半段按顺序入栈
    while(*p!='\0')
    {
        stack[count++]=*p;
        p++;
    }
    //重新定义p指向字符串开头
    p=s;
    //比较将字符串前半段（前->后）与栈（后->前）内容对比
    for(int i=len/2-1;i>=0;i--)
    {

        if((i==0)&&\
        ((*p=='('&&stack[i]==')')||\
        (*p=='['&&stack[i]==']')||\
        (*p=='{'&&stack[i]=='}')))
        {
            //一一对应，为真
            return true;
        }
        p++;   
    }
    return false;
}

发表于 2023-09-12 16:46:01 回复(0)
C
小熊猫的黑眼圈头像 小熊猫的黑眼圈
bool isValid(char* s )
{
    // write code here
    char stack[10010]={0};
    int pos=0;
    while(*s)
    {
        int gap=fabs(*s-stack[pos]);
        if(gap>2||0==gap)
        {
            stack[++pos]=*s;
        }
        else
        {
            --pos;
        }
        ++s;
    }
    if(pos)
    {
        return false;
    }
    return true;
}
发表于 2023-08-08 20:52:43 回复(0)
C
小小小孩头像 小小小孩 
#define SMALL 81 //()
#define MEDIUM 184 //[]
#define LARGE 248 //{}
#define MAX_LEN 5000
char stack[MAX_LEN];
int s_top = -1;
bool isValid(char* s ) {
    // write code here
    int len = strlen(s);
    for(int i=0;i<len ;i++)
    {
        if(s_top <=-1 || s[i] == '(' || s[i] == '{'|| s[i] == '[')
            stack[++s_top] = s[i];
        else
        {
             int sum = s[i]+stack[s_top];
            if(sum == SMALL || 
                sum == MEDIUM ||
                sum == LARGE)
                s_top--;                
            else
                return false;
        };
    }
    return s_top==-1;
}

发表于 2023-06-24 22:51:07 回复(0)
C
爱吃肉的咸鱼在春招头像 爱吃肉的咸鱼在春招 
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param s string字符串
 * @return bool布尔型
 */
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#define MaxSize 5000

typedef struct Stack {
    char* base;
    char* top;
    int StackSize;

}* stack;

int InitStack(stack s) {
    s->base = (char*)malloc(sizeof(char) * MaxSize);
    if (!s->base) {
        exit(-2);
    }
    s->top = s->base;
    s->StackSize = MaxSize;
    return 1;
}

void PushStack(stack s, char c) {
    if (s->top - s->base == MaxSize) {
        exit(-2);
    }
    *(s->top) = c;
    ++(s->top);
}

char PopStack(stack s) {
    if (s->top == s->base) {
        return ' ';
    }
    char c = *(s->top - 1);
    --(s->top);
    return c;
}
bool isValid(char* s) {
    if (strlen(s) <= 1) {
        return false;
    }
    stack sta = (struct Stack*)malloc(sizeof(struct Stack));
    InitStack(sta);
    char c;
    for (int i = 0; i < strlen(s); i++) {
        if (s[i] == '(' || s[i] == '[' || s[i] == '{') {
            PushStack(sta, s[i]);
        } else {
            if (sta->top - sta->base == 0) {
                return false;
            }
            c = PopStack(sta);
            if (c == '(') {
                if (s[i] != ')') {
                    return false;
                }
            } else if (c == '[') {
                if (s[i] != ']') {
                    return false;
                }
            } else if (c == '{') {
                if (s[i] != '}') {
                    return false;
                }
            }
        }
    }
    if (sta->top - sta->base == 0) {
        return true;
    } else {
        return false;
    }
}

发表于 2023-04-06 20:20:40 回复(0)
提交观点

问题信息

字符串 栈
难度：
40条回答 39640浏览

热门推荐

通过挑战的用户

查看代码

相关试题

有效括号序列

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号