POJ3704 括号匹配问题 递归方法

目录

题目

算法

完整代码

---

题目

参考

递归:

https://blog.csdn.net/qq_45272251/article/details/103257953

利用了递归, 但思路稍复杂了

循环:

https://blog.csdn.net/weixin_50340097/article/details/114579805

(看起来是递归其实是循环. 每次递归其实是循环内一次迭代, 没有使用递归的精髓)

https://blog.csdn.net/qq_38851184/article/details/104252592

循环这篇文章的收获, 额外定义状态数组记录对应位置是否匹配.

本文利用递归栈的特性, 力求简明快速地解决这个问题.

算法

首先定义全局变量

(1)待匹配的字符串str2；

(2)定义字符数组state用来记录每个位置的匹配状态. (尚未匹配上的全部标注为$或? , 待匹配上后改回来.)

递归函数输入参数

(1)查找开始位置start

(2)未匹配左括号个数(递归栈内剩余元素)leftnum

递归函数返回值

右括号位置('0'代表无可匹配的右括号)

递归算法流程:

1.如果当前下标对应字符串是'('，记录为'$'

        (1)左括号入栈: 调用递归栈从下一个位置开始寻找左括号. start=pos+1, leftnum=leftnum+1.

        (2)若左括号匹配成功. 配对的左右括号记录为' '. 从已经找到的右括号右侧继续下一次循环.

        (3)若左括号匹配失败, 出栈(返回匹配失败记号0). (所调用的递归已遍历到字符串结束.)

2.如果当前下标对应字符串是')'，记录为'?'

        (1)若栈非空(leftnum!=0), 左括号出栈: 即递归函数返回(返回值右括号位置pos). 

        (2)若栈空(leftnum==0): 没有左括号时，说明在递归最外层, 不返回, 继续循环.

3、如果当前下标对应的字符既不是'('也不是')'，，记录为' '.

完整代码

#include <bits/stdc++.h>
using namespace std;
#define MAXN 105char str2[MAXN];
char state[MAXN];int match(int start, int leftnum){int right=0;if(start>=strlen(str2))//匹配到最后返回return 0;for(int pos=start;pos<strlen(str2);pos++){if(str2[pos]=='('){//情况1.出现左括号state[pos]='$';//记录未匹配的左括号right=match(pos+1,leftnum+1);printf("(:%d; ):%d\n",pos,right);if(right>0){//匹配成功state[pos]=' ';state[right]=' ';pos=right;//跳过上次找过的地方}else{//如果到最后都没有找到, 说明整个字符串都被遍历过了return 0;}// match(right+1,leftnum);//没有需要匹配的左括号就不入递归栈// break;}else if(str2[pos]==')'){//情况2. 出现右括号state[pos]='?';// printf("):%d\n",pos);// match(pos+1);//永远由左括号触发下一层递归入栈, 右括号控制出栈if(leftnum>0){//栈非空return pos;}}else{//情况3. 左右括号都不是state[pos]=' ';}}return 0;
}int main()
{while(gets(str2)){memset(state,'\0',sizeof(state));match(0,0);puts(str2);puts(state);cout<<endl;}return 0;
}

运行效果: