Question

c++ 求教大神如何利用递归实现匹配括号

Answer 1

//使用栈进行括号匹配
//打印结果中,未匹配的'('下标注'$',未匹配的')'下标注'?'

#include <vector>
#include <list>
#include <iostream>
#include <cstring>
#define MAXN   100
using namespace std;

//节点数据类型
typedef struct
{
    char c;          //字符（括号）
    int  pos;        //位置
} Node, *PNode;

//用双向链表来模拟栈
typedef  list<Node> STACK;

//括号匹配
//left为要匹配的左边括号，right为要匹配的右边括号
//打印中结果,未匹配的'('下标注'$',未匹配的')'下标注'?'
void match(const char *s, char left, char right)
{
	STACK st;
	STACK::iterator  it;
	PNode pn=NULL;
	int i=0, n=strlen(s);
	pn=new Node();
	//用栈进行括号匹配
	//基本思路：遇到左括号则入栈；遇到右括号则检查栈顶是否为左括号，是则
	//          将其出栈；否则将右括号入栈。
	//          最后剩下的就是未匹配的括号（及其在字符串中的位置）
	for (i=0;i < n; i++)	 		//检查所有输入字符
	{
		pn->c=s[i];
		pn->pos=i;
		//遇到左边括号，则入栈
		if ( s[i] == left )        st.push_back(*pn);
		else if ( s[i] == right)   //遇到右边括号
		{
			if (!st.empty())       //如果栈非空
			{
				it=st.end();			
				it--;				//得到栈尾指针
				Node no= *it;
				if (no.c == left)	st.pop_back(); //若栈顶为左边括号，则出栈
				else				st.push_back(*pn);//否则将右边括号入栈
			}
			else st.push_back(*pn); //栈为空，遇到右边括号，将其入栈
		}		
	}
	
	delete pn;          //删除临时节点
	pn=NULL;		
	n = st.size() ;    //栈节点个数
    int k = 0;
    it=st.begin();
    for (i=0; (i<n )&& (it != st.end()); ++it,++i)
    {
		Node no = *it;      //未匹配括号节点
        while (k < no.pos ) //非未匹配括号：打印空格
        {
            cout<<' ';
            k++;
        }
        //当前未匹配括号，按要求打印'$'或'?'
        if (no.c == left)      cout<< '$' ;
        else if(no.c == right) cout<< '?';
        k++;
    }
	st.clear();//销毁栈（只是习惯，有创建就显式销毁。不是必需）
}
int main()
{
    char s[MAXN+1];
    vector<string> vs;
    
	//输入，保存在vs中，Ctrl+Z结束
    while(cin.getline(s,MAXN)) vs.push_back(s);
	
	//对每行的输入进行匹配
	vector<string>::iterator it=vs.begin();	
	for(;it!=vs.end();it++){
		cout<<(*it).c_str()<<endl;
		match((*it).c_str(),'(', ')');
	}

    return 0;
}

Answer 2

#include <iostream>
using namespace std ;
char * match( char *s )
{
	while( *s )
	{
		if ( *s == '(' )
		{
			char *p=match( s+1 );
			if ( p ) s = p ; 
			else
				break ;
		}
		else if ( *s == ')' )
		{
			return s ;
		}
		s++;
	}
	return NULL;
}
void match_brace( char *s )
{
	char temp[101],*ss=s;
	int i=0,err=0;
	while ( *s ) //遍历字符串
	{
		if ( *s=='(' ) //遇到（进行匹配
		{
			char *p=match( s+1 ) ;
			if ( p ) //匹配正确
			{
				temp[i++]=' ';
				while( s < p )
				{
					temp[i++]=' ';
					s++;
				}
			}else{ //未能匹配
				temp[i++]='$' ;
				err++;
			}
		}
		else if ( *s == ')' ) //因为匹配正确时，会跳过)，所以这里如果遇到），则说明有问题
		{
			temp[i++]='?' ;
			err++;
		}
		else
			temp[i++]=' ';
		s++;
	}
	temp[i]='\0';
	if ( err )
	{
		cout << ss <<endl ;
		cout << temp<<endl ;
	}
}

int main()
{
	char str[101];
	while( cin.getline(str,sizeof(str) ) )
	{
		match_brace( str );
	}
	return 0;
}

追问

请问第十行是什么意思啊？而且好像还是有问题。。。

追答

有什么问题你提出来啊，比如，测试哪个案例不正确，上图也可以，提供相应案例也成，这程序我测试过一些案例，均可以通过

char * match( char *s ) //这个函数是完成，从s位置开始，查找一个）实现与（匹配，如果找不到，返回NULL，如果找到，则返回相应的）位置
{
    while( *s )
    {
        if ( *s == '(' ) //如果在查找过程中，又一次遇到（，则递归查找其匹配的）
        {
            char *p=match( s+1 ); //递归
            if ( p ) s = p ; //如果找到，返回的p就是）的位置，s后移到其位置，继续s原本的任务
            else
                break ; //否则，结束查找，返回错误NULL
        }
        else if ( *s == ')' ) //找到了，返回相应的位置
        {
            return s ;
        }
        s++;
    }
    return NULL;
}