難しい。スタックかキューの考え方を適用すべきなんやろうし、大学の時学んだコンパイラの字句解析
にも似とんやろうし、プログラミングの基礎と呼べる概念なんやろうけど、解けん。
大学の「コンパイラ」の実習がちゃんと、というか最低限出来てればこれは簡単に解けたはず。
とりあえず、完答出来てないけど、一旦答えを提出した。
1st
| Correctness | Performance | Task Score |
|---|---|---|
| 0% | 0% | 0% |
function solution($S) {
$ans = 0;
// rb: round bracket, sb: square bracket, br: brace
$rb = $sb = $br = 0;
// Split by one
$A = str_split($S, 1);
$N = count($A);
if(0 != ($N % 2)) {
return $ans;
}
while(($c = array_shift($A)) == true) {
if($c = '(' && $rb == 0) { $rb++; }
if($c = '[' && $sb == 0) { $sb++; }
if($c = '{' && $br == 0) { $br++; }
if($c = '}') { $br--; }
if($c = ']') { $sb--; }
if($c = ')') { $rb--; }
}
if(($rb || $sb || $br) == 0) {
$ans = 1;
} else {
$ans = 0;
}
return $ans;
}
考え方は、左括弧が出てきたら変数を１増分し、それに対応する右括弧が出てきたら、その変数を１減少
させる。これだと、単純に括弧を数えただけで、例題のような ([)()] に対応出来ない。
よって、もちろん、再考する。
2nd
| Correctness | Performance | Task Score |
|---|---|---|
| 100% | 100% | 100% |
function solution($S) {
$stack = array();
for($i = 0; $i < strlen($S); $i++) {
if( (($S{$i}==')') and (end($stack)=='(')) or
(($S{$i}=='}') and (end($stack)=='{')) or
(($S{$i}==']') and (end($stack)=='[')) )
array_pop($stack);
else
array_push($stack, $S{$i});
}
if(empty($stack))
return 1;
else
return 0;
}
このコードは、smknstdさんのものを丸パクリしたものです。（整形はしたけど）
要諦だけ説明すると、閉じ括弧が来るまでスタックに push し、閉じ括弧が来たら、スタックの top に
対応する開き括弧があるか調べ、あれば pop する。うむ、確かにこれで良い。
ついでに、他のコードも眺めてみた。
def solution(S):
if len(S) % 2 == 1: return 0
matched = {"]":"[", "}":"{", ")": "("}
to_push = ["[", "{", "("]
stack = []
for element in S:
if element in to_push:
stack.append(element)
else:
if len(stack) == 0:
return 0
elif matched[element] != stack.pop():
return 0
if len(stack) == 0:
return 1
else:
return 0
よお出来とるなあ。開き括弧ならスタックにプッシュし、閉じ括弧なら以下２パターンの処理に移る。
- スタックの長さが０の場合
-
matched配列の値とスタックのトップの値が異なる場合
これは両方０を返す。つまり、閉じ括弧が来たのに、スタックが空（＝閉じ括弧先行）の場合と、
スタックは空でないものの、想定される閉じ括弧とスタックのトップにある閉じ括弧が異なる場合の２つ。
後者があり得るのは、閉じ括弧が連続で現れ、かつスタックに、それらに対応する開き括弧がないケース。
()) のように、閉じ括弧が開き括弧より多い場合に、return 0 する、ということ。
そして、正しく対応する括弧があった場合は、pop() されるだけ。最終的に、スタックの長さが０の
場合は、すべて括弧が正しく対応していた、ということで return 1 、そうでなければ return 1 。
この「そうでなければ」に該当するのは、開き括弧が多かった場合。つまり、(() など。
さらに、これは俺も実装したけど、最初に長さが偶数でないときは０を返すという処理がある。
これのおかげで、無駄な計算はだいぶ省かれる。
所感
お手本コードさんたち、発想が俺と全然ちゃう。どうやったらそんな美しい発想になる？
あと、Python のコードは美しい。プログラマを煩わせる ;, {, } がない。趣味で書くのは Python が
ええなあ。とりあえず、しばらくは先人のコードに触れて少しずつ自身のコードを美化していく他は
なさそうですが。