用stack实现检测字符串中(){}[]是否匹配

　2012-06-20 07:32:59　来源：WEB开发网　　　

核心提示： 基本思路： for str 中的每个ch 如果 ch 是左字符 push() 如果 ch 是右字符如果 stack 为空，肯定不匹配，用stack实现检测字符串中(){}[]是否匹配，退出如果 stack 非空，若 top() 和 ch 不配对，若为空，匹配不为空，那么肯定不匹配，退出最后检测stack是否为空

基本思路：
for str 中的每个ch
如果 ch 是左字符
push()
如果 ch 是右字符
如果 stack 为空，肯定不匹配，退出
如果 stack 非空，若 top() 和 ch 不配对，那么肯定不匹配，退出

最后检测stack是否为空，若为空，匹配
不为空，则不匹配。

注意特殊情况：输入纯字符的情况

// match.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <stack>
#include <string>
#include <iterator>
#include <algorithm>
bool is_right(char ch)
{
	if (ch == ')' || ch == '}' || ch == ']')
		return true;
	else
		return false;
}

bool is_left(char ch)
{
	if (ch == '(' || ch == '[' || ch == '{')
		return true;
	else 
		return false;
}

bool is_pair(char left, char right)
{
	if ((left == '(' && right == ')') ||
		(left == '[' && right == ']') ||
		(left == '{' && right == '}'))
		return true;
	else
		return false;
}
int main(int argc, char* argv[])
{
	string str;
	stack<char> m_char;

	cout << "Enter the string : " ;
	getline(cin, str);

	bool is_have_push_left = false; //主要是防止输入 huang 这样的情况
	for (unsigned int i = 0; i < strlen(str.c_str()); i++)
	{
		char ch = str.at(i);
		if (is_left(ch))
		{
			m_char.push(ch);
			is_have_push_left = true;
		}
		if (is_right(ch))
		{
			if (m_char.empty())
				break;

			char ch_top = m_char.top();
			if (is_pair(ch_top, ch))
				m_char.pop();
			else
				break;
		}
	}
	
	if (m_char.empty() && is_have_push_left)
		cout << "match" << endl;
	else
		cout << "not match" << endl;
	
	return 0;
}