c语言使用栈的思想判断一串括号配对是否正确
原题目:给定一个只包括 ‘(’,’)’,’{’,’}’,’[’,’]’ 的字符串,判断字符串是否有效。
这道题我最之前使用两层循环做的,后来想想其实直接可以用数组写一个简单栈来对括号进行配对。首先对输入的字符串长度进行奇偶判断,若是遇到奇数,则直接pass掉。然后开始对字符串遍历,凡是遇到左括号都让它入栈,到遇到右括号时,让它和栈顶的左括号配对,若配对失败则该字符串无效,大概思路就是这样,直接供上代码。
#include<stdio.h>
#include<string.h>
char tihuan(char m);//替换与之对应的括号
int main()
{
char a[50],b[50];
int top=0,len;//先设置栈顶为0
gets(a);
len=strlen(a);//此strlen调用string库
if(len%2!=0)
{
printf("无效1");
}
else
{
for(int i=0;i<len;i++)
{
if(a[i]=='{'||a[i]=='('||a[i]=='[')
{
b[top]=a[i];
top++;
}
if(a[i]=='}'||a[i]==')'||a[i]==']')
{
a[i]=tihuan(a[i]);//将右括号替换成与之对应的左括号
if(top==0)
{
printf("无效2");//若遍历到右括号栈里仍然没有左括号直接pass掉
}
else
{
top--;//这里因为数组下标是从0开始记的,所以栈顶top永远是空的,top-1才是它真正栈顶
if(b[top]==a[i])
{
;//什么也不执行
}
else
{
top++;
}
}
}
}
if(top==0)
{
printf("有效");
}
else
{
printf("无效3");
}
}
}
char tihuan(char m)
{
if(m=='}')
return '{';
if(m==')')
return '(';
if(m==']')
return '[';
}