鉄則本 B51 - Bracket (3Q, ★4)

スタックを用いて、かっこの対応をとる問題！

• 問題へのリンク

問題概要

対応のとれているカッコ列 が与えられる。対応する左かっこ '(' と右かっこ ')' が、それぞれ の何番目と何番目であるかを順に求めよ。

制約

• 

メモ

詳しい解説はここにあるのでメモ程度に。

github.com

スタックには左カッコ '(' に対応する index を格納していく。')' に対応する '(' の index は、スタックの末尾にある要素を見ていけば良い。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    string S;
    cin >> S;
    vector<int> stk;
    for (int i = 0; i < S.size(); i++) {
        if (S[i] == '(') stk.push_back(i);
        else {
            cout << stk.back()+1 << " " << i+1 << endl;
            stk.pop_back();
        }
    }
}