2015年01月14日

C#で括弧の対応を保存したまま文字列を反転させる

   このエントリーをはてなブックマークに追加 Clip to Evernote
どう書く?orgに感謝を込めて」シリーズ その62

今回の問題は、括弧の対応を維持したまま文字列を反転させるというもの。
長めの問題文ですが、そのまま引用させてもらいます。

■問題 (出題者:nobsun さん)
与えられた文字列を前後反転する関数 ReverseString を書いてください。
ただし、ReverseString は単純に文字列を反転するのではなく、括弧の対応を保存するようにしてください。

以前のお題で作成した単純に与えられた文字列を単純に前後反転したもの返す reverseString では
  reverseString("文字列(もじれつ)の反転(はんてん)")
    → ")んてんは(転反の)つれじも(列字文"

のように括弧の対応は保存されませんが、ReverseString では
  ReverseString("文字列(もじれつ)の反転(はんてん)")
    → "(んてんは)転反の(つれじも)列字文"

のように括弧の対応が保存されます。
括弧文字は、'('と')'、'{'と'}'、'['と']'で、それぞれASCII文字と仮定してください。
  ReverseString("対応[の{とれている(さまざまな)括弧}の(例)]です。")
    → "。すで[(例)の{弧括(なまざまさ)るいてれと}の]応対"

入力文字列では対応の取れている括弧の内側には対応の取れない括弧文字はないと解釈してください。たとえば、
  ReverseString("これ(は(対応のとれていない)括弧がある例です。")
    → "。すで例るあが弧括(いないてれとの応対)は(れこ"

次のような場合は対応のとれている括弧はないという解釈になります。
  ReverseString("これ(も{対応の)とれていない}括弧の例です")
    → "。すで例の弧括}いないてれと)の応対{も(れこ"

日本語対応にする場合の文字のエンコーディングは実装側で都合のよいように仮定してください。
日本語対応であることは望ましいですが、必須ではありません。

対応する開き括弧と閉じ括弧を入れ替えてから、最後に一気に反転させるという方法で実装してみました。
括弧の入れ替えは StackとListを使って実現しています。
こうやれば、もっと簡単に実現できるよ! という目から鱗のアルゴリズムがあれば、どなたか教えてください。

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

namespace Doukaku.Org {
    class Program {
        static void Main(string[] args) {
            ReverseAndPrint("文字列(もじれつ)の反転(はんてん)");
            ReverseAndPrint("対応[の{とれている(さまざまな)括弧}の(例)]です。");
            ReverseAndPrint("これ(は(対応のとれていない)括弧がある例です。");
            ReverseAndPrint("これ(も{対応の)とれていない}括弧の例です");

            Console.ReadLine();
        }

        static void ReverseAndPrint(string s) {
            Console.WriteLine(ReverseString(s));
            Console.WriteLine();
        }

        static string ReverseString(string s) {
            char[] ParenthesesA = { '{', '(',  '[' };
            char[] ParenthesesB = { '}', ')',  ']' };
            Stack<CharAadIndex> stack = new Stack<CharAadIndex>();
            List<char> chars = new List<char>();
            int index = 0;
            foreach (var c in s) {
                if (ParenthesesA.Contains(c)) {
                    // 開き括弧
                    stack.Push(new CharAadIndex(c, index));
                    chars.Add(c);
                } else {
                    int i = Array.IndexOf(ParenthesesB, c);
                    if (i >= 0 && stack.Count > 0) {
                        CharAadIndex pair = stack.Peek();
                        if (pair.Char == ParenthesesA[i]) {
                            // 閉じ括弧:対応取れている
                            char temp = stack.Pop().Char;
                            chars[pair.Index] = c;
                            chars.Add(temp);
                        } else {
                            // 閉じ括弧:対応取れていない
                            stack.Push(new CharAadIndex(c, index));
                            chars.Add(c);
                        }
                    } else {
                        chars.Add(c);
                    }
                }
                index++;
            }
            StringBuilder sb = new StringBuilder();
            foreach (var c in chars.Reverse<char>()) {
                sb.Append(c);
            }
            return sb.ToString();
        }
    }

    class CharAadIndex {
        public CharAadIndex(char c, int index) {
            Char = c;
            Index = index;
        }
        public char Char { get; set; }
        public int Index { get; set; }
    }
}



 

この記事へのトラックバックURL

http://trackback.blogsys.jp/livedoor/gushwell/52400838