불 후위 표기식

면접 대비

시간 제한1초메모리 제한256 MB

요약

스택으로 AND, OR, XOR, NOT을 포함한 후위 불리언 식을 계산해 참이면 1, 거짓이면 0을 출력합니다.

난이도: 쉬움10점 중 3점
유형: 스택
정답자: 아직 제출이 없습니다

문제

논리식은 보통 중위 표기법으로 쓴다. 연산자(∧, ∨)를 피연산자 사이에 놓는 방식이다. 예를 들어 ((a∧b)∨¬c)는 a와 b가 모두 참이거나 c가 거짓일 때 참이다. Mary Lucy Margret은 연산자를 피연산자 뒤에 놓는 후위 표기법을 쓴다. 위 식을 후위 표기법으로 쓰면 (a b ∧ c ¬ ∨)이 된다.

Mary Lucy Margret이 후위 표기법으로 쓴 논리식을 읽어 값을 계산하는 프로그램을 작성하라. 주어지는 식은 모두 올바른 식이다.

입력

첫 줄에 식의 개수 $T$ 가 주어진다. 다음 $T$ 개의 줄에는 후위 표기법으로 쓴 논리식이 한 줄에 하나씩 주어진다. 각 줄은 토큰의 개수 $n$ 으로 시작하고, 그 뒤에 $n$ 개의 토큰이 공백 하나로 구분되어 이어진다.

토큰 1과 0은 각각 참과 거짓을 뜻하고, 대문자는 연산자를 뜻한다. 나올 수 있는 토큰은 다음과 같다.

1: 참
0: 거짓
A: 논리곱
R: 논리합
X: 배타적 논리합
N: 부정

출력

$T$ 개의 줄을 출력한다. 각 줄에는 해당 식의 값이 참이면 1을, 거짓이면 0을 출력한다.

예제5

예제 1

입력

3
3 0 1 R
3 0 0 R
7 1 0 A 1 R N N

예상 출력

1
0
1

예제 2

입력

4
9 0 0 A 0 N 0 N A R
9 0 1 A 0 N 1 N A R
9 1 0 A 1 N 0 N A R
9 1 1 A 1 N 1 N A R

예상 출력

예제 3
입력
```
2
1 1
1 0
```
예상 출력
```
1
0
```

예제 4

입력

예상 출력

예제 5

입력

4
2 1 N
2 0 N
5 1 N N N N
4 0 N N N

예상 출력