[자료구조] 스택(Stack)의 응용 중위표기식 -> 후위표기식 (4)

중위 표기식을 후위 표기식으로 변환

e.g ) 2 - 10 / 5 * 6 + 4

1. 중위 표기식을 처음부터 순서대로 읽음

2. 피연산자의 경우에는 바로 출력 가능

3. 연산자의 경우 일단 스택에 stack에 push하여 우선 순위 확인 필요 (LIFO 구조이기 때문)

4. Tip. 스택의 우선순위 보다 더 높은 연산자가 있으면 pop하여 출력한 후에 push (우선순위가 높은 연사자는 모두 pop 해야함)

5. 수식이 종료되면 스택에 있는 모든 연산자를 pop하여 출력

 

#Python 코드

# 괄호가 없는 중위 표기식을 후위 표기식으로 변환
# 입력 : 2 - 10 / 5 * 6 + 4
# 기대 출력 : [2, 10, 5, '/', 6, '*', '-', 4, '+']

OPERATORS = '+-*/'
PRECEDENCE = [1,1,2,2] #연산자 + - * / 의 우선순위로 숫자로 지정

postfix = [] # 후위 표기식을 저장할 stack
operator_stack = [] # operator stack에는 char들이 저장된다

def is_operator(ch):
    for i in range(len(OPERATORS)):
        if (OPERATORS[i] == ch):
            return i
    return -1
    
def precedence(op): #우선 순위를 리턴해준다
    return PRECEDENCE[is_operator(op)]

def process_op(op):
    if len(operator_stack) == 0:
        operator_stack.append(op)
    else:
        top_op = operator_stack[-1]
        if (precedence(op) > precedence(top_op)):
            operator_stack.append(op)
        else:
            while(len(operator_stack) != 0 and precedence(op) <= precedence(top_op)):
                operator_stack.pop() # 원래 pop을 하면 값을 받아야하지만 이전에 peek를 하여 따로 값을 받지는 않음
                postfix.append(top_op)
                if (len(operator_stack) != 0):
                    top_op = operator_stack[-1] #stack이 비지 않았으면 top_op 값을 바꿔준다
            operator_stack.append(op)
    return 0                

def convert(infix):
    token = infix.split(' ')
    index = 0
    while (index < len(token)):
        if (token[index][0] >= '0' and token[index][0] <= '9'): # 가장 앞자리가 0에서 9 일 경우 정수
            postfix.append(int(token[index]))
        elif (token[index] in OPERATORS):
            process_op(token[index])
        else:
            return 'Syntax Error'
    
        index += 1
       
    final_check = len(operator_stack) 
    while(final_check > 0):
        postfix.append(operator_stack.pop())
        final_check -= 1
    return postfix



print(convert(input()))