括弧列

今回は paiza の「括弧列」の問題に挑戦！

🟦 問題概要

🔹 やること

• 長さ N の括弧列 S が与えられる
• S が 正しい括弧列かどうか を判定する

🔹 括弧列とは

• 文字は ( と ) のみ
• 他の文字は出ない

🔹 正しい括弧列の定義

次を満たすもの：

1. 空文字列は正しい括弧列である。
2. 文字列 s が正しい括弧列であるとき、 ( + s + ) は正しい括弧列である。
3. 文字列 s , t が正しい括弧列であるとき、 s + t は正しい括弧列である。

正しい：

()
(())
()()
(()())
((((())())()))

正しくない：

)(
(
())
((())
(()()))((()())()

正しい括弧列とは：

• 途中で閉じすぎない
• 最後に開きが残らない

🔹 入力

N
S

• N：文字数
• S：括弧列

🔹 出力

• 正しい → Yes
• 正しくない → No

🔹 条件

• 1 ≤ N < 50,000
• 文字は ( または )
  
  
  

入力例:

4
(())

出力例:

Yes

✅OK例：

const rl = require('readline').createInterface({ input: process.stdin });

const lines = [];
rl.on('line', line => lines.push(line));

rl.on('close', () => {
    const N = Number(lines[0]);
    const S = lines[1];

    const stack = [];

    for (let i = 0; i < N; i++) {
        const A = S[i];

        // スタックが空でない かつ
        // 末尾が '(' で 今読んだ文字が ')'
        if (
            stack.length > 0 &&
            stack[stack.length - 1] === '(' &&
            A === ')'
        ) {
            stack.pop(); // 対応するので削除
        } else {
            stack.push(A); // それ以外は積む
        }
    }

    // 最後に何も残らなければ正しい括弧列
    if (stack.length === 0) {
        console.log("Yes");
    } else {
        console.log("No");
    }
});

🔍コードの流れ

• 入力を受け取る
  • N（文字数）
  • S（括弧列）
• 空のスタックを用意する
• 文字列 S を左から1文字ずつ見る
  • 今の文字を A とする
  • もし
    → スタックから1つ取り出す（() を削除）
    • スタックが空でなく
    • スタックの一番上が '(' で
    • 今の文字が ')' なら
  • それ以外なら
    → 今の文字をスタックに積む
• ループ終了後
  • スタックが空なら → "Yes"
  • 空でなければ → "No"

📝まとめ

① 正しい括弧列とは

正しい ⇔ 次の2つを満たす

• 途中で ) が多くならない
• 最後に ( と ) の数が同じ

② スタックの使いどころ

• ( を積む
• ) が来たら対応できれば消す

③ スタックの意味

• stack の中身 ＝「まだ閉じられていない括弧」
• stack が空 ＝ すべて正しく対応済み