[Python] 1918 - 후위 표기식

[Gold II] 후위 표기식 - 1918

[문제 링크](https://www.acmicpc.net/problem/1918)

🗝️알고리즘 분류

• 자료구조
• 스택

---

💻문제 정의

주어진 중위 표기식을 후위 표기식으로 바꾸어 출력하는 문제이다.

이 수식의 피연산자는 알파벳 대문자로 이루어지며, 수식에서는 단 한번만 등장한다. 또한 연산자가 맨 앞에 오거나, 곱하기가 생략되는 등의 수식은 주어지지 않는다.

 

💡접근 및 설계

중위 표기식을 후위 표기식으로 바꾸기 위해선 먼저 연산자의 우선 순위를 알아야 한다. 문제에선 (, ), *, /, +, - 6개의 연산자만을 활용한다.

 

이들 중에서 가장 우선순위가 높은 것은 괄호((, )) 그 다음 곱셈(*), 나눗셈(/), 마지막으로 더하기(+), 빼기(-) 이다.

 

후위 표기법에선, 우선순위가 높은 연산자가 먼저 나오도록 한다. 이를 구현하기 위해서 스택을 활용하였다.

 

+와 *가 있는 수식, A + B * C 라는 수식이 있다고 가정해보자. 이 식의 후위 표기법은 ABC*+가 될 것이다.

*가 +보다 우선순위가 높기 때문에 위와 같은 결과가 출력 되어야 한다.

 

그럼 이를 알고리즘으로 어떻게 구현할 수 있을까?

 

또한 괄호 내부의 연산자들은 우선순위와 상관없이 먼저 사용되어야 한다.

 

두 가지에 유의하여 문제를 풀어보자.

 

✏️알고리즘 풀이

다음과 같은 순서를 따라 알고리즘을 설계하였다.

1. 주어진 중위 표기식에서 '('를 만난다면, stack에 저장.
2. '*', '/' 를 만난다면 스택에 저장. 만약 스택 내부에 다른 연산자가 존재할 시, '*', '/'이면 결과 문자열에 추가하고 자신은 스택에 저장.
3. '+', '-'는 우선순위가 가장 낮기 때문에, 자신을 제외한 모든 연산자를 결과 문자열에 추가한다.
4. ')'를 만난다면 '(' 앞까지 모든 연산자를 결과 문자열에 추가, 이후 '('를 스택에서 pop
5. 남은 스택에 존재하는 문자열을 결과 문자열에 추가한다.

 

연산자는 다음과 같은 알고리즘에 의해 순서가 결정된다.

 

피연산자의 경우, 해당 문제에선 모두 알파벳이니 파이썬 내장 함수 isalpha()를 이용하여 알파벳인지 판단, 바로 결과 문자열에 추가하도록 하였다.

 

🗒️전체 코드

# 1918 후위표기식

import sys
input = sys.stdin.readline

exp = input()

stack = [] # 연산자들을 담을 스택
result = ''  # 결과 출력

for wrd in exp:
    if (wrd.isalpha()): # 알파벳은 그대로 저장
        result += wrd

    else: # 연산자들에 대해
        if (wrd == "("): # 여는 괄호를 만날시, 스택에 저장
            stack.append(wrd)

        elif (wrd == "*") or (wrd == "/"): # 곱하기 또는 나누기를 만날  경우, 
            while stack and (stack[-1] == "*" or stack[-1] == "/"): # 스택에 연산자가 들어 있고, 스택 제일 위에 곱 또는 나누기일 때 까지
                result += stack.pop() # 결과에 바로 붙여준다.

            stack.append(wrd) # 스택에 연산자 저장

        elif (wrd == "+") or (wrd == "-"): # 더하기 또는 나누기일 경우,
            while stack and (stack[-1] != "("): # 스택에 연산자가 들어 있고, 스택 제일 위에 여는 괄호가 아닐 때 까지
                result += stack.pop() # 결과에 저장
            
            stack.append(wrd) # 스택에 연산자 저장

        elif (wrd == ")"): # 닫는 괄호를 만날 경우
            while stack and (stack[-1] != "("): # 스택에 연산자가 들어 있고, 스택 제일 위에 여는 괄호가 아닐 때 까지
                result += stack.pop() # 결과에 저장

            stack.pop() # 여는 괄호 팝

while stack: # 스택 내부가 빌 때 까지
    result += stack.pop() # 결과에 저장

print(result) # 결과 출력

---

💭오늘의 회고

중위 표기식을 후위 표기식으로 변환하는 방법을 알고 있다면 꽤나 간단히 풀 수 있는 문제였을 것이다.

자료구조를 배우면서 가장 쉽게 접하는 알고리즘이라 생각한다.

 

예전에 파이썬을 배운지 얼마 되지 않았을 때, 괄호를 생각하지 않은 후위 표기식 변환 문제를 접해본 경험이 있다.

괄호 유무에 따라 문제 난이도가 크게 차이가 난다는 것이, 알고리즘 설계가 이렇게 복잡하는 생각이 들었다.

 

또한 자바를 공부하면서 이를 자바코드로도 구현 해보았기에, 쉽게 문제를 해결할 수 있었다.