首页 > 试题广场 >

有效括号序列

[编程题]有效括号序列
  • 热度指数：336382 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给出一个仅包含字符'(',')','{','}','['和']',的字符串，判断给出的字符串是否是合法的括号序列
括号必须以正确的顺序关闭，"()"和"()[]{}"都是合法的括号序列，但"(]"和"([)]"不合法。

数据范围：字符串长度
要求：空间复杂度 ，时间复杂度
示例1

输入

"["

输出

false
示例2

输入

"[]"

输出

true
算法知识视频讲解
添加回答
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)
C
碧秋头像 碧秋 
#include<stdio.h>

/*[()]
左括号就进栈，右括号就出栈
*/
bool isValid(char* s ) {
	char stk[10000];
	int top=0;

	for(int i=0;s[i]!='\0';i++){
		char c=s[i],c2=0;
		switch(c){
			case '{':
			case '[':
			case '(':stk[top++]=c;break;
			case '}':
			case ']':
			case ')':c2=stk[--top];
		}
		if(c2!=0){//当前字符是右括号,进行了弹栈，c2是左括号，c是右括号
			if(c=='}'){
				if(c2!='{')
					return false;
			}else if(c==']'){
				if(c2!='[')
					return false;
			}else{
				if(c2!='(')
					return false;
			}
		}
	}//for
	return top==0;
}

发表于 2023-03-31 12:58:25 回复(0)
C
帅奶哟。头像 帅奶哟。 
int i = 0, j = -1;
char a[10000];

bool isValid(char* s ) {
    // write code here
    while (s[i] != '\0') {
        if (s[i] == '(' || s[i] == '[' || s[i] == '{') {    //左括号进栈
            a[++j] = s[i];
        }
        else {          //是右括号则判断是否匹配
            if (s[i] == ')' && a[j] != '(') return false;
            else if (s[i] == ']' && a[j] != '[') return false;
            else if (s[i] == '}' && a[j] != '{') return false;
            else j--;
        }
        i++;    //指向字符串下一个字符
    }
    if (j >= 0) return false;   //栈非空
    else return true;
}

发表于 2023-03-17 15:16:39 回复(0)
C
牛客350454091号头像 牛客350454091号 
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param s string字符串 
 * @return bool布尔型
 */
 // ([{ 相当于进栈  }])相当于出栈



bool isValid(char* s ) 
{
    // write code here
    char arr[10001] = "\0";
    int aIndex = 0;
    int sIndex = 0;
    bool flag = true; // 合法
    while(s[sIndex] != '\0' && flag)
    {
        switch(s[sIndex++])
        {
            case '[':
            {
                arr[aIndex++] = ']';
                break;
            }
            case '{':
            {
                arr[aIndex++] = '}';
                break;
            }
            case '(':
            {
                arr[aIndex++] = ')';
                break;
            }
            case ')':
            {
                if (arr[--aIndex] != ')')
                {
                    flag = false;
                }
                break;
            }
            case ']':
            {
                if (arr[--aIndex] != ']')
                {
                    flag = false;
                }
                break;
            }
            case '}':
            {
                if (arr[--aIndex] != '}')
                {
                    flag = false;
                }
                break;
            }
        }
    }
    if (aIndex != 0)
    {
        flag = false;
    }
    return flag;
}

发表于 2022-11-12 21:45:56 回复(0)
提交观点

问题信息

字符串 栈
难度：
36条回答 35514浏览

热门推荐

通过挑战的用户

查看代码

相关试题

有效括号序列

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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