首页 > 代码库 > Hihocoder1458-Parentheses Matching(stack，vector)
Hihocoder1458-Parentheses Matching(stack，vector)
时间限制: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)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。