SWEA 1232번 [S/W 문제해결 기본] 9일차 - 사칙연산

이진 트리를 후위 순회(postorder traversal)하는 방식으로 문제를 해결하였습니다.

1. Node 클래스를 정의하여 이진 트리의 노드를 표현

2. postorder 함수로 주어진 노드를 루트로 하는 부분 트리를 후위 순회하여 식을 생성

3. calculate 함수는 후위 표기식으로 표현된 연산을 계산
   연산자를 만나면 스택에서 두 개의 피연산자를 꺼내 해당 연산을 수행하고, 그 결과를 다시 스택에 넣는다. 피연산자를 만나면 그냥 스택에 넣습니다.

from collections import defaultdict
 
class Node:
    def __init__(self,data):
        self.data=data
        self.left=None
        self.right=None
 
def postorder(node):
    global answer
    if node.left:
        postorder(tree[node.left])
    if node.right:
        postorder(tree[node.right])
    answer.append(node.data)
 
def calculate(l):
    stack=[]
    for i in range(len(l)):
        if l[i]=='+':
            b=stack.pop()
            a=stack.pop()
            stack.append(int(a)+int(b))
 
        elif l[i]=='-':
            b = stack.pop()
            a = stack.pop()
            stack.append(int(a)-int(b))
 
        elif l[i]=='*':
            b = stack.pop()
            a = stack.pop()
            stack.append(int(a)*int(b))
 
        elif l[i]=='/':
            b = stack.pop()
            a = stack.pop()
            stack.append(int(a)//int(b))
 
        else:
            stack.append(int(l[i]))
 
    return stack[-1]
 
for _ in range(10):
    n=int(input())
    tree=defaultdict(Node)
    answer=[]
    for i in range(n):
        arr=list(input().split())
        tree[int(arr[0])]=Node(arr[1])
        if len(arr)>2:
            tree[int(arr[0])].left=int(arr[2])
            if len(arr)>3:
                tree[int(arr[0])].right=int(arr[3])
 
    postorder(tree[1])
    print(f'#{_+1} {calculate(answer)}')