왜 postfix 가 필요한가?
우리는 기본적으로 infix 방법으로 수식들을 쓴다.
1과 3을 더하고 싶으면 1 + 3 이라고 쓴다. 이게 infix 방법이다.
하지만 stack을 사용하여 컴퓨터 계산을 하기 위해 postfix가 고안되었다.
postfix를 사용하면 괄호 사용이 필요 없어지고, 컴퓨터가 더 효율적으로 계산 할수 있다.
아래 사진과 같이 infix 를 postfix 로 계산할 수 있다.
먼저 "A + B * C" infix표기를 postfix 표기로 변경하고 싶다면 다음과 같은 로직을 따르면 된다.
우선 스택을 하나 만든다.
이 스택에는 연산자들이 우선순위에 따라 담기게 될 것이다.
이름을 opstack 이라고 부른다.
그리고 리스트를 하나 만든다.
이 리스트는 postfix 방식으로 변환될 값들이 들어가 있는 리스트이다.
이름을 outstack 이라 부른다.
"A + B * C" 에서 'A' 를 먼저 본다.
A는 피연산자이기 때문에, outstack 에 넣는다. 앞으로 나오는 모든 피연산자는 outstack 에 바로 넣을 것이다.
#outstack
['A']
#opstack
[]그 다음에 '+'를 본다. '+'는 연산자이기 때문에 opstack에 넣는다.
#outstack
['A']
#opstack
['+']그 다음에 'B' 는 outstack 에 넣는다.
#outstack
['A', 'B']
#opstack
['+']그 다음 ' * ' 은 연산자이다. opstack에 담겨있는 다른 연산자와 우선순위를 비교한다. 만약 넣으려는 연산자가 들어있는 연산자보다 우선순위가 높다면 바로 넣으면 된다.
하지만 넣으려는 연산자가 들어있는 연산자보다 우선순위가 낮다면, 넣으려는 연산자보다 opstack에 있는 우선 순위의 연산자들을 다 pop 한다.
이 경우에 * 는 + 보다 우선순위이기 떄문에, 바로 opstack 에 넣으면 된다.
#outstack
['A', 'B']
#opstack
['+', '*']그리고 C 는 outstack 에 넣는다.
#outstack
['A', 'B', 'C']
#opstack
['+', '*']이제 주어진 모든 연산자와 피연산자를 확인했다. 이제 opstack 에 있는 연산자들을 모두 pop 시킨다.
#outstack
['A', 'B', 'C', '*', '+']
#opstack
[]이렇게 infix 에서 postfix 로 변경이 가능하다!
그렇다면 컴퓨터는 어떻게 postfix 된 수식을 계산할까?
#postfix 된 리스트
['A', 'B', 'C', '*', '+']우선 왼쪽에서 오른쪽으로 수식을 읽으면서 각 요소를 처리한다.
우선 피연산자를 만나면 스택에 push 한다.
'A'를 보고 stack에 push 한다.
'B'를 보고 stack에 push 한다.
'C'를 보고 stack에 push 한다.
# stack
[ 'A', 'B', 'C' ]그러다 연산자인 * 을 만나면 'B' 와 'C' 를 pop 하고
'B * C' 계산하여 다시 스택에 넣는다.
# stack
[ 'A', 'B * C' ]그리고 '+' 를 만나면, 또 'B C' 와 'A' 를 pop 하고 계산을 한다.
'A' + 'B C' 이 값을 다시 스택에 넣는다.
수식을 끝까지 처리한 후 스택에 남아있는 최종결과가 수식을 계산한 값이 된다.
그러면 코드로 위에 로직을 구현해보자!
코드구현
import sys
def infix_to_postfix (arr) :
outstack = []
opstack = []
for i in range(0, len(arr)) :
if arr[i] == "*" :
if len(opstack) == 0 :
opstack.append(arr[i])
else :
for j in range(len(opstack)-1, -1, -1) :
if opstack[j] == '/' :
outstack.append(opstack.pop())
else :
opstack.append(arr[i])
break
elif arr[i] == "/" :
if len(opstack) == 0 :
opstack.append(arr[i])
else :
for j in range(len(opstack)-1, -1, -1) :
if opstack[j] == '*' :
outstack.append(opstack.pop())
else :
opstack.append(arr[i])
break
elif arr[i] == '+' :
if len(opstack) == 0 :
opstack.append(arr[i])
else :
for j in range(len(opstack)-1, -1, -1) :
if opstack[j] == '*' or opstack[j] == '/' or opstack[j] == '-' :
outstack.append(opstack.pop())
else :
opstack.append(arr[i])
break
elif arr[i] == '-' :
if len(opstack) == 0 :
opstack.append(arr[i])
else :
for j in range(len(opstack)-1, -1, -1) :
if opstack[j] == '*' or opstack[j] == '/' or opstack[j] == '+' :
outstack.append(opstack.pop())
else :
opstack.append(arr[i])
break
elif arr[i] == "(" :
opstack.append(arr[i])
elif arr[i] == ")" :
for h in range(len(opstack)-1, -1, -1 ):
if opstack[h] == "(" :
opstack.pop()
break
else :
outstack.append(opstack.pop())
else :
outstack.append(arr[i])
print("answer: ", outstack)
print("opstack: ",opstack)
while len(opstack) != 0 :
outstack.append(opstack.pop())
return outstack # 계산하는 로직 구현
def calculate (arr) :
arr2 = collections.deque()
for i in arr :
arr2.append(i)
stack = []
while len(arr2) != 0 :
temp = arr2.popleft()
if temp == "*" or temp == "/" or temp == "+" or temp == "-" :
a = stack.pop()
c = stack.pop()
if temp == "*":
stack.append(int(a) * int(c))
elif temp == "/" :
stack.append(int(c) / int(a))
elif temp == "+" :
stack.append(int(a) + int(c))
elif temp == "-" :
stack.append(int(a) - int(c))
else :
stack.append(temp)
if len(arr2) == 0 :
break
print(stack[0])
