회로 계산

여러분은 대학에서 컴퓨터 구조론 수업을 듣고 있다. 조합 논리 회로의 입력이 주어졌을 때 회로의 출력값을 계산해서 답을 확인하는 프로그램을 작성하려고 한다.

그림 A.1: 조합 논리 회로의 예. 설명은 본문을 참고한다.

그림 A.1의 회로를 예로 들어 보자. 이 회로에는 네 개의 입력(왼쪽의 A부터 D까지)이 있고, 각 입력은 참 또는 거짓이다. 게이트는 네 개 있고 각 게이트는 AND, OR, NOT 세 종류 중 하나다. 각 게이트는 입력에 따라 참 또는 거짓을 출력한다. 마지막 게이트(오른쪽의 OR)가 회로 전체의 출력을 낸다. 이 세 가지 게이트는 각각 대응하는 논리 연산자로 텍스트에 쓸 수 있다: AND는 *, OR은 +, NOT은 -다. 앞으로는 게이트 대신 연산자로 회로를 설명한다.

연산자는 다음과 같이 동작한다. 각 입력에 참(T) 또는 거짓(F)을 배정하면 연산자는 다음 표에 나온 진릿값을 낸다.

AND와 OR은 입력을 두 개 받고 NOT은 입력을 하나만 받는다. 또한 연산자가 들어간 식(예: A B *)은 후위 표기법으로 쓴다. 연산자가 입력 뒤에 온다(그림 A.1에서 회로도의 각 게이트가 입력 뒤에 오는 것과 같다).

후위 표기법으로 올바른 회로를 나타낼 때는 다음 문법을 따른다.

• 대문자(A부터 Z)는 올바른 회로다. 즉, 입력 하나만 있고 게이트가 없어도 올바른 회로이며, 자기 입력값을 그대로 출력한다.
• <C1>과 <C2>가 올바른 회로라면 <C1> <C2> *는 두 부분 회로 출력의 AND를 내는 올바른 회로다.
• <C1>과 <C2>가 올바른 회로라면 <C1> <C2> +는 두 부분 회로 출력의 OR을 내는 올바른 회로다.
• <C1>이 올바른 회로라면 <C1> -는 <C1>의 출력에 NOT을 적용한 값을 내는 올바른 회로다.

이 밖의 표기는 올바른 회로가 아니다.

따라서 그림 A.1의 회로를 후위 표기법으로 나타내는 한 가지 방법은 다음 문자열이다.

A B * C D + - +

각 입력(이 예에서는 A, B, C, D)에 진릿값(T 또는 F)이 주어지면 그 값이 회로의 게이트를 따라 전파되고, 마지막 게이트가 내는 진릿값이 회로의 출력이다. 예를 들어 위 회로에 A=T, B=F, C=T, D=F를 주면 회로의 출력은 F다.

변수에 대한 배정과 회로 설명이 주어졌을 때, 여러분의 프로그램은 회로의 출력을 출력해야 한다.

입력의 첫 줄에는 정수 n이 하나 주어지며, 1 ≤ n ≤ 26이다. 다음 줄에는 공백으로 구분된 n개의 문자가 주어진다. 각 문자는 T 또는 F이고, i번째 문자는 알파벳 i번째 글자로 표시된 입력의 진릿값이다.

입력의 마지막 줄에는 위에서 설명한 문법을 따르는 회로 설명이 주어진다. 각 회로는 올바르고, 알파벳의 처음 n개 글자만 입력 레이블로 쓰며, 공백을 제외한 총 문자가 1개 이상 250개 이하다.

각 변수에는 진릿값이 하나만 주어지지만, 변수는 회로 설명에 여러 번 나타나 둘 이상의 게이트에 입력으로 들어갈 수 있다.

주어진 입력값으로 회로를 계산했을 때의 출력인 문자 하나(T 또는 F)를 출력한다.