在一行中输入一个字符串
,长度
,由可见字符组成。
如果字符串
中的括号部分能构成合法括号序列,则输出
;否则输出
。
abcd(])[efg
false
提取括号 `(`、`)`、`[`、`]` 后为 `(])[`,不是合法括号序列。
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为空 }