栈的应用–括号匹配
这里我以leetcode 上的一道题来进行问题的描述：
由于只包含字符的字符串'('，')'，'{'，'}'，'['和']'，确定输入字符串是有效的。
括号必须关闭以正确的顺序，"()"并且"()[]{}"都是有效的，但"(]"并"([)]"没有。
编程判断括号是否匹配实现思路： 遇到左括号就进栈，遇到右括号就出栈。
代码实现如下：
#include<stdio.h>
#include<stdlib.h>
typedef struct link{
char a;
struct link *next;
}LinkList ;
LinkList* InitLink( )
{
LinkList *head ;
head =(LinkList *)malloc(sizeof(LinkList));
head->next = NULL ;
return head ;
}
int InStack(LinkList *head,char p) //链栈不需要判断栈满
{
LinkList *temp ;
temp =(LinkList *)malloc(sizeof(LinkList));
temp->a = p;
temp->next = head->next ;
head->next = temp ;
return 0;
}
int IsEmptyStack(LinkList *head)
{
if(head->next == NULL)
return -1 ; //为空栈
else return 1;
}
char OutStack(LinkList *head) //判断栈空
{
char temp ;
LinkList *t ;
t= head->next ;
temp=head->next->a ;
head->next = t->next ;
free(t);
return temp;
}
int main(void)
{
char str[52];
int i;
char temp;
int t = 0;
LinkList *head ;
head = InitLink();
printf("please input the tseted string \n");
scanf("%s",str);
getchar();
for(i= 0 ;str[i] ;i++)
{
if(str[i] == '{' || str[i] == '(' )
InStack(head,str[i]);
else if(str[i] == ')')
{
if(IsEmptyStack(head) < 0)
{
printf("右 括 号 冗 余 \n");
break;
}
temp = OutStack(head);
if(temp == '(')
t++ ;
}
else if(str[i] == '}')
{
if(IsEmptyStack(head) < 0)
{
printf("右 括 号 冗 余 \n");
break;
}
temp = OutStack(head);
if(temp == '{')
t++ ;
}
}
if(IsEmptyStack(head) > 0){ //最后判断栈是否空
printf(" 左 括 号 冗 余\n");
printf("已匹配了%d 对\n",t);
}
else {
printf("一共匹配了%d 对 \n",t);
}
return 0;
}