아틴 집합 계산기

Nick은 최근 아틴 집합(artinian set), 줄여서 아틴(artinal)이라 부르는 특별한 종류의 집합을 배웠습니다. 이 집합의 장점은 저마다 유한한 표현을 가진다는 점이어서 컴퓨터로 처리할 수 있습니다. 형식적인 정의는 다소 복잡합니다.

• 높이가 $\le 0$인 아틴은 오직 공집합 ∅ 하나뿐입니다.
• 양의 정수 $N$에 대해, 높이가 $\le N$인 아틴은 그 원소가 모두 높이 $\le N-1$인 아틴인 유한 집합들과 정확히 일치합니다.
• 어떤 양의 정수 $N$에 대해 $A$가 높이 $\le N$인 아틴이면, $A$를 아틴이라고 합니다.
• 모든 아틴의 모임을 $U$로 씁니다.

높이가 $\le N$인 아틴은 높이가 $\le N+1$인 아틴이기도 하므로, 임의의 아틴 $A$에 대해 높이 $h(A)$를 $A$가 높이 $\le N$인 아틴이 되게 하는 가장 작은 $N$으로 정의합니다. 높이가 $N$인 아틴을 $N$-아틴이라고 부릅니다.

여기에 두 가지 개념이 더 필요합니다. $U$ 위의 표준 순서(canonical order, <로 표기)와 아틴의 표준형(canonical form)입니다.

• 높이가 $\le N$인 아틴 $A$의 표준형은, 각 $A_i$가 높이 $\le N-1$인 아틴이고 $A_1 < A_2 < \cdots < A_s$를 만족하도록 원소를 나열한 $A = \{A_1, A_2, \ldots, A_s\}$입니다.
• 표준형으로 쓴 두 아틴 $A = \{A_1, \ldots, A_s\}$와 $B = \{B_1, \ldots, B_t\}$가 모두 높이 $\le N$일 때, $A < B$인 것은 다음을 만족하는 정수 $k$ ($1 \le k \le \min(s+1, t)$)가 존재하는 것과 동치입니다: 모든 $1 \le j < k$에 대해 $A_j = B_j$이고, $k = s+1$이거나 $A_k < B_k$이다. 직관적으로는, 정렬된 원소 목록을 왼쪽부터 비교하여 처음으로 다른 원소가 순서를 결정하고, 한쪽이 다른 쪽의 진부분 목록이면 그쪽이 앞섭니다.

아틴의 표준 표현(canonical representation)은 문자 {, }, ,로 이루어진 문자열입니다. repr(∅) = {}이고, $A = \{A_1, \ldots, A_s\}$가 표준형이면 repr($A$) = { + repr($A_1$) + , + $\cdots$ + , + repr($A_s$) + }입니다.

표준 표현은 길어지기 쉬우므로 다음 약칭을 도입합니다. 각 정수 $N \ge 0$에 대해 유한 서수(finite ordinal) $\mathbf{N}$을 귀납적으로 정의합니다: $\mathbf{0} := ∅$이고 $\mathbf{N{+}1} := \{\mathbf{N}\} \cup \mathbf{N}$이며, 따라서 $\mathbf{N} = \{\mathbf{0}, \mathbf{1}, \ldots, \mathbf{N{-}1}\}$입니다. 축약 표준 표현(reduced canonical representation)은 표준 표현에서, 자신보다 큰 서수 $\mathbf{M}$ ($M > N$)의 출현 안에 포함되지 않은 모든 서수 $\mathbf{N}$의 출현을 십진수 $N$으로 바꾼 것입니다.

아틴에 대한 연산은 다음과 같으며, 우선순위가 높은 것부터 낮은 것 순으로 나열합니다.

• 단항 교집합 ∩: 공집합이 아닌 아틴 $A = \{A_1, \ldots, A_s\}$에 대해 ∩$A := A_1 \cap A_2 \cap \cdots \cap A_s$.
• 단항 합집합 ∪: 임의의 아틴 $A = \{A_1, \ldots, A_s\}$에 대해 ∪$A := A_1 \cup A_2 \cup \cdots \cup A_s$이고, ∪∅ := ∅.
• 이항 교집합 ∩: $A \cap B := \{x : x \in A \text{ 이고 } x \in B\}$.
• 이항 합집합 ∪: $A \cup B := \{x : x \in A \text{ 또는 } x \in B\}$.
• 이항 차집합 −: $A - B := \{x \in A : x \notin B\}$.
• 이항 대칭차 △: $A \mathbin{\triangle} B := (A - B) \cup (B - A)$.

아틴 사이의 관계는 다음과 같이 정의합니다.

• 상등 =과 부등 ≠.
• 포함 ⊂과 ⊃: $A ⊂ B \Leftrightarrow B ⊃ A \Leftrightarrow (x \in A \Rightarrow x \in B)$. 즉 ⊂은 "부분집합 또는 상등"을 뜻합니다.
• 원소 관계 ∈과 ∋: $B \in A$ (동치로 $A \ni B$)는 $B$가 $A$의 원소임을 뜻합니다.
• 위에서 설명한 표준 순서 관계 <, ≤, ≥, >. 여기서 $A \le B \Leftrightarrow (A < B \text{ 또는 } A = B)$, $A > B \Leftrightarrow B < A$, $A \ge B \Leftrightarrow B \le A$입니다.

여러분은 아틴으로 계산을 수행하는 작은 프로그램을 실행해야 합니다. 프로그램은 한 줄에 하나씩 놓인 연산자들의 나열입니다. 연산자는 다섯 종류입니다.

• 대입 ⟨ident⟩:=⟨expr⟩ — 변수 ⟨ident⟩를 ⟨expr⟩의 값으로 설정합니다.
• 평가 !⟨expr⟩ — ⟨expr⟩를 평가하여 그 축약 표준 표현을 한 줄에 출력합니다.
• 검사 ?⟨expr⟩⟨relation⟩⟨expr⟩ — 조건을 평가하여 TRUE 또는 FALSE를 한 줄에 출력합니다.
• 주석 #⟨임의의 문자열⟩ — 그 줄 전체를 출력으로 복사합니다.
• 빈 연산자 — 공백 문자만으로 이루어진 줄로, 아무 일도 하지 않습니다.

문법에는 다음 정의를 사용합니다.

• ⟨ident⟩ ::= ⟨alpha⟩{⟨alpha⟩}
• ⟨alpha⟩ ::= ⟨letter⟩ | ⟨digit⟩ | _
• ⟨digit⟩ ::= 0 | 1 | … | 9
• ⟨letter⟩ ::= A | … | Z | a | … | z
• ⟨expr⟩ ::= { [ ⟨expr⟩ { ,⟨expr⟩ } ] } | ⟨ident⟩ | ⟨expr⟩⟨binop⟩⟨expr⟩ | ⟨unop⟩⟨expr⟩ | (⟨expr⟩)
• ⟨binop⟩ ::= + | * | - | ^
• ⟨unop⟩ ::= + | *
• ⟨relation⟩ ::= < | > | = | <= | >= | <> | -> | <- | << | >>

이항 연산자 +, *, -, ^는 각각 ∪, ∩, −, △을 나타내고, 단항 연산자 +, *는 각각 ∪, ∩을 나타냅니다. 관계 <, >, =, <=, >=, <>, ->, <-, <<, >>는 각각 <, >, =, ≤, ≥, ≠, ∈, ∋, ⊂, ⊃을 나타냅니다. 괄호 (와 )는 통상적으로 우선순위를 바꿉니다. 하나의 ⟨ident⟩를 이루는 ⟨alpha⟩ 문자들만 예외로 하고, 임의의 두 토큰은 임의 개수의 공백 문자(스페이스와 탭)로 구분할 수 있습니다.

프로그램 실행 전에, 이름이 음이 아닌 정수 $N$의 (앞자리 0 없는) 십진 표기인 모든 변수는 유한 서수 $\mathbf{N}$으로 미리 설정됩니다. 그 밖의 모든 변수는 ∅으로 시작합니다. 식별자는 대소문자를 구별합니다.

입력은 최대 100줄이며, 각 줄에는 연산자가 하나씩 들어 있습니다. 어떤 줄도 254자를 넘지 않습니다.

위 설명대로 ?, !, # 연산자마다 한 줄씩 출력하십시오. 입력은 실행 중 오류가 발생하지 않음이 보장됩니다(예: 단항 ∩은 결코 공집합에 적용되지 않습니다).