バニッシュ・スタンダードの中村です。
最近はアルゴリズムとデータ構造に興味があってコツコツ学んでいます。
LeetCodeやAtCoderをGoで解いたり、最近はC++を学んでいるのでたまにC++で解いたりしています。
LeetCodeの問題を解いているとスタックを扱う問題に出会って、スタックってどうやって実装できたかな？と思考が詰まったのもあり整理してみようと思いました。
Golangにはスタックを直接的にサポートするデータ構造はないので、スライスを使って擬似的にスタックを実装してみたいと思います。
スタックとは
LIFO（Last-In-First-Out）なデータ構造です。
最後に追加した要素を最初に取り出します。
現実世界でいうと、皿を積み重ねて一番上から皿を取る、これもスタックですね。
スタックは配列といった動的なデータ構造を使って実装することができます。
スタックは2つの基本操作であるPush(要素の追加)・Pop(要素の取り出し)を持ちます。
問題
で、今回題材にする問題は以下です。
{, [, (, }, ], )←こういうブラケットを組み合わた文字列sが入力で渡されるので、ブラケットの組み合わせが正しいかを調べます。
例えば入力値sが{}()[]ならtrueを返しますし、{}[)ならfalseを返すような関数を作ります。
やっていき
まずはこんな感じの関数を書いてみました。
func IsValidParentheses(s string) bool {
/*
ブラケットの組み合わせが正しいなら文字数は偶数になるので、バリデーションをかけておく
*/
if len(s)%2 == 1 {
return false
}
/*
文字列sを頭から２個ずつ取り出して、ブラケットの組み合わせが正しいか確認する
*/
for i := 0; i < len(s)-1; i += 2 {
switch s[i] {
case '(':
if s[i+1] != ')' {
return false
}
case '[':
if s[i+1] != ']' {
return false
}
case '{':
if s[i+1] != '}' {
return false
}
}
}
return true
}
さて、この関数は要件を満たせているでしょうか？
.
.
.
結論から言うと「要件を満たせていません」。
この関数は論理エラーを引き起こします。
どこで間違えたのでしょうか？
そもそも入力値のブラケットの組み合わせの想定が足りてなく、{([])}でもtrueを返すような関数を作らないとダメですね。
スタックを実装してみる
ここでスタックの出番です。
かっこが続く場合はスタックに溜めていき、閉じかっこがくればスタックから1つずつ取り出して、ブラケットの組み合わせが正しいか確認していけばよさそうですね。
いよいよスタックを使う形で実装してみます。
func IsValidParentheses(s string) bool {
if len(s)%2 == 1 {
return false
}
var stack []rune
for _, v := range s {
switch v {
case '(', '{', '[':
stack = append(stack, v) // スタックに詰める
case ')', '}', ']':
if len(stack) == 0 {
return false
}
top := stack[len(stack)-1] // スタックから取り出す
stack = stack[:len(stack)-1] // 後処理
if !((top == '(' && v == ')') || (top == '{' && v == '}') || (top == '[' && v == ']')) {
return false
}
}
}
// スタックが空であればブラケットはバランスが取れていると判断
if len(stack) > 0 {
return false
}
return true
}
無事、LeetCodeで提出してAcceptedしました。
（関数名は都合上isValidにする必要があります）
ユーザー定義型を導入してみる
問題を解くだけならこれでもいいですが、ユーザー定義型を導入するとこんな感じになります。
type Stack []rune
// Goの関数は値渡しなのでポインタを介してスタックを更新
func (s *Stack) Push(value rune) {
*s = append(*s, value)
}
func (s *Stack) Pop() (rune, bool) {
if len(*s) == 0 {
return 0, false
}
top := (*s)[len(*s)-1]
*s = (*s)[:len(*s)-1]
return top, true
}
func IsValidParentheses(s string) bool {
if len(s)%2 == 1 {
return false
}
var stack = Stack{}
for _, v := range s {
switch v {
case '(', '{', '[':
stack.Push(v) // スタックに詰める
case ')', '}', ']':
top, ok := stack.Pop() // スタックから取り出す
if !ok {
return false
}
if !((top == '(' && v == ')') || (top == '{' && v == '}') || (top == '[' && v == ']')) {
return false
}
}
}
// スタックが空であればブラケットはバランスが取れていると判断
if len(stack) > 0 {
return false
}
return true
}
Genericsを使ってみる
先ほどまでは具象型でスタックを作っていたので、より汎用的に使えるようにGenericsを導入するとこんな感じになりました
type Stack[T any] []T
// Goの関数は値渡しなのでポインタを介してスタックを更新
func (s *Stack[T]) Push(value T) {
*s = append(*s, value)
}
func (s *Stack[T]) Pop() (T, bool) {
if len(*s) == 0 {
var zero T
return zero, false
}
top := (*s)[len(*s)-1]
*s = (*s)[:len(*s)-1]
return top, true
}
func IsValidParentheses(s string) bool {
if len(s)%2 == 1 {
return false
}
var stack = Stack[rune]{}
for _, v := range s {
switch v {
case '(', '{', '[':
stack.Push(v) // スタックに詰める
case ')', '}', ']':
top, ok := stack.Pop() // スタックから取り出す
if !ok {
return false
}
if !((top == '(' && v == ')') || (top == '{' && v == '}') || (top == '[' && v == ']')) {
return false
}
}
}
// スタックが空であればブラケットはバランスが取れていると判断
if len(stack) > 0 {
return false
}
return true
}
以下の判定処理もいい感じにできそうですが、力尽きたのでこの辺で...
if !((top == '(' && v == ')') || (top == '{' && v == '}') || (top == '[' && v == ']')) {
return false
}
最後に
元々アルゴリズムとデータ構造には苦手意識があったこともあり、今年はちゃんと理解できるまで時間つくって向き合おうと思います。
まずは簡単なものから取り組んでいるのですが、スラスラ解けなくて勉強になりました...
分からなかったことが分かるようになっていく過程は楽しいですね！
あ、アルゴリズムでいうと最近は結城浩さんの数学ガール/乱拓アルゴリズムを読んでいます。
まだ途中なのですがアルゴリズムだけでなく数学ってこんなに面白かったんだって実感しています。
物語形式なので肩肘はらずにリラックスして楽しめます。おすすめなのでよかったら読んでみてください。
他にもシリーズがあり、数学ガールの秘密ノートは月500円で読み放題プランがあるみたいです。
物理本も販売されてます。
Discussion