给出一个仅包含字符'(',')','{','}','['和']',的字符串，判断给出的字符串是否是合法的括号序列
括号必须以正确的顺序关闭，"()"和"()[]{}"都是合法的括号序列，但"(]"和"([)]"不合法。
括号必须以正确的顺序关闭，"()"和"()[]{}"都是合法的括号序列，但"(]"和"([)]"不合法。
数据范围：字符串长度 
要求：空间复杂度 )
，时间复杂度
[编程题]有效括号序列
#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)
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)
将判断左右括号阴藏, 使代码更简洁
#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)
#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)
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)
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @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)
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @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)
要用到栈思想，也就是字符串前半段与后半段一一对应
#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)
#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)
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @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)
#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)
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)
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @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)
使用字符串来模拟栈的操作，本题难点在于要考虑到各种入参的场景
bool isValid(char* s ) {
// write code here
int len=strlen(s);
if(len == 0) return true;
if(len == 1) return false; // 只有1个括号的场景
if(len%2!=0) return false; // 括号不配对的场景
char* left =NULL;
left = (char*)malloc(sizeof(char)*len);
if(left==NULL) return false;
char* p =s;
int m=0, count=0;
while(*p!='\0') {
printf("m:%d\n",m);
if(*p =='(' || *p =='[' || *p =='{') {
if(*p =='(') left[m++] =')';
if(*p =='[') left[m++] =']';
if(*p =='{') left[m++] ='}';
printf("left[m-1]:%c\n",left[m-1]);
}
if(*p ==')' || *p ==']' || *p =='}') {
count++;
if(*p != left[m-1]) return false; // 左右括号不匹配
else m--;
}
p++;
}
if(count==0) return false; // 全都是左括号场景
return true;
}
发表于 2022-11-10 11:49:10
回复(0)
问题信息
难度：
34条回答
1069收藏
34042浏览
通过挑战的用户
查看代码-
2023-01-31 19:12:46 -
2022-12-07 13:58:39
-
2022-11-26 13:12:57
-
2022-11-13 10:57:05 -
2022-10-28 16:11:48
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
