20.有效的括号-C语言-创新互联
题目来源:力扣
专注于为中小企业提供成都网站设计、成都网站制作服务,电脑端+手机端+微信端的三站合一,更高效的管理,为中小企业铁西免费做网站提供优质的服务。我们立足成都,凝聚了一批互联网行业人才,有力地推动了1000多家企业的稳健成长,帮助中小企业通过网站建设实现规模扩充和转变。题目描述:
给定一个只包括
'('
,')'
,'{'
,'}'
,'['
,']'
的字符串s
,判断字符串是否有效。有效字符串需满足:
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
示例 1:
输入:s = "()" 输出:true示例 2:
输入:s = "()[]{}" 输出:true示例 3:
输入:s = "(]" 输出:false提示:
1<= s.length<= 104
s
仅由括号'()[]{}'
组成
思路:
根据s当前位置字符来判断操作,若s为左括号,入栈,若s为右括号,取栈顶元素并且出栈,然后用栈顶元素和s比较,若匹配,则说明当前括号对应,程序继续执行,否则错误
代码:
typedef int STDataType;
typedef struct Stack {
STDataType* a;
int top;
int capacity;
}ST;
void StackInit(ST* ps);//初始化
void StackDestory(ST* ps);//销毁
void StackPush(ST* ps,STDataType x);//入栈
void StackPop(ST* ps);//出栈
STDataType StackTop(ST* ps);//返回栈顶元素
void StackSize(ST* ps);//计算数据个数
bool StackEmpty(ST* ps);//判断是否为空
void StackInit(ST* ps)//初始化
{
assert(ps);
ps->a = (STDataType*)malloc(sizeof(STDataType) * 4);
if (ps->a == NULL) {
printf("malloc fail\n");
exit(-1);
}
ps->capacity = 4;
ps->top = 0;
}
void StackDestory(ST* ps)//销毁
{
assert(ps);
free(ps->a);
ps->a = NULL;
ps->top = ps->capacity = 0;
}
void StackPush(ST* ps, STDataType x)//入栈
{
assert(ps);
if (ps->top == ps->capacity) {//满了扩容
STDataType* tmp= (STDataType*)realloc(ps->a,ps->capacity*2*sizeof(STDataType));
if (tmp == NULL) {
printf("realloc fail\n");
exit(-1);
}
else {
ps->a = tmp;
ps->capacity *= 2;
}
}
ps->a[ps->top] = x;
ps->top++;
}
void StackPop(ST* ps)//出栈
{
assert(ps);
assert(ps->top>0);
ps->top--;
}
STDataType StackTop(ST* ps)//返回栈顶元素
{
assert(ps);
assert(ps->top >0);
return ps->a[ps->top - 1];
}
void StackSize(ST* ps)//计算数据个数
{
assert(ps);
return ps->top;
}
bool StackEmpty(ST* ps)//判断是否为空
{
assert(ps);
return ps->top == 0;
}
bool isValid(char * s){
ST st;
char top;
StackInit(&st);
while(*s != '\0'){
switch(*s){
case '(':
case '{':
case '[':
StackPush(&st,*s);
s++;
break;
case ')':
case '}':
case ']':
if(StackEmpty(&st)){
StackDestory(&st);
return false;
}
top = StackTop(&st);
StackPop(&st);
if((*s==')' && top != '(') ||
(*s==']' && top != '[') ||
(*s=='}' && top != '{'))
{
StackDestory(&st);
return false;
}else{
s++;
}
break;
default:
break;
}
}
bool ret =StackEmpty(&st);
StackDestory(&st);
return ret;
}
注意:1.返回之前要释放内存,否则会有内存泄漏情况(这是好的习惯,与题无关)
2.如果只输入左括号,我们就无法取栈顶元素然后比较,所以结尾要加上判空,如果不为空,说明栈内还有左括号,没有匹配完成,返回false
3.如果只输入右括号,会导致程序出错,所以在取栈顶元素前要判断栈是否为空,为空则说明栈内无对应左括号,返回flase
4.使用完一次s后要记得s++
运行结果:
你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧
本文名称:20.有效的括号-C语言-创新互联
文章位置:http://myzitong.com/article/dihjjd.html