括弧の対応のチェック

30分プログラム、その782。anarchy golf - Bracket Matchingにインスパイアされました。
問題の詳細はリンク先を参照してください。要するに括弧の対応がとれているかどうかのチェックです。正規表現じゃ無理なことで有名なアレです。
簡易パーサコンビネータを書いて...、みたいなことも考えたのですが、まあこれぐらいなら明示的にスタックを持ち回れば十分でしょう。

使い方

- isParen "";
val it = true : bool
- isParen "(<>)[]";
val it = true : bool
- isParen "(((";
val it = false : bool

ソースコード

structure Stack : sig
    type 'a t
    val push : 'a -> 'a t -> 'a t
    val pop  : 'a t ->  ('a  * 'a  t)
    val isEmpty : 'a t -> bool
    val empty  : 'a t
end = struct
   type 'a t = 'a list

   fun isEmpty [] = true
     | isEmpty _  = false

   fun push x xs = x :: xs

   fun pop (x::xs) = (x,xs)
     | pop [] = raise Empty

   val empty = []
end

val map = [(#"(", #")"),
	   (#"[", #"]"),
	   (#"{", #"}"),
	   (#"<", #">")]


fun isBegin c = List.exists (fn (x,_) =>  c = x) map

fun toBegin c =
    case List.find (fn (_,y) =>  y = c) map of
	NONE       =>  raise Empty
      | SOME (x,_) =>  x

fun paren [] st = Stack.isEmpty st
  | paren (c::cs) st =
    if isBegin c then
	paren cs (Stack.push c st)
    else
	let
	    val (x,st') = Stack.pop st
	in
	    if x = toBegin c then
		paren cs st'
	    else
		false
	end

fun isParen s = paren (String.explode s) Stack.empty

参考

• 過去の30分プログラム
• anarchy golf - Bracket Matching