/* ACMプログラミングコンテスト 2011 国内予選 【 世界の天秤 】 ■ 問題 文字列の中で、括弧が対応していることをチェックする。括弧は2種類あり、()と[]がある。どちらについても対応していなければいけない。 ただこの「対応」が一般的な対応とは少し違う。例えば([)]は、どちらの括弧も始まりと終わりがあり対応しているのであるが、 この問題の場合には、対応していない、となる。それは、()であっても[]であっても”その間の文字の中”で、 また括弧が対応していなければいけない、という制約だからである。 ■ 解答例 この問題は、FIFO (First in, First out)を使って解決することができる。このFIFOには、期待する終わり括弧を入れておく。 例えば文字列を最初から走査し、 "(" を発見すると、 ")" があることを期待してFIFOに入れる。そして次に ")" を見つければ、 FIFOから ")" を取り出して、対応関係は問題が無いと判定する。 "([)]" の場合には、最初の "(" を発見し、FIFOに ")" を入れる。次の "[" を発見し、 "]" をFIFOに入れる。 この時点でFIFOには上から順に "]" ")" の順で終わり括弧が格納されている。次に ")" を見つけた時にFIFOの最上位と 違う種類の括弧であるため、対応が取れていないと判定される。 "(" の場合には、"(" を読み込んでFIFOに ")" を入れる。そして文字列は終了するため、FIFOにデータ残った状態になり、その事をもって 対応が取れていないと判定する。 */ import java.io.*; import java.util.*; public class Exp2011_B { public static void main(String[] args) throws Exception{ BufferedReader br = new BufferedReader(new FileReader(args[0])); while(true){ String line = br.readLine(); if(line.charAt(0)=='.'){ break; } boolean yes = true; Vector tofind = new Vector(); for(int cnt=0;cnt