[백준] 후위 표기식

https://www.acmicpc.net/problem/1918

1918번: 후위 표기식

스택을 이용하는 문제입니다.

 

우선 문제를 간단하게 요약하면, 

컴퓨터에서는 후위 표기식을 사용합니다. 하지만 사람들은 식을 중위 표기식으로 나타냅니다. 이때, 중위 표기식을 후위 표기식으로 올바르게 고치는 코드를 작성해야 하는 문제입니다. 

a+b*c -> abc*+ (중위표기식 -> 후위표기식)

 

<Solution>

옛날에 스택을 이용한 계산기 만들기를 해본 기억을 되살려 문제를 해결하였습니다. 

 

우선 알고리즘은 다음과 같습니다. 

 

- 만약 괄호가 없다면

1. 피연산자는 항상 string에 들어간다. 

2. 연산자는 stack안에 담긴 연산자를 확인해서, 만약 본인이 우선순위가 밀리게 되면, stack안의 연산자를 본인이 안밀리는 것이 등장 할 때 까지 pop해서 string에 저장하고, 본인을 넣는다. 

3. 수식이 끝나면, 현재 남아 있는 스택의 연산자를 모두 pop 해서 string에 넣어준다. 

다음과 같은 과정을 거쳐갑니다.

 

-만약 괄호가 있다면

1. '(' 괄호면 무조건 stack에 넣는다.

2. ')' 괄호면 stack에서 '(' 가 나올 때 까지 pop해서 string에 넣어준다.

 

이 두가지 조건만 위에서 추가해주면 됩니다. 

 

실제 구현은 아래와 같습니다. 

list index와, '('문자 감지에만 조금 신경을 쓰면 될 것 같습니다.

import sys

s = sys.stdin.readline().rstrip()

stack = []
result = ''
for s_ in s:
    # print(f'stack = {stack}')
    # print(f'result = {result}')
    # print(f'current string = {s_}')
    # step 1
    if s_ == '(':
        stack.append(s_)
    elif s_ == ')':
        while(1):
            e = stack.pop()
            if e != '(':
                result += e
            else:
                break
    elif s_ == '+' or s_ == '-' or s_ == '*' or s_ == '/':
        # if stack is empty -> just push
        priority = 1 if (s_ == '+' or s_ == '-') else 2
        while(1):
            if len(stack) == 0:
                stack.append(s_)
                break
            if stack[-1] == '(':
                stack.append(s_)
                break
                
            s_priority = 1 if (stack[-1] == '+' or stack[-1] == '-') else 2
            
            if priority <= s_priority:
                result += stack.pop()
            else:
                stack.append(s_)
                break
    else:
        result += s_

# pop leftover
while(stack):
    result += stack.pop()

print(result)