스택(stack) 자료구조를 활용하면 일반적인 중위 표기(infix notation)를 후위 표기(postfix)로 변환하여 컴퓨터가 계산하기 편리하게 만들어줄 수 있다.
방법은 다음과 같다.
e가 피연산자인 경우result에append한다.e가 연산자인 경우e보다 우선순위가 같거나 높은 연산자들을stack에서pop하여result에append한다.
반복이 끝나면 stack에 남은 연산자들을 하나씩 pop하여 result에 append한다.
def infix_to_postfix(expression, operator):
rank = {}
for i in range(len(operator)):
rank[operator[i]] = i
result = []; stack = [];
for e in expression:
if e in operator:
while len(stack) > 0 and rank[stack[-1]] <= rank[e]:
result.append(stack.pop())
stack.append(e)
else:
result.append(e)
while len(stack) > 0:
result.append(stack.pop())
return result