jtw7913   9달 전

문제

당신은 대학에서컴퓨터 구조 수업을 듣고 있다. 과제를 검산하기 위해, 주어진 입력값에 대해 조합 논리 회로의 출력값을 계산하는 프로그램을 작성하려고 한다.

예시로, 그림 A.1과 같은 회로를 생각해보자. 이 회로는 네 개의 입력(A부터 D까지)을 가지며, 각 입력은 참(T) 또는 거짓(F)이다. 또한 네 개의 게이트가 있으며, 각 게이트는 AND, OR, NOT 중 하나이다. 각 게이트는 자신의 입력에 따라 참 또는 거짓 값을 출력한다. 가장 마지막 게이트(오른쪽의 OR 게이트)가 회로 전체의 최종 출력값을 만든다.

이 문제에서는 게이트를 다음과 같은 논리 연산자로 표현한다.

  • * : AND

  • + : OR

  • - : NOT

이 연산자들의 동작은 다음과 같다.

AND와 O

ABA B *A B +
TTTT
FTFT
TFFT
FFFF

NOT

AA -
TF
FT

AND와 OR는 두 개의 입력을 필요로 하고, NOT은 하나의 입력만을 필요로 한다.

회로는 후위 표기법(postfix notation)으로 표현한다. 즉, 연산자가 피연산자 뒤에 위치한다. 예를 들어 A B *는 A와 B의 AND 연산을 의미한다.

유효한 회로의 정의

회로는 다음 규칙에 따라 구성된다.

  1. 대문자 알파벳(A부터 Z)은 그 자체로 유효한 회로이다. (입력 하나만으로도 유효한 회로이며, 해당 입력값을 그대로 출력한다.)

  2. <C1>과 <C2>가 유효한 회로라면,
    <C1> <C2> * 는 두 회로의 출력을 AND한 유효한 회로이다.

  3. <C1>과 <C2>가 유효한 회로라면,
    <C1> <C2> + 는 두 회로의 출력을 OR한 유효한 회로이다.

  4. <C1>이 유효한 회로라면,
    <C1> - 는 해당 회로의 출력을 NOT한 유효한 회로이다.

  5. 위의 규칙 외의 표현은 유효한 회로가 아니다.

예를 들어, 그림 A.1의 회로는 다음과 같이 표현할 수 있다.

A B * C D + - +

입력값이 A=T, B=F, C=T, D=F일 때, 이 회로의 출력은 F가 된다.

입력

  • 첫 줄에 정수 $N$이 주어진다. ($1 \leq N \leq 26$)
    이는 입력 변수의 개수를 의미한다.

  • 다음 줄에는 $N$개의 문자(T 또는 F)가 공백으로 구분되어 주어진다.
    i번째 문자는 알파벳의 i번째 문자에 해당하는 입력값을 의미한다.
    (예: $N=4$이면, A, B, C, D 순서로 값이 주어진다.)

  • 마지막 줄에는 회로의 후위 표기식이 주어진다.

조건:

  • 회로는 위에서 정의한 문법을 항상 만족하는 유효한 회로이다.

  • 입력 변수로는 처음 $N$개의 알파벳만 사용된다.

  • 공백을 제외한 전체 문자 수는 최소 1개, 최대 250개이다.

  • 각 변수는 하나의 값만 주어지지만, 회로에서 여러 번 사용될 수 있다.

출력

주어진 입력값에 따라 회로를 계산한 결과를 출력하라.
출력은 T 또는 F 중 하나의 문자이다.

댓글을 작성하려면 로그인해야 합니다.