[BOJ] 1918.후위표기식 (Python)

 

1918번: 후위 표기식

 

이 문제는 중위 표기식으로 주어진 값을 후기 표기식으로 변경하여 출력하는 문제입니다.

즉, A+B*C-D/E라고 주어진 중위 표기식을 ABC*+DE/- 와 같은 후기 표기식으로 바꾸어 출력하면 됩니다.

 

결괏값은 문자로 출력되므로 후위 표기식을 문자열로 관리했습니다.

피연산자는 알파벳으로 주어지므로 isalpha()를 사용하면 쉽게 연산자와 구분이 가능합니다.

이 방식으로 피연산자를 찾으면 결괏값을 저장하는 문자열에 더해줍니다.

 

연산자의 경우 우선순위를 정하고 그에 따라 stack에 추가하는데, 이 과정에서 조건에 따른 pop이 필요합니다.

조건에 따라 pop을 처리하면서 결괏값을 만들어 갈 수 있습니다.

 

우선순위에 따라 처리하면, 

1. ( 는 무조건 stack에 추가한다.
2. *이나 / 은 stack에 추가하기 전에 stack에 존재하는 *이나 /을 pop 하여 결괏값에 저장한다.
3. +나 -는 stack에 추가하기 전에 stack에 존재하는 ( 직전까지의 값들을 모두 pop 하여 결괏값에 저장한다.
4. )는 stack에 존재하는 ( 직전까지의 값들을 모두 pop 하여 결괏값에 존재하고, stack에서 ( 제거를 위해 pop을 추가로 한 번 더 수행한다.

이와 같은 형태로 코드를 작성하면 다음과 같습니다.

text = input()
answer = ''
stack = [] # 연산자 관리용

for t in text :
    if t.isalpha() :
        answer += t
    else :
        if t == '(' :
            stack.append(t)
        elif t == '*' or t == '/' :
            while stack and (stack[-1] == '*' or stack[-1] == '/') :
                answer += stack.pop()
            stack.append(t)
        elif t == '+' or t == '-' :
            while stack and stack[-1] != '(' :
                answer += stack.pop()
            stack.append(t)
        elif t == ')' :
            while stack and stack[-1] != '(' :
                answer += stack.pop()
            stack.pop() # '('를 빼는 작업

while stack :
    answer += stack.pop()

print(answer)