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는 식을 의미한다)

 

상수: 0, 1, 2

변수: P, Q, R

NOT: -X

AND: (X*Y)

OR: (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형 문법은 다음과 같다.

 

<formula> ::= 0 | 1 | 2 | P | Q | R |

              -<formula> | (<formula>*<formula>) | (<formula>+<formula>)

        

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

 

출력

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

---

*,+ 는 if 문으로 구분 0이 있나 1이있나/ 2가있나 1이있나 

브루트포스로 해야하나? 일단 식을 최대한 줄이고 시작해야할듯

--은 replace

import sys

def operation(A,B,oper):
    if oper == "*":
        if 0 == A or 0 == B:
            return 0
        elif 1 == A or 1 ==B:
            return 1
        else:
            return 2
    else:
        if 2 == A or 2 == B:
            return 2
        elif 1 == A or 1 ==B:
            return 1
        else:
            return 0

input = []
while 1:
    S = sys.stdin.readline()
    if '.' in S:
        break
    input.append(S)

for S in input:
    S = S.replace("--","")
    #S = list(S)
    #print(S)
    

    cnt = 0

    for p in range(3):
        for q in range(3):
            for r in range(3):

                SS = S.replace("P",str(p))
                SS = SS.replace("Q",str(q))
                SS = SS.replace("R",str(r))

                SS = SS.replace("-0",str("2"))
                SS = SS.replace("-1",str("1"))
                SS = SS.replace("-2",str("0"))
                
                operstack = []
                numstack = []
                #print(SS)
                for s in SS:
                    print(numstack,operstack)
                    if s.isdigit():
                        numstack.append(int(s))
                    elif s == ")":
                        A = numstack.pop()
                        B = numstack.pop()
                        oper = operstack.pop()
                        numstack.append(operation(A,B,oper))
                        operstack.pop()
                    else:
                        operstack.append(s)
                #print(numstack)
                if 2 in numstack:
                    cnt += 1 
    print(cnt)

제대로 한거 같은데 테스트도 다 통과했는데 뭐가 잘못되건지 모르겠다.

친구의 도움을 받았는데 

문제가 되는 부분을 찾았다. -가 숫자랑 붙어만있는게 아니였다.

괄호 앞에 -가 있을 수 있다는 것을 알았다.

(((((-(--Q*-Q)*-P)*-1)+-Q)+--R)+-(---P*(Q*(---2*-2))))

https://icpc.iisf.or.jp/past-icpc/domestic2008/

ICPC2008 Problems(Domestic)

import sys
# *,+ 계산
def operation(A,B,oper):
    if oper == "*":
        if 0 == A or 0 == B:
            return 0
        elif 1 == A or 1 ==B:
            return 1
        else:
            return 2
    else:
        if 2 == A or 2 == B:
            return 2
        elif 1 == A or 1 ==B:
            return 1
        else:
            return 0
# 인풋 다 받아 놓고 했음
# 치면나오고하는게 불편해서
input = []
while 1:
    S = sys.stdin.readline()
    if '.' in S:
        break
    input.append(S)

# 하나씩 계산
for S in input:
    # -- 는 어차피 없어지니깐 사라지게
    S = S.replace("--","")
    #S = list(S)
    #print(S)

    cnt = 0
    # 전체 순회
    for p in range(3):
        for q in range(3):
            for r in range(3):
                # PQR을 숫자로 바꿈
                SS = S.replace("P",str(p))
                SS = SS.replace("Q",str(q))
                SS = SS.replace("R",str(r))

                # -하나 있는 연산을 걍 바꿔줌
                SS = SS.replace("-0",str("2"))
                SS = SS.replace("-1",str("1"))
                SS = SS.replace("-2",str("0"))
                
                operstack = []
                numstack = []
                #print(SS)
                # 이제 하나씩 계산
                for s in SS:
                    #print(numstack,operstack)
                    # 숫자는 숫자 스택에
                    if s.isdigit():
                        numstack.append(int(s))
                    # 닫는 괄호
                    elif s == ")":
                        # 닫는 괄호면 계산해야하기 때문에 숫자 2개 빼기
                        A = numstack.pop()
                        B = numstack.pop()
                        # 연산도 하나 빼기
                        oper = operstack.pop()
                        # 그걸로 계산
                        numstack.append(operation(A,B,oper))
                        # 여는 괄호 빼기
                        operstack.pop()
                        # 전에 -가 있다면 마이너스 계산하기
                        if operstack and operstack[-1] == "-":
                            operstack.pop()
                            num = numstack.pop()
                            numstack.append(2-num)
                    else:
                        # 다른 oper면 oper 스택에 넣기
                        operstack.append(s)
                #print(numstack)
                if 2 in numstack:
                    cnt += 1 
    print(cnt)