[백준] 1918: 후위 표기식

문제이해

일반적인 수식법인 중위 표기법대로 표현된 식이 입력되면, 후위 표기법으로 출력하면 되는 문제이다. 여기서 후위 표기법이란 계산의 우선순위 순서대로 연산자가 피 연산자 뒤에 위치하는 방법이다. 

ex. 

A+B+C  => AB+C+

A*B+C => AB*C+

A+B*C => ABC*+

A*(B+C) => ABC+*

계획

여러 경우가 있다고 생각할 수도 있는 문제인데 규칙은 하나밖에 없다. 바로 생각이 안나도 여러 예시들을 보다 보면 규칙성이 나온다. 주어지는 연산자마다 종류를 나누면 훨씬 쉽게 생각할 수 있는데 우선순위 가 높은 '*'와 '/'는 first, '+'와  '-' second라고 생각하자.

s : 

0	1	...	i	i+1	i+2	...	n
알파벳	연산자		알파벳	연산자	알파벳		연산자

이런 중위 표기법으로 된 식이 있다고 할때 s[i+1] 연산자 이전에 s[i+1] 연산자보다 우선순위가 낮은 연산자가 있다면 그다음 연산자를 확인하고, 만약 없다면, s[i+2] 알파벳 뒤에 우선순위가 높은 연산자 순서대로 연산자를 붙여주면 된다. 

즉 s[i+1] 이 first에 해당한다면, 우선순위가 낮은 것은 second, s[i+1]이 second에 해당한다면, 우선순위가 낮은 것은 없다. 다만 괄호가 있는 것이 우선순위가 가장 높으므로, 괄호사이의 연산자는 괄호 밖에 있는 연산자보다 우선순위가 더 높아야 한다.

 

계획수행

import sys

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

stack = []
ans = ''
first = ['*', '/']		#우선순위 높은 곱셈과 나눗셈
second = ['+', '-']		#우선순위 낮은 덧셈과 밸셈

for i in s:
    if i.isalpha():
        ans += i
        continue		#만약 알파벳이라면 정답 문자열에 추가

    if i == '(':
        stack.append(i)
    elif i == ')':
        while stack and stack[-1] != '(':
            ans += stack.pop()
        stack.pop()		#만약 ')'라면 '('까지 정답에 추가
    elif i in first:
        while stack and stack[-1] in first:
            ans += stack.pop()
        stack.append(i)	#만약 first라면 second만 정답에 추가
    elif i in second:
        while stack and stack[-1] != '(':
            ans += stack.pop()
        stack.append(i)	#만약 second라면 '('빼고 추가 할 수 있는 것 추가

while stack:
    ans += stack.pop()
print(ans)

 

 

느낀 점

 

규칙을 발견하는 것이 가장 중요한 것 같다.