源代码网站培训,网站建设步和客户沟通,网络营销策划方案15篇要求,传奇网站怎么做力扣网 20 有效的括号
题目描述
给定一个只包括 (#xff0c;)#xff0c;{#xff0c;}#xff0c;[#xff0c;] 的字符串 s #xff0c;判断字符串是否有效。
有效字符串需满足#xff1a;
左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。每个右…力扣网 20 有效的括号
题目描述
给定一个只包括 (){}[] 的字符串 s 判断字符串是否有效。
有效字符串需满足
左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。每个右括号都有一个对应的相同类型的左括号。
示例 1
输入s ()
输出true示例 2
输入s ()[]{}
输出true示例 3
输入s (]
输出false思路分析
如果这里再用所谓的遍历字符串寻找进行匹配的话时间复杂度高且不说还麻烦但如果我们学习栈了以后这道题会变得异常轻松。
我们将所有的左括号入栈在字符串里找右括号同时出栈左括号进行匹配如果匹配成功就返回true否则返回false。
注意的问题
这里除了括号类型的匹配问题同时还有数量问题会存在左括号多于右括号或者反过来的情况这里如果数量不匹配的话也返回false。
判断数量的问题再寻找右括号时先判断栈是否为空这是判断右括号多余左括号的情况
在遍历一遍字符串后如果栈里面还有括号说明左括号多于右括号也返回false。
完整代码
力扣环境下是不提供栈的这里我们需要自己定义。
栈定义和常用接口
头文件
#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#includestdio.h
#includestdlib.h
#includeassert.h
#includestdbool.htypedef char STDataType;typedef struct Stack
{STDataType* a;int _top;int _capacity;
}Stack;// 初始化栈
void StackInit(Stack* ps);
// 入栈
void StackPush(Stack* ps, STDataType data);
// 出栈
void StackPop(Stack* ps);
// 获取栈顶元素
STDataType StackTop(Stack* ps);
// 获取栈中有效元素个数
int StackSize(Stack* ps);
// 检测栈是否为空如果为空返回非零结果如果不为空返回0
int StackEmpty(Stack* ps);
// 销毁栈
void StackDestroy(Stack* ps); 接口实现文件
#includeStack.h// 初始化栈
void StackInit(Stack* ps)
{assert(ps);ps-a NULL;ps-_capacity 0;ps-_top 0;
}// 入栈
void StackPush(Stack* ps, STDataType data)
{assert(ps);//检查是否栈满if (ps-_top ps-_capacity){int newcapacity ps-_capacity 0 ? 4 : ps-_capacity * 2;Stack* ptr realloc(ps-a, sizeof(STDataType) * newcapacity);if (ptr NULL){perror(realloc fail);return;}ps-a ptr;ps-_capacity newcapacity;}//入栈ps-a[ps-_top] data;ps-_top;
}// 出栈
void StackPop(Stack* ps)
{assert(ps);assert(ps-_top 0);ps-_top--;
}// 获取栈顶元素
STDataType StackTop(Stack* ps)
{assert(ps);assert(ps-_top 0);return ps-a[ps-_top-1];
}// 获取栈中有效元素个数
int StackSize(Stack* ps)
{assert(ps);return ps-_top;
}
// 检测栈是否为空如果为空返回非零结果如果不为空返回0
int StackEmpty(Stack* ps)
{assert(ps);if (ps-_top 0){return 1;}else{return 0;}
}// 销毁栈
void StackDestroy(Stack* ps)
{assert(ps);free(ps-a);ps-_capacity 0;ps-_top 0;
}
题目所需代码
bool isValid(char* s) {Stack st;StackInit(st);//初始化栈while (*s){if (*s { || *s ( || *s [)//为左括号进栈{StackPush(st, *s);}else{if (StackEmpty(st))//如果为右括号先判断栈是否为空{StackDestroy(st);return false;}char top StackTop(st);//出栈栈顶括号StackPop(st);if (*s ] top ! [ ||//两者进行匹配如果存在不等情况返回false*s } top ! { ||*s ) top ! (){StackDestroy(st);return false;}}s;}bool ret StackEmpty(st);//最后再判断栈是否为空左括号多余右括号情况布尔值如果栈为空返回真否则返回假StackDestroy(st);return ret;
}
