首页 > 试题广场 >

括号配对问题

[编程题]括号配对问题
  • 热度指数:10569 时间限制: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\,如果 AB 都是合法括号序列,则它们的拼接 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

说明

提取括号后为 `[()]`,是合法括号序列。
利用栈先进后出的特点解题,遇到第一个右括号就与栈顶元素进行比较。
#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)