括号匹配问题 - 链栈

学校布置的题目，感觉挺有意思的，于是拿来写一发题解。

老规矩，先附上题目

【问题描述】用前面程序实现的char型链栈，解决括号匹配问题
【输入形式】以#为结束符的一个符号序列
【输出形式】如果所有的左右括号全部匹配，输出1；否则输出0

【样例输入】{([])}()#

【样例输出】1

这道题说的很明确了，要求用栈来解决。

我们不妨想一下，怎么样的输入可以被称为是匹配的呢？经过分析，我得出这样的结论：对于每一个遇到的右括号，如果前面从右往左第一个没有匹配的左括号如果能和他匹配，而且最后整个序列没有剩余，那么整个序列就是正确的。

那么我们的思路就形成了，建立一个栈，遇到左括号就push入栈，遇到右括号就取出最顶上的元素观察是否匹配，如果还有右括号而栈已经空了或者栈没空序列已经结束了都是错误的。

下面给出代码

#include
using namespace std;
typedef struct node{
	char data;
	struct node *next;
}LinkStackNode;
typedef LinkStackNode *LinkStack;
void InitStack(LinkStack &S)
{
	S=(LinkStack)malloc(sizeof(LinkStackNode));
	S->next=NULL;
}
void push(LinkStack &S,char x)
{
	LinkStack temp;
	temp=(LinkStack)malloc(sizeof(LinkStackNode));
	temp->data=x;
	temp->next=S->next;
	S->next=temp;
}
char pop(LinkStack &S)
{
	char x;
	LinkStack temp;
	temp=S->next;
	if(temp==NULL)
		return false;
	S->next=temp->next;
	x=temp->data;
	free(temp);
	return x;
}
int main()
{
	int i=1;
	char c,str[100];
	LinkStack S;
	InitStack(S);
	while((c=getchar())!='#')
	{
		str[i]=c;
		i++;
	}
	for(int j=1;jnext==NULL)
			{
				printf("0");
				return 0;
			}
			c=pop(S);
			if(str[j]==']'&&c!='[')
			{
				printf("0");
				return 0;
			}
			if(str[j]=='}'&&c!='{')
			{
				printf("0");
				return 0;
			}
			if(str[j]==')'&&c!='(')
			{
				printf("0");
				return 0;
			}
		}
	}
	if(S->next==NULL)
		printf("1");
	else
		printf("0");
	return 0;
}