[SWEA] 1232. 사칙연산 - Python

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV141J8KAIcCFAYD 

SW Expert Academy

< 📝 문제 >
사칙연산으로 구성되어 있는 식은 이진 트리로 표현할 수 있다. 아래는 식 “(9/(6-4))*3”을 이진 트리로 표현한 것이다.

임의의 정점에 연산자가 있으면 해당 연산자의 왼쪽 서브 트리의 결과와 오른쪽 서브 트리의 결과를 사용해서 해당 연산

 

자를 적용한다.

사칙연산 “+, -, *, /”와 양의 정수로만 구성된 임의의 이진트리가 주어질 때, 이를 계산한 결과를 출력하는 프로그램을 작

 

성하라.

단, 중간 과정에서의 연산은 실수 연산으로 하되, 최종 결과값이 정수로 떨어지지 않으면 정수부만 출력한다.

위의 예에서는 최종 결과값이 13.5이므로 13을 출력하면 된다.

 

< ❓ 생각 >
연산자 위주로 계산  : 연산자의 왼쪽 자식과 오른쪽 자식을 연산자로 계산이니 후위 순회

< 💻 코드 >

def post_odrer(v):
    if v:
        post_odrer(left[v])
        post_odrer(right[v])
        if tree[v] == '+':
            tree[v] = int(tree[left[v]]) + int(tree[right[v]])
        elif tree[v] == '-':
            tree[v] = int(tree[left[v]]) - int(tree[right[v]])
        elif tree[v] == '*':
            tree[v] = int(tree[left[v]]) * int(tree[right[v]])
        elif tree[v] == '/': # 정수로 계산
            tree[v] = int(tree[left[v]]) // int(tree[right[v]])
    return

for tc in range(1,11):
    # 정점의 총 수
    N = int(input())
    tree = [0]*(N+1)
    left = [0]*(N+1)
    right = [0]*(N+1)

    for _ in range(N):
        s = input().split()
        tree[int(s[0])] = s[1]
        # 정점이 연산자면(자식 노드가 있는 경우)
        if len(s) == 4:
            left[int(s[0])] = int(s[2])
            right[int(s[0])] = int(s[3])

    post_odrer(1)
    print(f'#{tc} {tree[1]}')

< ❗ 느낀 점 >

계산 식으로 볼때는 전위 순회 였는데 코드로 계산하려고 하니 연산자의 자식들이 다 필요해서 후위 순회로 생각을 바꾸었다.