/***链栈实现括号匹配***/
#include<iostream>
using namespace std;
#include"LinkStack.h"

//括号的匹配
bool Matching()
{
	//检验表达式中所含括号是否正确匹配，如果匹配，则返回true，否则返回false。
	//表达式以“#”结束
	SNode<char> *S;
	InitStack(S);
	int flag=1;        								// 标记查找结果以控制循环及返回结果
	char c;
	char x;
	cin>>c;            								// 读入第一个字符
	while(c!='#' && flag)
	{
	   switch (c){
		   case '[':
		   case '(': 								// 若是左括号，则将其压入栈
			    cout<<"左括号进栈！"<<endl;
				Push(S,c);
				break;
		   case ')' :     							// 若是右括号“)”，则根据当前栈顶元素的值分情况考虑
			    GetTop(S,x);
				if (!StackEmpty(S) && x=='(' )		// 若栈非空且栈顶元素是“(”，则匹配成功
				{
					Pop(S,x);
					cout<<"右括号出栈！"<<endl;
				}
				else
					flag=0;                 		// 若栈空或栈顶元素不是“(”，则非法
				break;
		   case ']' :								 // 若是右括号“]”，则根据当前栈顶元素的值分情况考虑
				GetTop(S,x);
				if (!StackEmpty(S) && x=='[' )		// 若栈顶元素是“[”，则匹配成功
					 Pop(S,x);
				else
					flag=0;                 		// 若栈空或栈顶元素不是“[”，则非法
			   break;
	   }//switch
	   cin>>c;       								//继续读入下一个字符
	}//while
	DestroyStack(S);
	if (StackEmpty(S) && flag )
	   return true;
	else
	   return false;
}//Matching

int main()
{
	int flag; 
	cout<<"请输入待匹配的表达式，以“#”结束："<<endl;
	flag = Matching();
	if(flag)
		cout<<"括号匹配成功！"<<endl;
	else
		cout<<"括号匹配失败！"<<endl;
	return 0;
}