[문제 출처 : Codechef] Reverse Polish Notation(역폴란드 표기법)이라는 형태의 수학적 기술법이 있습니다. 우리가 아는 일반적인 수식과 다르게, 연산자들이 피연산자들의 다음에 오는 형태를 말합니다. 예를 들면, “3 + 4”의 수식은 “3 4 +”와 같은 방식으로 표현하는 것을 말합니다. 제가 얼핏 알기로는 계산기에서 이와 같은 원리로 연산을 진행한다고 들은 것 같네요 :)
자 그럼 샘플 예제로 주어진 수식들을 살펴봅시다.
(a+(b*c))
((a+b)*(z+x))
((a+t)*((b+(a+c))^(c+d)))이 예제들을 역폴란드 표기법으로 바꿔보면 아래와 같습니다.
abc*+
ab+zx+*
at+bac++cd+^*어떻게 하면 바꿀 수 있을까요? 이게 보기에는 굉장히 쉬워 보이는데, 막상 짤려고 하면 그렇게 간단한 문제가 아니라는 것을 직감하게 됩니다.. 너무 복잡하거든요.. 저도 처음에는 recursive함수로 짜고 함수끼리 서로 call 하는 등.. 정말 가관이었습니다. 여러분도 아래의 해결책을 보기 전에 한번쯤 스스로 구현해 보시는 게 좋은 연습이 될 것 같습니다 :)
코드의 원리는 굉장히 간단합니다. 우리의 생각을 벗어나는 간단함이라 황당하실 수도 있어요 ㅋㅋ 일단 착안해야 하는 부분은, 가장 먼저 닫히는 괄호부터 표현으로 변환시켜가야 한다는 점입니다. 여기서 stack을 활용하시면 굉장히 손쉽게 구현할 수 있습니다.
def transformExpr(expr):
op = [] #연산자들을 담아두는 stack
newExpr = ''
for ch in expr:
if ch == '(': #여는 괄호가 나올 경우 다음 글자로 진행합니다.
continue
elif ch >= 'a' and ch <= 'z': #피연산자가 등장하면 그대로 결과 표현에 붙여줍니다.
newExpr += ch
elif ch == ')': #닫는 괄호가 나올 경우 표현이 끝난 것이므로 마지막으로 stack에 넣어놨던 연산자를 빼서 붙여줍니다.
newExpr += op.pop()
else: #연산자가 등장할 경우 stack에 넣어줍니다.
op.append(ch)
return newExpr
>>> print transformExpr('(a+(b*c))')
abc*+
>>> print transformExpr('((a+b)*(z+x))')
ab+zx+*
>>> print transformExpr('((a+t)*((b+(a+c))^(c+d)))')
at+bac++cd+^*연산자들이 stack에 들어갔기 때문에, First In Last Out의 원리를 이용하여 가장 빨리 닫히는 괄호부터 표현식들을 만들어 나갈 수 있게 됩니다 :) 막상 답을 보니 굉장히 간단하죠~? Stack의 간단한 구조지만 powerful함을 느낄 수 있었네요 :)