AOJ 1173: 世界の天秤 / The Balance of the World

競技プログラミング AOJ ICPC Stack 括弧列

問題

問題文

問題概要

丸括弧と角括弧の二種類の括弧を含む文字列が与えられる. 括弧列が整合しているか判定せよ.

ただしここで, 括弧列が整合しているとは以下を満たしていることを言う.

  • すべての左丸括弧には, 対応する右丸括弧がそれより後にある.
  • すべての左角括弧には, 対応する右角括弧がそれより後にある.
  • すべての右括弧には, 対応する左括弧がある.
  • 括弧の対応は一対一でなくてはならず, 単一の括弧が複数の括弧と対応することはない.
  • すべての対応する左括弧と右括弧の組について, その間にある文字列の中で括弧がバランスしている.

制約

  • データセットの数: 不明
  • 一行あたりの文字列の長さ |S|: |S| \leq 100

解答例

指針

  • Stack を使う

解説

超典型問題.

Stack を使って以下のような処理をすれば, 括弧列の整合性を判定できる.

与えられた文字列を先頭から順に一文字ずつ走査し, 括弧以外は無視, 文字が

  • 左丸括弧だった場合: Stack に push
  • 左角括弧だった場合: Stack に push
  • 右丸括弧だった場合:
    • Stack の top が左丸括弧だった場合: Stack を pop (Stack の top を取り出す)
    • Stack の top が左丸括弧ではなかった場合: 不整合

  • 右角括弧だった場合:

    • Stack の top が左角括弧だった場合: Stack を pop (Stack の top を取り出す)
    • Stack の top が左角括弧ではなかった場合: 不整合

  • 最後に Stack が空ではなかった場合: 不整合 (左括弧が余るパターン)

これをそのまま実装すればいい.

なお, 括弧列の種類が一つの場合は, カウンタ変数を一つ用意するだけで実装を簡略化でき, 明示的に Stack を用いる必要はない.

今回は2種類の括弧 (丸括弧と角括弧) があるのでその方法では以下のように, 括弧列それぞれは整合しているが, 括弧列の内部が整合していない場合に対応できない.

([)]
  • C++ による実装例
// submission: https://onlinejudge.u-aizu.ac.jp/status/users/kira924age/submissions/1/1173/judge/4078299/C++

#include <iostream>
#include <string>
#include <stack>

using namespace std;

int main() {
  while (true) {
    string s;
    getline(cin, s);
    if (s == ".") { break; }

    bool is_valid = true;

    stack<char> st;

    for (int i = 0; i < s.length(); i++) {
      if (s[i] == '(') { st.push(s[i]); }
      if (s[i] == ')') {
        if ( st.empty() || st.top() != '(') {
          is_valid = false;
          break;
        }
        st.pop();
      }
      if (s[i] == '[') { st.push(s[i]); }
      if (s[i] == ']') {
        if (st.empty() || st.top() != '[') {
          is_valid = false;
          break;
        }
        st.pop();
      }
    }
    if (!st.empty()) { is_valid = false; }
    cout << ( is_valid ? "yes" : "no") << endl;
  }

  return 0;
}
  • Python3 による実装例
# submission: https://onlinejudge.u-aizu.ac.jp/status/users/kira924age/submissions/1/1173/judge/4078313/Python3

while True:
    s = input()
    if s == ".": break

    st = []
    is_valid = True
    for c in s:
        if c == "(": st.append(c)
        if c == "[": st.append(c)
        if c == ")":
            if (not st) or st[-1] != "(":
                is_valid = False
                break
            else:
                st.pop()
        if c == "]":
            if (not st) or st[-1] != "[":
                is_valid = False
                break
            else:
                st.pop()
    if st:
        is_valid = False

    print( "yes" if is_valid else "no" )
  • Go による実装例
// submission: https://onlinejudge.u-aizu.ac.jp/status/users/kira924age/submissions/1/1173/judge/4078359/Go

package main

import (
    "bufio"
    "fmt"
    "os"
)

var sc = bufio.NewScanner(os.Stdin)

func nextString() string {
    sc.Scan()
    return sc.Text()
}

func main() {
    sc.Buffer(make([]byte, 0), 1000000009)

    for {
        var s string
        s = nextString()
        if s == "." {
            break
        }
        var st []byte
        is_valid := true

        for _, value := range s {
            if value == '(' {
                st = append(st, byte(value))
            }
            if value == '[' {
                st = append(st, byte(value))
            }
            if value == ')' {
                if len(st) == 0 || st[len(st)-1] != '(' {
                    is_valid = false
                    break
                } else {
                    st = st[:len(st)-1]
                }
            }
            if value == ']' {
                if len(st) == 0 || st[len(st)-1] != '[' {
                    is_valid = false
                    break
                } else {
                    st = st[:len(st)-1]
                }
            }
        }
        if len(st) != 0 {
            is_valid = false
        }
        if is_valid {
            fmt.Println("yes")
        } else {
            fmt.Println("no")
        }
    }
}