判括号匹配（顺序栈）

现在的位置: 首页 > 综合 > 正文

RSS

判括号匹配（顺序栈）

2013年12月07日 ⁄ 综合 ⁄ 共 1116字 ⁄ 字号小中大 ⁄ 评论关闭

1.题目：

Problem Description

任意输入一个由若干个圆括号、方括号和花括号组成的字符串，设计一个算法判断该串中的括号是否配对。

Input

有多组数据，每组为一个包含3类括号的字符串，串长不超过100。

Output

若该串中的括号匹配输出1，否则输出0。

Sample Input

([{}])
([{}})
([{)]}

Sample Output

1
0
0

2.参考代码：

#include <iostream>
#include <string.h>
using namespace std;

class SeqStack{   ///顺序栈
private:
	char data[1111];
	int top;
public:
	SeqStack(){
		top=-1;
	}
	~SeqStack(){
		
	}
	void Push(char x){
		data[++top]=x;
	}
	char GetTop(){
		return data[top];
	}
	void Pop(){
		if(top!=-1)
			top--;
	}
	bool empty(){
		if(top==-1)
			return true;
		else 
			return false;
	}
};

int main()
{
	char s[1111];
	int i,len;
	while(gets(s))
	{
		len=strlen(s);
		SeqStack w;
		for(i=0;i<len;i++)
		{
			if(s[i]=='(' || s[i]=='[' || s[i]=='{')   
				w.Push(s[i]);
			    ///若遇到左圆括号，左花括号，左方括号，则直接入栈
			else if(s[i]==')')   ///遇到右圆括号
			{
				if(!w.empty())   ///若不为空
				{
					if(w.GetTop()=='(')   ///就判断栈顶是否为左圆括号
						w.Pop();   ///是的话，就将栈顶的左圆括号出栈
					else
						w.Push(s[i]);   ///否则当前元素入栈
				}
				else
					w.Push(s[i]);   ///当前元素入栈
			}
			else if(s[i]=='}')   ///遇到右花括号和上面的同理
			{
				if(!w.empty())
				{
					if(w.GetTop()=='{')
						w.Pop();
					else
						w.Push(s[i]);
				}
				else
					w.Push(s[i]);
			}
			else if(s[i]==']')   ///遇到右方括号和上面的同理
			{
				if(!w.empty())
				{
					if(w.GetTop()=='[')
						w.Pop();
					else
						w.Push(s[i]);
				}
				else
					w.Push(s[i]);
			}
		}
		if(w.empty())   ///若遍历完整个字符串后，栈为空则说明匹配成功
			cout<<1<<endl;
		else
			cout<<0<<endl;   ///否则不成功
	}
	return 0;
}