[SW 1233][tree] 사칙 연산 유효성 검사

사칙 연산 유효성 검사

SW Expert Academy

파이썬
- 유효성 검사만 한 코드

#정수일 경우: 자식노드가 있으면 유효X 대신 아래로 확인
#단말노드일 경우: 연산자가 아니라 정수가 오면 유효X

operator= ['+','-','*','/']

for test_case in range(1,11):
    n=int(input())
    answer=1
    for i in range(n):
        read= list(input().split())
      
        #숫자가 아닌 연산자인경우
        #자식노드가 있어야함
        if read[1] in operator:
            if len(read)<3:
                answer=0
        #정수가 온 경우 이면
        else:
            #자식노드가 있으면 안됨
            if len(read)>2:
                answer=0

    print("#{} {}".format(test_case, answer))

 

 

파이썬 
- 값 계산까지 확인하는 코드

• 트리가 유효하지 않는 경우
  • 현재 노드의 key가 연산자인데 자식 노드가 존재하지 않는 경우
  • 현재 노드의 key가 정수인데 자식 노드가 존재하는 경우
  • 부 트리(sub tree)가 유효하지 않는 경우

left_val / right_val 이 n/0 꼴이 되면 zero division error가 발생하여 계산할 수 없지만,

문제에서는 이같은 경우를 invalid에 포함시키지 않기로 했기때문에 'invalid'를 return하는 것이 아니라,

따로 'zero division error'를 return한다. (0/1 결과를 출력할 때 zero division error인 경우도 1로 출력한다.)

operator=['+','-','*','/']

#operate함수 : 유효성 검사
def operate(v):
    #현재 노드값이 연산자이면
    if tree[v] in operator:
        #자식노드가 무조건 있어야함, 없으면 유효x
        if not left_child[v] or not right_child[v]:
          return 'invalid'

        #재귀
        #왼쪽 서브트리 유효성 검사
        left_val=operate(left_child[v])
        #오른쪽 서브트리 유효성검사
        right_val= operate(right_child[v])
      
        #서브 트리가 유효하지 않으면 현재 트리도 유효하지 않음
        if left_val=='invalid' or right_val=='invalid':
            return 'invalid'
        #0으로 나누는문제는 고려x -> 결과는 1
        if left_val=='zero division error' or right_val=='zero division error':
            return 'zero division error'
    
        #연산 작업 후 return
        result=0
        if tree[v]== '+':
            result=left_val+right_val
        elif tree[v]=='-':
            result= left_val -right_val
        elif tree[v]=='*':
            result= left_val *right_val
        else: #나누기
            if right_val==0:
                return 'zero division error'
            #0이 아니면
            result= left_val/ right_val
        return result

    #현재 노드값이 정수이면
    else:
        #마지막 노드여야 하므로 자식이 없어야함 , 있으면 유효x
        if left_child[v] or right_child[v]:
            return 'invalid'
        #없으면
        return tree[v] #현재 값(정수) 리턴
    
  

for tc in range(1,11):
    N= int(input())
    #노드 정보
    #[node, key, left child, right child]
    #마지막 노드는 숫자만 나올수도
    arr=[input().split() for _ in range(N)]
  
    #트리, 왼쪽자식노드, 오른쪽자식 노드 각각
    tree= [0]*(N+1) 
    left_child= [0]*(N+1) 
    right_child=[0]*(N+1) 
  
    for a in arr:
        node= int(a[0]) #첫번째값: node

        #현재노드 key가 연산자가 아닐때
        if a[1] not in operator:
            #정수가 온것: int로 변경
            a[1]=int(a[1])

        #트리에 연산자 or 수 삽입 
        tree[node]=a[1] 

        if len(a)>=3:
            left_child[node]= int(a[2])
            #4가지 다 가진 경우  
            if (len(a)==4): 
                right_child[node]= int(a[3])

    result=1
    if operate(1)=='invalid': 
        result=0
    print("#{} {}".format(tc,result))

 

출처: https://cys4585.tistory.com/10

 

 

자바 코드
- 유효성만 확인하는 코드

package day7_bfs;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

//연산자일 경우: 자식노드 없으면 유효X

//정수일 경우: 자식노드가 있으면 유효X 대신 아래로 확인
//단말노드일 경우: 연산자가 아니라 정수가 오면 유효X

public class SW1233_ParkSomin {
    public static void main(String[] args) throws IOException {
        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb= new StringBuilder();

        int T= 10;

        for(int test_case=1; test_case<=T; test_case++){
            int N=Integer.parseInt(br.readLine());

            int answer=1;
            for(int i=1; i<=N; i++){
                StringTokenizer st= new StringTokenizer(br.readLine());
                st.nextToken(); //첫번째 정점번호는 PASS

                char node= st.nextToken().charAt(0);

                if (st.hasMoreTokens()) { //단말노느가 아닐때 (값이 더있으면)
                    //연산자가 와야함, 숫자가오면 유효X
                    if(Character.isDigit(node)){
                        answer=0;
                    }
                }
                //단말노드 이면 : 숫자여야함
                else{
                    if (!Character.isDigit(node)) { //숫자가 아니면
                        answer = 0;
                    }
                }
            }
            sb.append("#"+test_case+" "+ answer+ "\n");
        }
        System.out.println(sb.toString());
    }

}