长春建设厅网站首页,搭建网站原理,网站策划的最终体现,微信网站制作系统目录
题目
算法
完整代码 题目 参考
递归:
https://blog.csdn.net/qq_45272251/article/details/103257953
利用了递归, 但思路稍复杂了
循环:
https://blog.csdn.net/weixin_50340097/article/details/114579805
(看起来是递归其实是循环. 每次递归其实是循环内一次迭…目录
题目
算法
完整代码 题目 参考
递归:
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)左括号入栈: 调用递归栈从下一个位置开始寻找左括号. startpos1, leftnumleftnum1. (2)若左括号匹配成功. 配对的左右括号记录为 . 从已经找到的右括号右侧继续下一次循环. (3)若左括号匹配失败, 出栈(返回匹配失败记号0). (所调用的递归已遍历到字符串结束.)
2.如果当前下标对应字符串是)记录为? (1)若栈非空(leftnum!0), 左括号出栈: 即递归函数返回(返回值右括号位置pos). (2)若栈空(leftnum0): 没有左括号时说明在递归最外层, 不返回, 继续循环.
3、如果当前下标对应的字符既不是(也不是)记录为 . 完整代码
#include bits/stdc.h
using namespace std;
#define MAXN 105char str2[MAXN];
char state[MAXN];int match(int start, int leftnum){int right0;if(startstrlen(str2))//匹配到最后返回return 0;for(int posstart;posstrlen(str2);pos){if(str2[pos](){//情况1.出现左括号state[pos]$;//记录未匹配的左括号rightmatch(pos1,leftnum1);printf((:%d; ):%d\n,pos,right);if(right0){//匹配成功state[pos] ;state[right] ;posright;//跳过上次找过的地方}else{//如果到最后都没有找到, 说明整个字符串都被遍历过了return 0;}// match(right1,leftnum);//没有需要匹配的左括号就不入递归栈// break;}else if(str2[pos])){//情况2. 出现右括号state[pos]?;// printf():%d\n,pos);// match(pos1);//永远由左括号触发下一层递归入栈, 右括号控制出栈if(leftnum0){//栈非空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);coutendl;}return 0;
}运行效果:
