首页 > 试题广场 >

括号配对问题

[编程题]括号配对问题
  • 热度指数：15610 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
\hspace{15pt}给定一个字符串 S，请检查字符串中仅由括号字符 \texttt{`['}、\texttt{`]'}、\texttt{`('}、\texttt{`)'} 组成的子序列是否构成合法括号序列。合法括号序列的定义如下：

\hspace{23pt}\bullet\,空序列是合法括号序列；

\hspace{23pt}\bullet\,如果 A 是合法括号序列，则 `(A)` 和 `[A]` 都是合法括号序列；

\hspace{23pt}\bullet\,如果 A 和 B 都是合法括号序列，则它们的拼接 AB 也是合法括号序列。

\hspace{15pt}字符串 S 可能包含其他字符，但只需考虑括号部分，忽略其他字符。

输入描述:
\hspace{15pt}在一行中输入一个字符串 S，长度 1 \leqq |S| \leqq 10^4，由可见字符组成。


输出描述:
\hspace{15pt}如果字符串 S 中的括号部分能构成合法括号序列，则输出 \texttt{true}；否则输出 \texttt{false}。
示例1

输入

abcd(])[efg

输出

false

说明

提取括号 `(`、`)`、`[`、`]` 后为 `(])[`，不是合法括号序列。
示例2

输入

a[x(y)z]

输出

true

说明

提取括号后为 `[()]`，是合法括号序列。
算法知识视频讲解
添加回答
C
Comeand头像 Comeand
#include <stdio.h>
#include <stdbool.h>

int main(){
    int s;
    char stack[500];
    int top=-1;
    bool hefa=true;
while((s=getchar())!=EOF&&hefa){
    switch(s) {
    case'(':
    case'[':
        stack[++top]=s;
        break;
    case')':
        if(top==-1||stack[top]!='('){
            hefa=false;
        }
        else{
            top--;
        }
        break;
    case ']':
        if(top==-1||stack[top]!='['){
            hefa=false;
        }
        else{
            top--;
        }
        break;
   }
}
    if(hefa&&top==-1){
    printf("true");
}else {
    printf("false");
}
    return 0;
}
发表于 2025-11-22 15:39:08 回复(0)
C
牛客736096499号头像 牛客736096499号
#include <stdio.h>
#include<stdlib.h>
int main() {
    int cap=4;
    char *stack=(char*)malloc(cap*sizeof(char));
    int top=-1;
    char c;

    if(stack==NULL){
        printf("内存分配失败");
        return 1;
    }

   while((c=getchar())!=EOF&&c!='\n')
   {
   if(c=='('||c=='['||c==')'||c==']')
    {
        if(c=='('||c=='[')
        {top++;
        if(top+1>cap){
            cap*=2;
            stack=(char*)realloc(stack,cap*sizeof(char));
        }
        stack[top]=c;
        }
        else{
            if(top==-1){
                printf("false\n");
                free(stack);
                return 0;
            }
            if((c==')'&&stack[top]=='(')||(c==']'&&stack[top]=='['))
            {
                top--;
            }
            else{
                printf("false");
                free(stack);
                return 0;
            }
        }
    }
   }
    if(top==-1){
        printf("true\n");
    }
    else{
        printf("false\n");
    }
   
   
   free(stack);
    return 0;

}
发表于 2025-11-11 21:22:39 回复(0)
C
想去重庆的牛油在debug头像 想去重庆的牛油在debug
利用栈先进后出的特点解题，遇到第一个右括号就与栈顶元素进行比较。 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

//顺序栈
typedef struct {
    char *str;
    int top;
} stack_t;

//顺序栈的创建与初始化
stack_t *stack_init(int len);
//入栈
void stack_push(stack_t *sq, char data);
//出栈
void stack_pop(stack_t *sq);
//判空
int stack_is_empty(stack_t *sq);

int main() {
    int len;
    char str[10000];
    scanf("%s", str);
    len = strlen(str);
    stack_t *sq = stack_init(len);
    for(int i = 0; str[i] != '\0'; i++){
        if ((str[i] == '(') || (str[i] == '[')){
            stack_push(sq, str[i]);   //满足条件，是左括号，入栈
        } else if ((str[i] != ')') && (str[i] != ']')){
            continue;
        }
        if ((str[i] == ')') || (str[i] == ']')){       //遍历到右括号开始位置，进行配对判断
            if(stack_is_empty(sq) == 0){               //如果栈为空，直接结束程序，并输出false
                printf("false\n");
                free(sq->str);
                free(sq);
                return 0;
            }
            if((sq->str[sq->top] == '(') && (str[i] == ')')){
                stack_pop(sq);     //满足条件，出栈     
                continue;
            }
            else if((sq->str[sq->top] == '[') && (str[i] == ']')){
                stack_pop(sq);     //满足条件，出栈
                continue;
            }
            else{
                printf("false\n");
                free(sq->str);
                free(sq);
                return 0;
            }
        }
    }

    if(stack_is_empty(sq) == -1){
        printf("false\n");
        free(sq->str);
        free(sq);
        return 0;
    } else {
        printf("true\n");
        free(sq->str);
        free(sq);
        return 0;
    }
    return 0;
}




//顺序栈的创建与初始化
stack_t *stack_init(int len)
{
    stack_t *sq = (stack_t *)malloc(sizeof(stack_t));
    if(sq == NULL){
        printf("sq create failed\n");
        return NULL;
    }
    sq->str = (char *)malloc(sizeof(char) * len);
    if(sq->str == NULL){
        printf("sq->str create failed\n");
        return NULL;
    }
    sq->top = -1;
    return sq;
}
//入栈
void stack_push(stack_t *sq, char data)
{
    sq->top += 1;
    sq->str[sq->top] = data;
}
//出栈
void stack_pop(stack_t *sq)
{
    sq->top -= 1;
}
//判空
int stack_is_empty(stack_t *sq)
{
    if(sq->top != -1)
        return -1;       //返回-1为非空
    else
        return 0;        //返回0为空
}

发表于 2025-08-10 17:12:26 回复(0)
提交观点

问题信息

字符串 栈 唯品会 测试工程师
来自：唯品会2019秋招互金测试岗
上传者：小小
难度：
3条回答 10357浏览

热门推荐

通过挑战的用户

查看代码

相关试题

括号配对问题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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