AOJ 1173 世界の天秤

問題へのリンク

C#のソース

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("So when I die (the [first] I will see in (heaven) is a score list).");
            WillReturn.Add("[ first in ] ( first out ).");
            WillReturn.Add("Half Moon tonight (At least it is better than no Moon at all].");
            WillReturn.Add("A rope may form )( a trail in a maze.");
            WillReturn.Add("Help( I[m being held prisoner in a fortune cookie factory)].");
            WillReturn.Add("([ (([( [ ] ) ( ) (( ))] )) ]).");
            WillReturn.Add(" .");
            WillReturn.Add(".");
            //yes
            //yes
            //no
            //no
            //no
            //yes
            //yes
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();

        var ResultList = new List<bool>();
        foreach (string EachStr in InputList) {
            if (EachStr == ".") break;
            ResultList.Add(IsValanced(EachStr));
        }

        var sb = new System.Text.StringBuilder();
        foreach (bool EachBool in ResultList) {
            sb.AppendLine(EachBool ? "yes" : "no");
        }
        Console.Write(sb.ToString());
    }

    static bool IsValanced(string pStr)
    {
        var Stk = new Stack<char>();

        foreach (char EachChar in pStr) {
            if (EachChar == '(' || EachChar == '[') {
                Stk.Push(EachChar);
            }

            if (EachChar == ')') {
                if (Stk.Count == 0) {
                    return false;
                }
                if (Stk.Peek() != '(') {
                    return false;
                }
                Stk.Pop();
            }

            if (EachChar == ']') {
                if (Stk.Count == 0) {
                    return false;
                }
                if (Stk.Peek() != '[') {
                    return false;
                }
                Stk.Pop();

            }
        }
        return Stk.Count == 0;
    }
}

解説

チェスのピースセットで

白ポーンを開括弧1、白ナイトを開括弧2
黒ポーンを閉括弧1、黒ナイトを閉括弧2
として考察すると

Stackを使って、
・開括弧なら積む
・閉括弧ならPeekした、Stackの一番上の開括弧と対応してるかを判定
という処理を行えばいいと分かります。

最後に、Stackが空なら、バランスの取れた括弧と判定してます。