이진문자열(0과 1만이 등장하는 문자열) 에 대한 문제임.
0과 1의 갯수가 같은 이진문자열의 집합 S를 생각하자

예를 들어 "" ∈ S, "0101" ∈ S, "1100" ∈ S 고, "001" ∉ S, "11100" ∉ S 임.


S는 다음과 문맥 자유 문법 E에 대응이 됨.


E ::= ε | 0 E 1 | 1 E 0 | E E


Backus-Naur 표기법이 익숙하지 않은 사람을 위해서 설명을 하자면

```

어떤 문자열 x가 E에 매칭된다는 것은:

- x가 빈 문자열 ε 이거나

- x가 '0 y 1' 꼴의 문자열이고 y가 E에 매칭되거나

- x가 '1 y 0' 꼴의 문자열이고 y가 E에 매칭되거나

- x가 'y z' 꼴의 문자열이고 y, z가 각각 E에 매칭 된다

```

S와 E가 대응이 된다는건 문자열 x가 S에 속하는지 여부와, x가 문법 규칙 E에 매칭 되는지 여부가 동치라는 뜻임.


그러면 주어진 이진문자열에서 0과 1의 갯수가 같은지 판별하고, 같은 경우 위 문법에 대응되는 파스 트리를 생성하는 프로그램을 만들 수 있음.

아래는 하스켈 구현임. 이진문자열은 그냥 Bool의 리스트로 만들었어.


import Data.List import Data.Maybe fromString :: String -> [Bool] fromString = map $ x -> case x of '0' -> False '1' -> True _ -> undefined data Exp = EEps | EF_T Exp | ET_F Exp | ECat Exp Exp deriving Show decode :: Exp -> [Bool] decode EEps = [] decode (EF_T e) = [False] ++ decode e ++ [True] decode (ET_F e) = [True] ++ decode e ++ [False] decode (ECat e1 e2) = decode e1 ++ decode e2 encode :: [Bool] -> Maybe Exp encode [] = Just EEps encode [x] = Nothing encode xs@(x : xs') | last xs' == not x = (if x then ET_F else EF_T) <$> encode (init xs') | otherwise = listToMaybe . catMaybes . init . tail $ zipWith (ls rs -> ECat <$> encode ls <*> encode rs) (inits xs) (tails xs)

(사실 이것 보다는 더 효율적으로 구현할 수 있음. 어차피 문제는 이게 아니니 대충 보세요)


>> encode (fromString "0011010110") Just (ECat (EF_T (EF_T EEps)) (ECat (EF_T EEps) (ECat (EF_T EEps) (ET_F EEps))))


========================== 여기부터 진짜 문제 ==========================


사실 0과 1의 갯수가 같은 문자열에 매칭되는 더 간단한 문법이 있음


F ::= ε | 0 F 1 F | 1 F 0 F

아까 문법은 branch가 4개인데 이건 3개라서 조금 더 간단함.


이 문법도 마찬가지로 프로그램으로 구현할 수 있음. 아래는 하스켈로 구현한 decode 함수임 (파스트리의 타입 Exp를 다시 이진문자열 [Bool] 로 만드는 함수)


data Exp = EEmp | EInd Bool Exp Exp deriving Show decode :: Exp -> [Bool] decode EEmp = [] decode (EInd x e1 e2) = [x] ++ decode e1 ++ [not x] ++ decode e2


문법 F에서의 encode 함수를 구현하는게 문제야.

주어진 이진문자열이 0과 1의 갯수가 같은지 판별하고, 같은 경우 문법 F의 파스 트리를 구하는 프로그램을 만들면 됨.


프로그래밍 언어는 자유임


* E, F 모두 ambiguous한 문법임. 그러니까 같은 문자열에 대응되는 파스 트리가 여러개일 수 있음. 아무거나 하나 구하면 됨.

* 0과 1의 갯수가 같은 모든 문자열이 F에 매칭된다는게 별로 자명하지 않음. 일단 왜 되는지 알아야 구현이 수월할 것임.

* 코드 예시를 하스켈만 제공해서 미안하지만, 어차피 글만 읽어도 문제는 이해할 수 있음.