2929.md

括号匹配 2929: 扩号匹配

题目要求判断给定序列中每一个右括号匹配的左括号的位置。

题目来源

2929: 扩号匹配

总时间限制: 1000ms 内存限制: 65536kB

描述

判断一组匹配的左右扩号序列中，每一个右扩号与之相匹配成对的左扩号是整个扩号序列的第几个扩号。输出所有判断结果。

输入

输入有两行。

第一行输入一个整数（该整数必定是偶数），该整数表示扩号序列中一共有多少个扩号。

第二行输入用1和2分别代表左右扩号的扩号序列。例如输入序列11211222，表示扩号序列(()(()))。

输出

输出为一行。即挨个输出每个2（右扩号‘）’）与之相匹配的1（左扩号‘（’）在扩号序列中是第几个，用空格格开。

样例输入

4
1212
4
1122
6
112122
8
11211222
20
11211122122121122212

样例输出

1 3
2 1
2 4 1
2 5 4 1
2 6 5 9 4 12 15 14 1 19

每一个右括号需要匹配左边距离它最近的左括号，因此可以考虑使用堆栈结构来处理，每次遇到一个左括号将其入栈，当匹配了一个右括号后出栈，栈中存储的是左括号的位置。

#include <iostream>
using namespace std;
int main() {
	int n, i;
	while (cin >> n) {
		char *data = new char[n + 1];
		cin >> data;
		int *stack = new int[n / 2], idx = 0;
		for (i = 0; i < n; ++i) {
			if (data[i] == '1') {
				stack[idx++] = i;
			}
			else {
				cout << stack[idx-- - 1] + 1 << " ";
			}
		}
		cout << endl;
		delete[] stack;
		delete[] data;
	}
	return 0;
}

2929.cpp 代码长度：379B 内存：128kB 时间：1ms 通过率：97% 最小内存：128kB 最短时间：0ms

可以采用标准模板库，这里我就自己用数组实现了一下简单的功能，用动态内存来分配，读取的时候由于不知道有多少位所以还是得用字符串存储，需要一个下标来标识栈顶。

有任何的改进意见欢迎大家在微信平台公众号主页面留言或者发表issue。