时间限制:10000ms
单点时限:1000ms
内存限制:256MB
Given a string of balanced parentheses output all the matching pairs.
A string consisting of only parentheses ‘(‘ and ‘)’. The parentheses are balanced and the length of the string is no more than 100000.
For each pair of matched parentheses output their positions in the string.
(())()()
1 4
2 3
5 6
7 8
输出可以匹配的每一对括号的位置，按照左括号位置升序输出
用stack标记’(‘的位置，扫一遍，遇到’)’就匹配最近的’(‘，用vector来存数对。
#include<bits/stdc++.h> using namespace std; int main() { stack<int> p; char s[100100]; while(~scanf("%s", s)) { vector<pair<int, int> > aa; int len = strlen(s); while(!p.empty()) p.pop(); for(int i = 0; i < len; i++) { if(s[i] == ‘(‘) p.push(i + 1); else if(s[i] == ‘)‘) { int x = p.top(); p.pop(); aa.push_back(pair<int, int>(x, i + 1)); } } sort(aa.begin(), aa.end()); for(int i = 0; i < aa.size(); i++) { printf("%d %d\n", aa[i].first, aa[i].second); } } return 0; }
Hihocoder1458-Parentheses Matching(stack，vector)
原文：http://www.cnblogs.com/zhien-aa/p/6274952.html