DouKaku?beta

challenge 文字列の反転(括弧の対応を保存) 

与えられた文字列を前後反転する関数 reverseString2 を書いてください。
ただし、reverseString2 は単純に文字列を反転するのではなく、括弧の対応
を保存するようにしてください。

以前のお題で作成した単純に与えられた文字列を単純に前後反転したもの返す
reverseString では

  reverseString("文字列(もじれつ)の反転(はんてん)") 
    → ")んてんは(転反の)つれじも(列字文"

のように括弧の対応は保存されませんが、reverseString2 では

  reverseString2("文字列(もじれつ)の反転(はんてん)")
    → "(んてんは)転反の(つれじも)列字文"

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

  reverseString2("対応[の{とれている(さまざまな)括弧}の(例)]です。")
    → "。すで[(例)の{弧括(なまざまさ)るいてれと}の]応対"

入力文字列では対応の取れている括弧の内側には対応の取れない括弧文字はな
いと解釈してください。たとえば、

  reverseString2("これ(は(対応のとれていない)括弧がある例です。")
    → "。すで例るあが弧括(いないてれとの応対)は(れこ"

次のような場合は対応のとれている括弧はないという解釈になります。

  reverseString2("これ(も{対応の)とれていない}括弧の例です")
    → "。すで例の弧括}いないてれと)の応対{も(れこ"

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

---
このお題はnobsunさんに投稿いただきました。ご協力ありがとうございます。
post comment

Posted feedbacks - Nested

Flatten Hidden 
エレガントでない気もしますが一応例示された通りの変換ができます。

＞reverseString2("これ(も{対応の)とれていない}括弧の例です")
＞　→ "。すで例の弧括}いないてれと)の応対{も(れこ"
句点が抜けてますね。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
# coding: shift_jis

def reverseString2(s, coding = 'shift_jis'):
    s = list(unicode(s, coding))
    length = len(s)
    stack = []
    pairs = []
    dic = {')': '(', '}': '{', ']': '['}
    
    # 対応する括弧をリストアップ
    for i, c in enumerate(s):
        if stack and dic.get(c, '') == stack[-1][1]:
            pairs.append((stack[-1][0], i))
            stack.pop()
        elif c in '({[':
            stack.append((i, c))
    
    s = s[::-1]
    
    for start, end in pairs:
        start, end = length - start - 1, length - end - 1
        s[start], s[end] = s[end], s[start]
    
    return ''.join(s).encode(coding)

def test(s, answer):
    s = reverseString2(s)
    print (s == answer) and 'ok!' or s

if __name__ == '__main__':
    test("文字列(もじれつ)の反転(はんてん)", "(んてんは)転反の(つれじも)列字文")
    test("対応[の{とれている(さまざまな)括弧}の(例)]です。", "。すで[(例)の{弧括(なまざまさ)るいてれと}の]応対")
    test("これ(は(対応のとれていない)括弧がある例です。", "。すで例るあが弧括(いないてれとの応対)は(れこ")
    test("これ(も{対応の)とれていない}括弧の例です。",  "。すで例の弧括}いないてれと)の応対{も(れこ")

投稿する場所間違えるわ、張りなおした際に間違えたコード張るわ、
括弧の交換を後でやる意味が無いわと散々でした。自分慌てすぎ。
以降はもっと落ち着いて投稿したいと思います･･･
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
def reverseString2(s, coding = 'shift_jis'):
    s = list(unicode(s, coding))
    stack = []
    dic = {')': '(', '}': '{', ']': '['}
    
    for i, c in enumerate(s):
        if stack and dic.get(c, '') == stack[-1][1]:
            s[stack[-1][0]], s[i] = s[i], s[stack[-1][0]]
            stack.pop()
        elif c in '(){}[]':
            stack.append((i, c))
    
    return ''.join(s[::-1]).encode(coding)
 似た問題があなごるにありましたね。 

see: anarchy golf - Mirroring Characters 

1
2
3
4
5
6
7
function reverseString2($){
  var p = '([{（［｛)]}）］｝', n = p.length / 2, s = [], i = -1, x, t;
  for($ = $.toString().split(''); $[++i];) if(~(x = p.indexOf($[i])))
    if(x < n) s.push({ x: x + n, i: i });
    else if((t = s.pop()) && t.x == x) $[t.i] = p.charAt(x), $[i] = p.charAt(x - n);
  return $.reverse().join('');
}

(cons x knil)のあたりが汚いので、もうちょっと何とかなるとは思うのですが…
実行結果：
(んてんは)転反の(つれじも)列字文
。すで[(例)の{弧括(なまざまさ)るいてれと}の]応対
。すで例るあが弧括(いないてれとの応対)は(れこ
すで例の弧括}いないてれと)の応対{も(れこ

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
(use text.tree)

(define parens '((#\) . #\() (#\} . #\{) (#\] . #\[)))
(define openp (append (map car parens) (map cdr parens)))

(define (spl x l)
  (cond ((null? l) (values #f #f))
        ((eqv? x (car l)) (values () (cdr l)))
        ((memv (car l) openp) (values #f #f))
        (else (receive (head tail) (spl x (cdr l))
                    (values (if head (cons (car l) head) #f) tail)))))

(define (reverse-string2 l)
  (tree->string
    (fold (lambda (x knil)
            (cond ((assv x parens) =>
                   (lambda (pair)
                     (cond ((spl (cdr pair) knil)
                            (lambda (x _) x)
                            => (lambda (body rest)
                                 (cons `(,(cdr pair) ,@body ,(car pair)) rest)))
                           (else (cons x knil)))))
                  (else (cons x knil))))
          () (string->list l))))

(for-each (compose print reverse-string2)
          '("文字列(もじれつ)の反転(はんてん)"
            "対応[の{とれている(さまざまな)括弧}の(例)]です。"
            "これ(は(対応のとれていない)括弧がある例です。"
            "これ(も{対応の)とれていない}括弧の例です"))
Squeak Smalltalk で。 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| parentheses reverseString2 offset |
parentheses := '({[)}]'.
offset := parentheses size // 2.
reverseString2 := [:str |
    | marks |
    marks := OrderedCollection new.
    str copy doWithIndex: [:chr :idx |
        | type |
        type := parentheses indexOf: chr.
        type > offset ifFalse: [type > 0 ifTrue: [marks add: idx; add: type]] ifTrue: [
            (marks notEmpty and: [marks removeLast + offset = type])
                ifTrue: [str swap: idx with: marks removeLast]
                ifFalse: [marks removeLast]]].
    str reversed].

reverseString2 value: '文字列(もじれつ)の反転(はんてん)'.
   "=> '(んてんは)転反の(つれじも)列字文' "
reverseString2 value: '対応[の{とれている(さまざまな)括弧}の(例)]です。'.
   "=> '。すで[(例)の{弧括(なまざまさ)るいてれと}の]応対' "
reverseString2 value: 'これ(は(対応のとれていない)括弧がある例です。'.
   "=> '。すで例るあが弧括(いないてれとの応対)は(れこ' "
reverseString2 value: 'これ(も{対応の)とれていない}括弧の例です。'.
   "=> '。すで例の弧括}いないてれと)の応対{も(れこ' "

全般に無難なコードとおもいますが
stk.popのところはちょっと感じ悪いかも。
つーかelsifでいろいろやりすぎ感がいやなのかなあ。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
K = [['(', ')'], ['[', ']'], ['{', '}']]
OPN, CLS = K.transpose

def reverseString2(org)
  str = org.split(//)
  stk = []

  str.each_with_index{|c, i|
    if ki = OPN.index(c)
      stk.push([i, ki])
    elsif ki = CLS.index(c) and (j, kj = stk.pop) and ki == kj
      str[j] = CLS[ki]
      str[i] = OPN[kj]
    end
  }

  str.reverse.join
end

if __FILE__ == $0
  def test(a,b)
    p a, reverseString2(a), b, reverseString2(a) == b
  end

  test("文字列(もじれつ)の反転(はんてん)", "(んてんは)転反の(つれじも)列字文")
  test("対応[の{とれている(さまざまな)括弧}の(例)]です。", "。すで[(例)の{弧括(なまざまさ)るいてれと}の]応対")
  test("これ(は(対応のとれていない)括弧がある例です。", "。すで例るあが弧括(いないてれとの応対)は(れこ")
  test("これ(も{対応の)とれていない}括弧の例です。",  "。すで例の弧括}いないてれと)の応対{も(れこ")
end

もっときれいに書けそうな気がします。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
reverseString2 :: String -> String
reverseString2 str = let (e, s) = foldl f ([],[]) str in foldl (\s1 (s2,c) -> s2++c:s1) s e
    where f (e, s) c
              | c `elem` "({[" = (([], c):e, s)
              | c `elem` ")}]" = case e of
                                   (es1, p1):(es2, p2):rest
                                        | c == opposite p1 -> ((p1:es1++c:es2, p2):rest, s)
                                        | otherwise -> ((c:es1++p1:es2, p2):rest, s)
                                   [(es, p)]
                                       | c == opposite p -> ([], p:es++c:s)
                                       | otherwise -> ([], c:es++p:s)
                                   [] -> (e, c:s)
              | otherwise = case e of
                              (es, p):rest -> ((c:es, p):rest, s)
                              otherwise    -> (e, c:s)
          opposite '(' = ')'
          opposite ')' = '('
          opposite '{' = '}'
          opposite '}' = '{'
          opposite '[' = ']'
          opposite ']' = '['
          opposite c = c

Haskell練習中。
あまり美しくないなあ。
ghciで日本語はどう使うのかなあ。

実行例
*Main> reverseString2 "mojiretsu(MOJIRETSU) no hanten(HANTEN)."
".(NETNAH)netnah on (USTERIJOM)usterijom"
*Main> reverseString2 "taiou[no{toreteiru(samazamana)kakko}no(rei)]desu."
".used[(ier)on{okkak(anamazamas)urieterot}on]uoiat"
*Main> reverseString2 "kore(ha(taiounotoreteinai)kakkonoarureidesu."
".usedieruraonokkak(ianieterotonuoiat)ah(erok"
*Main> reverseString2 "kore(mo{taiouno)toreteinai}kakkonoreidesu."
".usedieronokkak}ianieterot)onuoiat{om(erok"

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
parens = [('(',')'), ('[',']'), ('{','}')]

isOpener c = elem c $ map fst parens
isCloser c = elem c $ map snd parens

closer p = case lookup p parens of
             Just q -> q
             Nothing -> error "huh?"

revs [] rs zs = ([],rs++zs)
revs (x:xs) rs zs
  | isOpener x = case revs xs [] [x] of
                   (xs',rs') -> revs xs' (rs'++rs) zs
  | isCloser x = case zs of
                   [z] | x == closer z -> (xs, [z]++rs++[x])
                   _                   -> (xs, [x]++rs++zs)
  | otherwise  = revs xs (x:rs) zs

reverseString2 s = snd $ revs s [] []

ghcで日本語を正しく扱うには，いまのところ入出力の際に UTF8 <-> 内部コード
という変換をする必要があります．この変換を行うモジュールは以前自前で書いた
ことがあるのですが，今は Hackage DB に登録されています．

http://hackage.haskell.org/cgi-bin/hackage-scripts/package/utf8-string-0.2

インストール手順は以下のとおりです．

$ wget http://hackage.haskell.org/packages/archive/utf8-string/0.2/utf8-string-0.2.tar.gz
$ tar xf utf8-string-0.2.tar.gz
$ cd utf8-string-0.2
$ runhaskell Setup.lhs configure
$ runhaskell Setup.lhs build
$ sudo runhaskell Setup.lhs install

これで Codec.Binary.UTF8.String と System.IO.UTF8 モジュールが使えるように
なります．

$ ghc-pkg -l | grep utf8 

とやるとこのパッケージがインストールされたかどうか確認できます．
ghci には直接 UTF8 の文字列リテラルを入力できない(orz)ので，ソースコードに
定数として仕込んでおく必要があります．ソースコードのエンコーディングを
UTF8 にして

sample0 = "文字列(もじれつ)の反転(はんてん)"
sample1 = "対応[の{とれている(さまざまな)括弧}の(例)]です。"
sample2 = "これ(は(対応のとれてない)括弧がある例です。"
sample3 = "これ(も{対応の)とれていない}括弧の例です。"

というのをソースコード(3511.hs)にいれておきますそうしておいて，
- ghci を起動．
- System.IO.UTF8 を追加．
- 出力用 wrapper を追加．
- wrapper をつかって結果を表示

$ ghci -v0 3511.hs
*Main> :m + System.IO.UTF8
*Main System.IO.UTF8> let wrapper = (System.IO.UTF8.putStrLn .)
*Main System.IO.UTF8> wrapper reverseString2 sample0
(んてんは)転反の(つれじも)列字文
*Main System.IO.UTF8> wrapper reverseString2 sample1
。すで[(例)の{弧括(なまざまさ)るいてれと}の]応対
*Main System.IO.UTF8> wrapper reverseString2 sample2
。すで例るあが弧括(いなてれとの応対)は(れこ
*Main System.IO.UTF8> wrapper reverseString2 sample3
。すで例の弧括}いないてれと)の応対{も(れこ

ああ面倒 ^^;


	

	
	
	
    

      
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
using System;
using System.Text;
using System.Collections.Generic;

class Program {
    static string reverseString2(string s) {
        Stack<string> stack = new Stack<string>();
        StringBuilder sb = new StringBuilder(s.Length);
        string paren = "()[]{}";
        
        foreach (char ch in s) {
            int index = paren.IndexOf(ch);
            if (index < 0) {                // other
                sb.Insert(0, ch);
            } else if (index % 2 == 0) {    // ([{
                stack.Push(sb.ToString());
                stack.Push(ch.ToString());
                sb.Remove(0, sb.Length);
            } else {                        // )]}
                if (stack.Count == 0) {
                  sb.Insert(0, ch);
                } else if (stack.Peek() == paren.Substring(index - 1, 1)) {
                    sb.Insert(0, stack.Pop()).Append(ch);
                    if (stack.Count > 0) sb.Append(stack.Pop());
                } else {
                    sb.Insert(0, ch);
                    while (stack.Count > 0) sb.Append(stack.Pop());
                }
            }
        }
        while (stack.Count > 0) sb.Append(stack.Pop());
        
        return sb.ToString();
    }
    static void Main(string[] args) {
        Console.WriteLine(reverseString2("文字列(もじれつ)の反転(はんてん)"));
        Console.WriteLine(reverseString2("対応[の{とれている(さまざまな)括弧}の(例)]です。"));
        Console.WriteLine(reverseString2("これ(は(対応のとれていない)括弧がある例です。"));
        Console.WriteLine(reverseString2("これ(も{対応の)とれていない}括弧の例です"));
    }
}




    

	

  
  








  


  

  

  
    







  
  






  
    

      
      







  
  

	

	  
おっと、これだと対応が取れていないときの動作が不正ですね。

	

	
	
	

  
  








  


    

  


  

  

  
    







  
  

	

	  
「鶏を割くに牛刀をもってす」の感はありますが，
パーザを構成してしまうという手もあります．


	

	
	
	
    

      
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
import qualified System.IO.UTF8 as U
import Text.ParserCombinators.ReadP

data Kakko = Maru | Nami | Kaku

data Inline = Plain String
            | Paren Kakko [Inline]

pPlain  = do { s <- many1 $ satisfy (flip notElem "(){}[]"); return (Plain s)}

pMaru = do { char '('; is <- many pInline; char ')'; return (Paren Maru is) }
pNami = do { char '{'; is <- many pInline; char '}'; return (Paren Nami is) }
pKaku = do { char '['; is <- many pInline; char ']'; return (Paren Kaku is) }

pParen = pMaru +++ pNami +++ pKaku
pInline = pPlain +++ pParen

pInlines =   many1 (pPlain +++ pParen)
         +++ do { c  <- satisfy (const True)
                ; is <- pInlines
                ; return (Plain [c] : is)
                }

revInline (Plain s) = Plain (reverse s)
revInline (Paren k is) = Paren k (foldl ((. revInline) . flip (:)) [] is)

instance Show Inline where
  show (Plain s) = s
  show (Paren k is) = case k of
                         Maru -> '(':(concatMap show is)++")"
                         Nami -> '{':(concatMap show is)++"}"
                         Kaku -> '[':(concatMap show is)++"]"

reverseString2 = concatMap show 
               . reverse 
               . map revInline 
               . fst 
               . head 
               . filter (null . snd) 
               . readP_to_S pInlines

sample0 = "文字列(もじれつ)の反転(はんてん)"
sample1 = "対応[の{とれている(さまざまな)括弧}の(例)]です。"
sample2 = "これ(は(対応のとれてない)括弧がある例です。"
sample3 = "これ(も{対応の)とれていない}括弧の例です。"

{-
*Main> U.putStrLn $ reverseString2 $ sample0
(んてんは)転反の(つれじも)列字文
*Main> U.putStrLn $ reverseString2 $ sample1
。すで[(例)の{弧括(なまざまさ)るいてれと}の]応対
*Main> U.putStrLn $ reverseString2 $ sample2
。すで例るあが弧括(いなてれとの応対)は(れこ
*Main> U.putStrLn $ reverseString2 $ sample3
。すで例の弧括}いないてれと)の応対{も(れこ
-}




    

	

  
  








  


  

  
    







  
  

	

	  

	

	
	
	
    

      
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
def reverseString2(str:String) = {
  val bras = "()[]{}"
  ((List[(int,int)](), new StringBuilder(str)) /: str.toList.zipWithIndex){
    case ((stk, sb), (c, i)) => bras.indexOf(c) match {
      case -1 => (stk, sb)
      case bi  => bi&1 match {
        case 0 => ((i,bi^1)::stk,sb)
        case _ =>
          for((j,bj) <- List(stk.head) if bj == bi) {
            sb.update(j, bras(bi))
            sb.update(i, bras(bj^1))
          }
          (stk.tail, sb)
      }
    }
  }._2.reverse.mkString
}




    

	

  
  








  


  

  
    







  
  

	

	  
とりあえずそのままひっくり返して、対応してた括弧は後で入れ換え。

	

	
	
	
    

      
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
(defun reverse-string2 (string)
  (loop with str = (reverse string) and stack
    for c across str and i from 0
    do (case c
         ((#\) #\] #\}) (push (cons c i) stack))
         ((#\( #\[ #\{)
          (if (eql (caar stack) (elt ")]}" (position c "([{")))
              (progn
                (rotatef (elt str i) (elt str (cdar stack)))
                (setf stack (cdr stack)))
            (setf stack ()))))
    finally (return str)))

;;; test
(defun test (s1 s2)
  (format t "~:[NG~;OK~]~%" (string= (reverse-string2 s1) s2)))
(mapc #'test
      '("文字列(もじれつ)の反転(はんてん)"
        "対応[の{とれている(さまざまな)括弧}の(例)]です。"
        "これ(は(対応のとれていない)括弧がある例です。"
        "これ(も{対応の)とれていない}括弧の例です。")
      '("(んてんは)転反の(つれじも)列字文"
        "。すで[(例)の{弧括(なまざまさ)るいてれと}の]応対"
        "。すで例るあが弧括(いないてれとの応対)は(れこ"
        "。すで例の弧括}いないてれと)の応対{も(れこ"))




    

	

  
  








  


  

  

  
    







  
  

	

	  
自動で括弧の対応にマッチしてくれるライブラリはあると結構便利かもしれないと感じました。(括弧の対応はもちろんカスタマイズ可能) 。探せば既にあるような気もするけど

	

	
	
	
    

      
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
def reverse_string2 str
  match_pairs = {
    '(' => ')',
    '{' => '}',
    '[' => ']',
  }

  match_pairs.each do |key,val|
    str = str.gsub(/(#{Regexp.escape(key)})([^#{Regexp.escape(key)}]*?)(#{Regexp.escape(val)})/) {|str| "#{$3}#{$2}#{$1}" };
  end

  str.split(//).reverse.join
end

if $PROGRAM_NAME == __FILE__
  $KCODE = 'u'
  require 'rubygems'
  require 'spec'

  describe "reverse_string2" do
    it "は文字列を反転させること" do
      reverse_string2("文字列の反転").should == "転反の列字文"
    end

    it "は()の対応を保存すること" do
      reverse_string2("文字列(もじれつ)の反転(はんてん)").should == "(んてんは)転反の(つれじも)列字文"
    end
    it "は{}の対応を保存すること" do
      reverse_string2("文字列{もじれつ}の反転{はんてん}").should == 
      "{んてんは}転反の{つれじも}列字文"
    end
    it "は[]の対応を保存すること" do
      reverse_string2("文字列[もじれつ]の反転[はんてん]").should == "[んてんは]転反の[つれじも]列字文"
    end
    it "対応の取れている括弧にのみ対応すること" do
      reverse_string2("これ(は(対応のとれていない)括弧がある例です。").should == "。すで例るあが弧括(いないてれとの応対)は(れこ"
    end
  end
end




    

	

  
  








  
    

      
      







  
  

	

	  ネストした括弧に対応してない模様
	

	
	
	

  
  








  


    

  


  

  

  
    







  
  

	

	  
初投稿です。Cで書いてみました。日本語は未対応です。

	

	
	
	
    

      
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
char *reverse_string2( char *str, int length ){
   char *now = str;
   int len = length;
   int i=0;
   char **sp, *p;
   sp = (char **) malloc( length * sizeof( char * ));

   if( !sp || !now ){
      return NULL;
   }

   for(; *str && len--; now++ ){
      if( *now == '(' ) sp[i++] = now;
      else if( *now == '{' ) sp[i++] = now;
      else if( *now == '[' ) sp[i++] = now;
      else if( ( *now == ')' && i && *sp[i-1] == '(' && i-- )
            || ( *now == '}' && i && *sp[i-1] == '{' && i-- )
            || ( *now == ']' && i && *sp[i-1] == '[' && i-- ))
      {
         (p = strchr("()",*sp[i])) || (p = strchr("{}",*sp[i])) || (p = strchr("[]",*sp[i]));
         *sp[i] = *(p+1);
         (p = strchr(")(",*now)) || (p = strchr("}{",*now)) || (p = strchr("][",*now));
         *now = *(p+1);
      }
   }
   free( sp );
   return reverse_string( str, length );
}




    

	

  
  








  
    

      
      







  
  

	

	  
for ループの中を改良しました。

	

	
	
	
    

      
1
2
3
4
5
6
   for(; *str && len--; now++ ){
      if( *now == '(' || *now== '{' || *now == '[' ) sp[i++] = now;
      else if( ( *now == ')' && i && *sp[i-1] == '(' && (*sp[--i] = ')') && (*now = '(') )
            || ( *now == '}' && i && *sp[i-1] == '{' && (*sp[--i] = '}') && (*now = '{') )
            || ( *now == ']' && i && *sp[i-1] == '[' && (*sp[--i] = ']') && (*now = '[') ) ){}
   }




    

	

  
  








  


    

  


  

  

  
    







  
  

	

	  
一本の再帰呼び出しのパスで処理を終わらせられるように考えてみました。行きで閉じ括弧、帰りでひらき括弧の処理をしています。

	

	
	
	
    

      
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
type Paren = Char
type ParenStack = [Paren]

reverseString2 :: String -> String
reverseString2 str = fst $ reverseStrParen (str, [])

reverseStrParen :: (String, ParenStack) -> (String, ParenStack)
reverseStrParen ([],  _)        = ([], [])
reverseStrParen (x:[], stkOpen) = ([flipParenIfMatch x stkOpen], pushCloseParen x [])
reverseStrParen (x:xs, stkOpen) = 
            (reverseRest ++ [flipParen2Way x