No.22 括弧の対応

■■■問題■■■

Orinoは、テキストの括弧の対応箇所を見つけるプログラムを書きたいと思っている。

括弧の対応とは、
1.与えられた文字列から、「(」の直後に「)」が来る文字があるとき、文字列からその2つの文字を削除する。
2.削除された文字を新たな文字列として、1.の処理を繰り返し、文字列が空になるまで繰り返す。

そして、初めに与えられた文字列として考えた時のi番目文字と一緒に削除される
j番目に対応する文字が「括弧の対応」であるとする。

「(」と「)」のみで構成されるN文字の文字列が与えられ、
さらに整数値K (1 <= K <= N)が与えられる。

このとき、K番目の文字と対応する文字の箇所の番目を求めてください。

与えられる文字列は、すべての文字で括弧の対応があると保証されるとする。

■■■入力■■■

N K
S

1行目は 文字数を表すN (1 <= N <= 10000)と、
指定された文字の番号K (1 <= K <= N)がスペース区切りで与えられる。
2行目は、実際の文字を表す文字列が与えられる。この文字列は「(」または「)」であることが保証される。

■■■出力■■■

答えの整数値を最後の改行を含め出力してください。
最後に改行してください。

C#のソース

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static string InputPattern = "Input1";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("4 4");
            WillReturn.Add("(())");
            //1
            //「(())」の文字の4番目は、「)」である、このとき対応する文字は1番目の「(」である
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("12 2");
            WillReturn.Add("(((())()())) ");
            //11
            //「(((())()())) 」という文字列の2番目の文字は「(」である。
            //このとき対応する文字は11番目の「)」である。
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("20 5");
            WillReturn.Add("((((((()))))))(()())");
            //10
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        int K = InputList[0].Split(' ').Select(X => int.Parse(X)).Last();
        string S = InputList[1];

        //開き括弧をスタックにPushし、
        //閉じ括弧ならPopすれば、対応が分かる
        var stk = new Stack<int>();

        for (int I = 0; I <= S.Length - 1; I++) {
            if (S[I] == '(') stk.Push(I);
            if (S[I] == ')') {
                int wkPair = stk.Pop();
                if (K - 1 == I) Console.WriteLine(wkPair + 1);
                if (K - 1 == wkPair) Console.WriteLine(I + 1);
            }
        }
    }
}

解説

スタックで開き括弧の場所を記憶してます。