c++实现的括号匹配，通过链栈方式

/*
表达式中的括号是否匹配
*/

bool CLinkSta::IsMatch(DataType* str)
{
	if( NULL == str ) return false;
	
	while( m_node )
	{
		PopLinkStack();
	}
	CLinkNode* stack1 = NULL;
	CLinkNode* stack2 = NULL;
	CLinkNode* pNode1 = NULL;
	CLinkNode* pNode2 = NULL;
	DataType* cTemp = str;
	while( *cTemp )
	{
		if( *cTemp == '(' || *cTemp == '[' || *cTemp == '{' )
		{
			pNode1 = new CLinkNode;
			pNode1->m_Ch = *cTemp;
			pNode1->next = stack1;
			stack1 = pNode1;
		}
		else if( *cTemp == ')' || *cTemp == ']' || *cTemp == '}' )
		{
			
			pNode2 = new CLinkNode;
			pNode2->m_Ch = *cTemp;
			pNode2->next = stack2;
			stack2 = pNode2;
		}
		++cTemp;
	}
	int nCnt = 0;
	while( stack1 && stack2 )
	{
		stack1 = stack1->next;
		stack2 = stack2->next;
	}
	while( stack1 && stack2 )
	{
		CLinkNode* pTemp1 = stack1;
		CLinkNode* pTemp2 = stack2;
		stack1 = stack1->next;
		stack2 = stack2->next;
		DataType ch = pTemp1->m_Ch;
		switch( ch )
		{
		case ')':
			ch = '(';
			break;
		case ']':
			ch = '[';
			break;
		case '}':
			ch = '{';
			break;
		}
		
		if( ch != pTemp2->m_Ch )
		{
			++nCnt;
			break;
		}
		delete pTemp1;
		delete pTemp2;
	}
	
	if( !nCnt && !stack1 && !stack2 )
	{
		return true;
	}
	else
	{
		while( stack1 )
		{
			CLinkNode* pTemp1 = stack1;
			stack1 = stack1->next;
			delete pTemp1;
		}
		while( stack2 )
		{
			CLinkNode* pTemp2 = stack2;
			stack2 = stack2->next;
			delete pTemp2;
		}
			while( *str )
			{
				if( *str == '(' || *str == '[' || *str == '{' )
				{
					PushLinkStack(*str);
				}
				else if( *str == ')' || *str == ']' || *str == '}' )
				{
					if( !m_node )
					{
						return false;
					}
					else
					{
						DataType ch = *str;
						switch( ch )
						{
						case ')':
							ch = '(';
							break;
						case ']':
							ch = '[';
							break;
						case '}':
							ch = '{';
							break;
						}
						
						if( ch != PopLinkStack() )
						{
							return false;
						}
					}
				}
				++str;
			}
			
			if( !m_node )
			{
				return true;
		}
	}
	return false;	
}

评论

1 楼 iaimstar 2009-06-26  

这一堆堆的