演習課題「括弧列判定」
N 文字の 括弧列 S が与えられます。与えられた 括弧列 が 正しい括弧列 かどうか判定してください。
ここで、 括弧列 とは以下のように定義します。
* ( または ) または空文字のみで構成される文字列
また、 正しい括弧列 とは以下のように定義します。
1. 空文字列は正しい括弧列である。
2. 文字列 s が正しい括弧列であるとき、 ( + s + ) は正しい括弧列である。
3. 文字列 s , t が正しい括弧列であるとき、 s + t は正しい括弧列である。
たとえば、以下の文字列はすべて 正しい 括弧列です。
()
(())
()()
(()())
((((())())()))
また、以下の文字列はすべて 正しくない 括弧列です。
)(
(
())
((())
(()()))((()())()
入力される値
N
S
条件
すべてのテストケースにおいて、以下の条件をみたします。
・ N は 1 以上 50,000 未満
・ S の各文字は
( または ) 期待する出力
S が正しい括弧列の場合は
Yes を、正しくない括弧列の場合は No を出力してください。末尾には改行を入れ、余計な文字、空行を含んではいけません。Yes
または
No
期待する出力値
No
＃04:スタックの活用例
このチャプターでは、スタックの活用例について学習します。
paiza のレベルアップ問題集にもスタックを使って解く問題がいくつかあります。
ぜひ取り組んでみてください。
スタック・キュー問題集
https://paiza.jp/works/mondai/stack_queue
深さ優先・幅優先探索問題集
https://paiza.jp/works/mondai/bfs_dfs_problems
スタックは深さ優先探索を行う際によく登場します。
深さ優先・幅優先探索問題集という問題集があるので、ぜひ覗いてみてください。
この括弧列の定義を考えると、ある時点までにペアになっていない一番最後の ( が、次に現れる ) に対応していることが、正しい括弧列の条件となります。
ペアになっていない最後の ( と次に現れる ) が対応しない、全体としては正しい括弧列が存在すると仮定してみましょう。
この 2 つの文字の間に文字列 X が存在すると仮定すると、( X ) という構造になります。
括弧列のルールより、X は正しい括弧列である必要があります。
ここからは X が空文字列かで場合分けを行います。
・X が空文字列である場合
( X ) は () となるので、この括弧列は正しいです
・X は空文字列でない場合
X が正しい括弧列である場合 ( と ) がそれぞれ少なくとも 1 つ以上含まれます。
しかし、最後に現れる ( が X の中に含まれるので、( X ) の ( が最後の ( であるという仮定に矛盾します。
よって、X は空文字列である場合にのみ ( X ) は正しい括弧列となるので、
ペアになっていない最後の ( と次に現れる ) は対応する必要があります。
コードimport java.util.*;
public class Main{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
String s = sc.next();
Deque<Character> stack = new ArrayDeque<Character>();
for (int i = 0; i < n; i++) {
if(s.charAt(i) == '('){
stack.push(s.charAt(i));
}else if (stack.size() > 0 && stack.peek() == '(') {
stack.pop();
}
}
sc.close();
}
}