Coursera 学习记录 ：排队游戏（通过递归调用的括号匹配问题以及while循环的巧用）
描述
在幼儿园中，老师安排小朋友做一个排队的游戏。首先老师精心的把数目相同的小男孩和小女孩编排在一个队列中，每个小孩按其在队列中的位置发给一个编号（编 号从0开始）。然后老师告诉小朋友们，站在前边的小男孩可以和他后边相邻的小女孩手拉手离开队列，剩余的小朋友重新站拢，再按前后相邻的小男孩小女孩手拉 手离开队列游戏，如此往复。由于教师精心的安排，恰好可以保证每两个小朋友都能手拉手离开队列，并且最后离开的两个小朋友是编号最小的和最大的两个小朋 友。（注：只有小男孩在前，小女孩在后，且他们两之间没有其他的小朋友，他们才能手拉手离开队列）。
请根据老师的排队，按小女孩编号从小到大的顺序，给出 所有手拉手离开队列的小男孩和小女孩的编号对。
输入
用一个字符串代表小朋友队列。字符串中只会出现两个字符（样例输入里用的是 括号但实际数据则不一定），
分别代表小男孩和小女孩，首先出现的字符代表小男孩，另一个字符代表小女孩。小孩总数不超过100
输出
按小女孩编号顺序，顺序输出手拉手离开队列的小男孩和小女孩的编号对，每行一对编号，编号之间用一个空格分隔。
样例输入
((()(())())(()))
样例输出
2 3
5 6
4 7
8 9
1 10
12 13
11 14
0 15
最终思路：
最重要的两点：
1、函数返回值的作用一定要清楚，并且意识到这个返回值会在之后用到。
2、while的循环，只要满足条件就会继续进行。（这一点我最开始忽略了，走了很多弯路）
观察((()(())())(()))，会发现：女孩子的出现决定是否会配对离开，所以就可以在出现男孩子的位置进行函数调用，如果一直是男孩子，就一直调用，直到女孩子的出现。
女孩子的出现会匹配走它前面的男生，所以直接输出就可以，然后返回值指向下一个，否则返回的还是男生那个位置。
然后就是while函数神奇作用了，如果是女生，就会往下进行，如果是男生就继续循环。
并且关键的，使用i和j两个来计数，就保证了i记录住了男生的位置，通过满足条件，不断地配对离开，直至调用全部结束。
//简单的说，就是只有两种符号的数组，然后进行符号的匹配
//输出的正好组成一对的标号
//使用递归调用来思考,并且同样使用getline来获得数据
#include<iostream>
using namespace std;
/*
char line[100];
int i = 0;
int j = 1;
int reline(int i, int j) {
if (line[i] == line[j]) {
i++;
j++;
reline(i, j);
}
if (line[i] != line[j] && line[j] != '\0') {
cout << i << j << endl;
i--;
j++;
reline(i, j);
//这个方法进行到这，就发现问题了，无法实现自动的减去并且保持序号不变。
//所以，考虑能否先将女孩子的编号全部找出，然后再匹配呢？
//采用ij两个变量，仍然有问题
}
}
int main() {
cin.getline(line,100);
//方法失败，重新思考
}
*/
//重新整理思路，第一个符号表示男孩，但是后面的情况不知道，而男孩女孩匹配成功的前提是，只要出现了一个女孩，就可以和前面的男孩匹配
//所以，可以一个个往后看，只要出现一次女孩就往前匹配走一个男孩
char line[100];
char boy;
// ((()(())())(()))
int reline(int i) {
int j = i + 1;//1
//需要有两个记录
while (line[j] == boy) {
j = reline(j);//2 6
}
if (line[j] != boy && line[j] != '\0') {
cout << i << ' ' << j << endl;//3
return j + 1;//4
}
else {
return j;//5
}
}
int main() {
cin.getline(line, 100);
boy = line[0];
reline(0);
return 0;
}
查看8道真题和解析
