백준 4970 (C++) 디지털 회로 개론

최초 업로드: 2025-10-09 06:33:21

최근 수정 시간: 2025-10-09 06:33:21

게시자: rlatjwls3333

카테고리: 백준

# [Gold III] 디지털 회로 개론

[문제 링크](https://www.acmicpc.net/problem/4970)

## 문제 설명

3차 논리는 논리값이 "true", "false", "unknown"을 가지는 논리 체계이다. 이 체계에서는 "false"는 0의 값을 가지고, "unknown"은 1, "true"는 2의 값을 갖는다.

"-"을 단항 연산자, "*"와 "+"는 이항 연산자라고 하자. 이 연산자는 각각 NOT, AND, OR을 의미한다. 3차 논리에서 3개 연산자는 다음과 같이 정의되어 있다.

P, Q, R을 3차 논리값을 갖는 변수라고 하자. 이때, 식이 주어졌을 때, 식의 값을 2로 만드는 (P,Q,R)쌍의 개수를 구하는 프로그램을 작성하시오. 식은 다음 중 하나의 형태를 갖는다. (X와 Y는 식을 의미한다)

AND와 OR은 항상 괄호로 둘러싸여 있다.

예를 들어, (P*Q)가 주어졌을 때, 식의 값을 2로 만드는 (P,Q,R)쌍은 (2,2,0), (2,2,1), (2,2,2) 3가지이다.

## 입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 식을 나타낸다. 식은 0, 1, 2, P, Q, R, -, *, +, (, )로만 이루어져 있다.

식의 BNF형 문법은 다음과 같다.

입력은 80글자를 넘지 않는다. 마지막 줄에는 '.'이 주어진다.

## 출력

각 테스트 케이스에 대해서, 입력으로 주어진 식의 값을 2로 만드는 (P,Q,R) 쌍의 개수를 출력한다.

## 풀이
스택으로 구현했습니다. 후위표기식과 비슷하나 조금 더 어렵습니다.

``` c++
#include<bits/stdc++.h>
using namespace std;

int NOT(int x) {
    return (2-x);
}

int AND(int x, int y) {
    if(x==2 && y==2) return 2;
    return !(x==0 || y==0);
}

int OR(int x, int y) {
    return max(x, y);
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    while(true) {
        string s; cin >> s;
        if(s[0]=='.') break;

int cnt=0;
 for(int p=0;p<=2;p++) {
 for(int q=0;q<=2;q++) {
 for(int r=0;r<=2;r++) {
 stack<int> stk;
 stack<char> opt;
 for(int ch : s) {
 if(ch=='P') stk.push(p);
 else if(ch=='Q') stk.push(q);
 else if(ch=='R') stk.push(r);
 else if('0'<=ch && ch<='2') stk.push(ch-'0');
 else {
 opt.push(ch);
 if(opt.top()==')') {
 opt.pop();
 while(opt.top()!='(') {
 char op = opt.top(); opt.pop();
 if(op=='-') stk.top() = NOT(stk.top());
 else {
 int top1 = stk.top(); stk.pop();
 int top2 = stk.top(); stk.pop();
 if(!opt.empty() && opt.top()=='-') {
 opt.pop();
 opt.push(op);
 stk.push(NOT(top2));
 stk.push(top1);
 }
 else if(op=='+') stk.push(OR(top1, top2));
 else stk.push(AND(top1, top2));
 }
 }
 opt.pop();
 }
 }
 }
 while(!opt.empty()) {
 char op = opt.top(); opt.pop();
 if(op=='-') stk.top() = NOT(stk.top());
 else {
 int top1 = stk.top(); stk.pop();
 int top2 = stk.top(); stk.pop();
 if(!opt.empty() && opt.top()=='-') {
 opt.pop();
 opt.push(op);
 stk.push(NOT(top2));
 stk.push(top1);
 }
 if(op=='+') stk.push(OR(top1, top2));
 else stk.push(AND(top1, top2));
 }
 }
 if(stk.top()==2) cnt++;
 }
 }
 }
 cout << cnt << '\n';
 }
}
```