[BOJ] 1918 : 후위 표기식 [스택](Python)

문제 링크

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

1918번: 후위 표기식

소스 코드

def main():
    formula = list(input())
    stack = [] # 연산자, 괄호가 담길 스택
    answer = ''

    for tmp in formula:
        if tmp.isalpha(): # 문자는 바로 정답 문자열에 추가
            answer += tmp
        elif tmp == '(': # 여는 괄호는 스택에 추가
            stack.append(tmp)
        elif tmp == '*' or tmp == '/': # 곱셈/나눗셈은 묶여 있음
            while stack and (stack[-1] == '*' or stack[-1] == '/'):
                answer += stack.pop()
            stack.append(tmp)
        elif tmp == '+' or tmp == '-': # 덧셈/뺄셈은 괄호만 아니면 덜어내기
            while stack and stack[-1] != '(':
                answer += stack.pop()
            stack.append(tmp)
        else: # 닫는 괄호는 여는 괄호 전까지 다 정답으로 추가
            while stack and stack[-1] != '(':
                answer += stack.pop()
            stack.pop() # 여는 괄호 제거

    while stack: # 남아 있는 문자 정답으로 추가하기
        answer += stack.pop()
    print(answer)

if __name__ == '__main__':
    main()

 

해설

• 스택

후위 표기식을 중위 표기식으로 바꾸는 것은 쉬울 것 같은데 반대는 방법이 거의 떠오르지 않았습니다 ㅜㅜ

당연한 것이지만 가장 까다로웠던 부분은 연산자 간의 우선순위를 어떻게 반영할 것인가였습니다.

그 부분을 집중해서 코드를 보시면 이해에 도움이 될 것 같아요

(혹시나 과정이 잘 이해되지 않는 경우 for문 내부에 print문을 찍어서 stack, answer 두 변수가 어떻게 변하고 있는지 tracking 해보세요!)

---

시간 복잡도

길이가 N인 문자열이라고 가정한다면, for문을 통해 N번만큼의 탐색을 수행하게 됩니다.

따라서 O(N)입니다.

 

각 탐색이 수행되는 동안에는 모든 연산이 상수 시간이 걸립니다.

예를 들어 리스트에 추가하는 append(이건 정확히는 amortized O(1)이긴 합니다), 리스트 원소를 꺼내는 pop 등 모두 O(1) 만큼의 시간이 소요됩니다.

 

따라서 위 스택 알고리즘은 O(N)의 시간 복잡도를 가진다고 볼 수 있습니다.

---

stack, answer 구분해서 탐색하기

이 둘을 구분해서 stack에는 연산자를 몰아 놓고, answer는 그 연산자들에 따라 문자와 연산자가 조합될 수 있도록 한 풀이입니다.

경우의 수를 하나씩 살펴보도록 하죠.

 

1) 문자인 경우

바로 answer에 추가해줍니다. 어차피 후위 표기식에서는 문자 이후에 연산자가 나타나기 때문입니다.

if tmp.isalpha():
    answer += tmp

 

2) 여는 괄호인 경우

stack에 추가합니다. 이후 다른 연산자들에 제한을 걸어주는 조건문에 활용이 됩니다.

elif tmp == '(': # 여는 괄호는 스택에 추가
    stack.append(tmp)

 

3) 연산자의 경우

이건 조금 까다롭습니다.

우리는 '곱셈/나눗셈'이 '덧셈/뺄셈'보다 먼저 계산되어야 한다는 것을 알고 있습니다.

이는 후위표기식에서는 문자 바로 뒤에 먼저 계산하는 연산자가 와야 한다는 뜻입니다.

(ex. ABC*+ → A + B*C)

 

따라서 곱셈/나눗셈의 경우 스택에 쌓아놓은 연산자가 * 또는 / 인 경우에만 스택의 원소를 꺼내어 정답에 추가합니다.

덧셈/뺄셈의 경우 여는 괄호만 아니면 싹 다 정답에 추가합니다.

곱셈/나눗셈은 덧셈/뺄셈보다 우선순위가 높기 때문에 곱셈/나눗셈이 추가로 나타나는 경우가 아니면 일단 keep해두는 것입니다.

'A + B*C - D/E' vs 'A + B*C * D/E' 두 예시를 한 번 비교해보세요.

elif tmp == '*' or tmp == '/': # 곱셈/나눗셈은 묶여 있음
    while stack and (stack[-1] == '*' or stack[-1] == '/'):
        answer += stack.pop()
    stack.append(tmp)
elif tmp == '+' or tmp == '-': # 덧셈/뺄셈은 괄호만 아니면 덜어내기
    while stack and stack[-1] != '(':
        answer += stack.pop()
    stack.append(tmp)

 

4) 닫는 괄호의 경우

여는 괄호가 나올 때까지 스택에 들어있는 모든 원소를 정답에 추가하면 됩니다.

괄호 자체는 정답에 포함하지 않기 때문에 마지막에 pop 해줌으로써 스택에 남은 괄호를 제거해줍니다.

else: # 닫는 괄호는 여는 괄호 전까지 다 정답으로 추가
    while stack and stack[-1] != '(':
        answer += stack.pop()
    stack.pop() # 여는 괄호 제거

 

5) 마지막으로 남은 원소

스택 문제는 보통 이렇게 마지막까지 for문을 돌려도 스택 내에 원소가 남아 있는 경우가 많습니다.

남아있는 원소가 있다면 정답에 순서대로 추가할 수 있도록 합니다.

while stack: # 남아 있는 문자 정답으로 추가하기
    answer += stack.pop()
print(answer)