조건문

시간 제한10초메모리 제한128 MB

요약

중첩 if로 이루어진 작은 언어의 프로그램을 해석해, 각 checkpoint에 도달할 수 있는 변수 값 조건을 구하고 반드시 참이거나 거짓이어야 하는 변수만 출력하거나 unreachable을 출력한다.

난이도: 어려움10점 중 8점
유형: 시뮬레이션, 구현, 재귀, 백트래킹
정답자: 아직 제출이 없습니다

문제

아래 세 가지 명령(statement)만으로 이루어진 아주 단순한 프로그래밍 언어가 있다.

if <boolean expression> then <statement list> fi
if <boolean expression> then <statement list> else <statement list> fi
checkpoint

모든 키워드는 소문자로 쓴다. <statement list>는 하나 이상의 명령을 나열한 것이고, 프로그램 전체가 하나의 <statement list>이다.

<boolean expression>은 다음 요소로 이루어진다.

변수: 알파벳 대문자 한 글자
연산자: 단항 ~(NOT), 이항 &(AND), 이항 |(OR)
우선순위: ~가 가장 높고, 그다음이 &, 마지막이 |이다.
괄호로 묶을 수 있다.
식 안에는 공백이 없다.

식의 문법은 다음과 같다.

<BE> -> ~<BE> | <BE>&<BE> | <BE>|<BE> | (<BE>) | [A-Z]

문법 오류가 없는 프로그램이 주어질 때, 각 checkpoint에 도달하려면 각 변수가 반드시 어떤 값을 가져야 하는지 구하는 프로그램을 작성하시오.

입력

문법 오류가 없는 프로그램 하나가 입력으로 주어진다.

키워드는 항상 소문자이고, 모든 불리언 변수는 알파벳 대문자 한 글자이다.
키워드는 공백(스페이스, 탭, 줄바꿈)으로 구분된다.
식(expression) 안에는 공백이 없다.
각 <statement list>는 최소 한 개의 statement를 포함한다.
프로그램에는 변수가 최대 20개 등장한다.
statement의 개수는 5000개를 넘지 않는다.
모든 boolean expression의 길이는 128글자를 넘지 않는다.

출력

각 checkpoint가 프로그램에 나타나는 순서대로 한 줄씩 출력한다. 각 줄은 다음과 같다.

먼저 >를 출력한다.
그 checkpoint에 도달할 수 있으면, 도달하기 위해 값이 반드시 정해지는 변수를 이어서 출력한다. 반드시 참(true)이어야 하는 변수는 대문자로, 반드시 거짓(false)이어야 하는 변수는 소문자로 쓰고, 알파벳 순서로 나열한다. 참·거짓 어느 값이든 가능한 변수는 출력하지 않는다.
도달할 수 없으면 > 뒤에 unreachable을 출력한다.

예제6

예제 1

입력

if A then
    checkpoint
    if ~A then
        checkpoint
    fi
else
    checkpoint
fi
if (A&B)|(~A&~B) then
    checkpoint 
fi
if A|~A then checkpoint fi
if B then
    if ~A then checkpoint fi
fi

예상 출력

>A
>unreachable
>a
>
>
>aB

예제 2
입력
```
if A then checkpoint fi
```
예상 출력
```
>A
```

예제 3

입력

if A then checkpoint else checkpoint fi

예상 출력

>A
>a

예제 4
입력
```
if A&B then checkpoint fi
```
예상 출력
```
>AB
```
예제 5
입력
```
if ~C then checkpoint fi
```
예상 출력
```
>c
```

예제 6

입력

if A|B then checkpoint fi
if A&~A then checkpoint fi

예상 출력

>
>unreachable