1. 후위표기식(postfix expression)

일반적으로 사람이 계산을 할 때 쓰는 표기식은 다음과 같이 '(3 + 4) × 2 % 7 - 1' 연산자가 피연산자(숫자)가 가운데 위치하는 중위표기식으로 쓴다. 그래서 연산식 전체를 모두 본 후 순서에 따라 연산을 진행하는 반면, 컴퓨터는 순서대로 하나씩 꺼내어 연산을 하기에 스택을 활용하여 연산을 하기에 적합한 방식으로 교체한 후 연산을 한다. 그것이 바로 후위표기식이며 연산자가 피연산자(숫자) 뒤에 위치를 하게 됨으로써 후위표기식이라 명명한다.

2. 스택(Stack) 활용

중위표기식을 후위표기식으로 바꿔볼 때 후입선출(LIFO:Last In First Out) 구조인 스택 자료구조가 활용된다. 어떤 식으로 스택을 활용하여 후위표기식으로
바뀌는지 살펴보고 바뀐 후위표기식이 어떻게 연산이 되어가는지도 확인해보자.

2.1 중위표기식을 후위표기식으로

실행 전 활용할 변수 두 가지, stack = [ ]과 후위표기식으로 바꾼 것을 담을 pos = ' '를 선언한다.
1. 중위표기식을 반복문을 통해 변수에 할당하면서, 연산자가 나오면 stack에 append()하고 피연산자(숫자)가 나오면 pos에 더한다.
2. 닫는 괄호 ')'가 나온다면 여는 괄호 '('가 나올 때까지 pop()하여 피연산자를 pos에 더한다.
3. 할당 된 것이 '×', '%'일 때, 우선 순위가 '+'와 '-'보다 높기에 stack 위쪽에 '+'와 '-'가 있으면 pos에 더해주고, '×', '%'가 있으면 먼저 쌓인 것이 우선 순위가 높기에 stack에서 '×'나 '%' 빼서 pos에 더한 후 stack에 쌓는다.
4. 할당 된 것이 '+', '-'일 때, stack에 쌓인 것이 '×', '%'이면 '×', '%'가 우선 순위가 높기에 꺼내어 pos에 더해주고 '+'와 '-'가 있더라도 먼저 쌓인 것이 우선 순위가 높기에 빼서 pos에 더해 준 후 stack에 쌓는다. 다시 말해, 할당 된 것이 '+', '-'일 때는 stack에 쌓여있는 모든 연산자가 우선 되기에 stack이 모두 빌 때까지 꺼내거나 '('를 만날 때까지 모두 꺼내면 된다.
5. pos에는 괄호는 더하지 않고 stack에서 꺼내기만 한다.

예시 '(3 + 4) × 2 % 7 - 1' 을 가지고 다시 진행해보자.
1. 중위표기식이 반복문으로 순서대로 변수에 할당되어 나오는데, stack로 활용할 리스트 하나와 후위표기식으로 바뀐 것을 담을 변수를 생성한다.
(예시: stack = [ ], pos = ' ')
2. 여는 괄호 '('는 먼저 stack에 쌓고 다음 3은 pos에 더해준 후 '+'이 나오면 stack에 append한다.
3. 4를 pos에 더한 후 닫는 괄호 ')'를 만나면 괄호 안의 연산이 우선되기에 stack에서 닫는 괄호 '('를 만날 때까지 pop을 하며 연산자가 pop이 되면 이 때 pos에 '+'를 더해준다.(현재까지 stack = [ ], pos = '34+')
4. '×'를 만나면 stack에 쌓아주고 '2'는 pos에 더해준 준다. (현재까지 stack = [×], pos = '34+2')
5. '%'를 stack에 쌓아줄 때 stack에 같은 순위('×'와 '%'은 같은 순위)가 있으면, 순서는 먼저 들어온 '×'가 먼저 연산이 되어야 하기에 stack에서 꺼낸(pop) 후 pos에 더한다. 그 후에 stack에 '%'를 쌓는다.(현재까지 stack=[%], pos='34+2×')
6. 7이 나오면 pos에 더해주고, '-'를 만나면 stack에 있는 '%'의 우선 순위가 높기때문에 stack에서 빼서 pos에 더해주고 '-'는 stack에 쌓은 후 마지막 1을 pos에 더해준다.(stack=[-], pos = '34+2×7%1'
7. 반복문이 끝나면 stack에 남아 있는 모든 것을 꺼내어(pop) pos에 더해준다.(pos = '34+2×7%1-')

2.2 문제

중위표기식 '(3 + 4) × 2 % 7 - 1'을 후위표기식으로 출력하시오.

2.3 풀이

n = input()(3+4)*2/7-1
stack = []
pos = ''
for i in n:
    if i.isdigit():# isdigit은 숫자 형태의 문자를 판별
        pos += i
    else: # 숫자 형태가 아니라면 연사자이기에 stack에 쌓는다.
        if i == '(': 
            stack.append(i)
        elif i == '*' or i == '/': # 앞에 쌓여있을 우선 순위가 같은 '*'와 '/'를 빼서 pos에 더한다.
            while stack and (stack[-1] == '*' or stack[-1] == '/'):
                pos += stack.pop()
            stack.append(i) # 우선 순위가 while문으로 정리가 되면 그 때 stack에 쌓는다.
        elif i == '+' or i == '-': # 우선 순위가 제일 낮기에 '('가 나오거나 stack가 빌 때까지 다 꺼내면 된다.
            while stack and stack[-1] != '(':
                pos += stack.pop()
            stack.append(i)
        elif i == ')': # 닫는 괄호가 나왔다면 여는 괄호를 만날 때까지 모두 꺼낸 후, 여는 괄호는 꺼내기만 한다.
            while stack and stack[-1] != '(':
                pos += stack.pop()
            stack.pop()
while stack: # 마지막으로 stack에 남아있는 것이 있을 경우 모두 꺼내어 pos에 더하면 된다.
    pos += stack.pop()
print(pos)
입력 : (3+4)*2/7-1
출력 : 34+2*7/1-

3. 1 후위표기식 계산하기

이제 후위표기식으로 되어 있는 것을 실제로 어떻게 연산이 되는지 알아보도록 하자.
중위표기식을 후위표기식으로 바꾸는 이유가 컴퓨터는 연산을 순서대로 진행하기 때문이라고 했다. 그 말은 후위식으로 바뀌었다면 순서대로 stack에 쌓으면서 연산만 하면 된다는 말이다.
1. 마찬가지로 stack을 하나 생성한다.
2. 이번엔 stack에 숫자를 쌓으면서 계산한다. 피연산자 숫자가 할당이 되면 stack에 쌓고 연산자가 나오면 stack에 쌓여있는 2개의 숫자를 꺼내 연산한다.
주의점은 빼기나 나눗셈을 할 때 순서를 생각해야 하기에, 두번째 꺼낸 숫자가 첫번째 꺼낸 숫자에 의해 연산이 된다는 것이다.
3. 연산한 것을 다시 stack에 쌓는다.
4. 2번 3번을 순서대로 끝까지 반목문을 진행하고 마지막에 stack에 남아있는 숫자가 연산한 결과이다.

예시로 '34+2*7/1-'를 여산해보자.
1. 3과 4가 stack에 쌓이고 '+"를 만나면 2개의 숫자를 꺼내서 두번째 꺼낸 수와 첫번째 꺼낸 수를 더해 stack에 다시 쌓는다.(stack = [7])
2. 2를 stack에 쌓고 '×'이 나오면 2개의 숫자를 꺼내서 두번째 꺼낸 수에 첫번째 꺼낸 수를 곱한 후 stack에 다시 쌓는다.(stack = [14])
3. 7을 sktack에 쌓고 '/'이 나오면 2개의 숫자를 꺼내 두번째 꺼낸 수에 첫번째 꺼낸 수를 나눈 후 stack에 다시 쌓는다.(stack = [2])
4. 1을 stack에 쌓고 '-'가 나오면 2개의 숫자를 꺼내 두번째 꺼낸 수에 첫번째 꺼낸 수를 뺀 후 stack에 다시 쌓는다.(stack = [1])
5. 반복문이 다 끝나고 stack에는 '1'만 남았으므로 후위식 연산 결과는 '1'인 것을 알 수 있다.

3. 2 문제

후위표기식 '34+2*7/1-'을 연산하여 결과를 출력하시오.

3. 3 풀이

n = input()
stack = []
for i in n:
    print(stack) # print()을 이용해서 stack에 쌓이고 연산되어 가는 과정도 살펴보자.
    if i.isdigit(): # 숫자 형식의 문자를 판별하는 함수로 연산자인지 피연산자인지 판별
        stack.append(int(i)) # 피연산자라면 숫자 형식인 문자를 숫자로 케스팅하여 stack에 쌓는다.
    else:
        if i == '*':
            a = stack.pop()# 첫번째 꺼낸 
            b = stack.pop()# 두번째 꺼낸
            stack.append(b * a) # 두번째 꺼낸 수에서 첫번째 꺼낸 수를 곱한 후, stack에 다시  쌓는다.
        elif i == '/':
            a = stack.pop()
            b = stack.pop()
            stack.append(int(b / a))# 나눗셈 '/'의 결과는 실수이기에 정수로 바꿨다. 그냥 둬도 무방하다.
        elif i == '+':
            a = stack.pop()
            b = stack.pop()
            stack.append(b + a)
        elif i == '-':
            a = stack.pop()
            b = stack.pop()
            stack.append(b - a)
print('연산 결과: ', stack.pop())
입력 : 34+2*7/1-
출력 :
[] # 처음엔 빈 리스트가 출력되고
[3] # 첫번째 수가 stack에 쌓인다.
[3, 4]
[7] # 덧셈이 나오면 두 수를 더한 후 다시 stack에 쌓인다.
[7, 2]
[14] # 곱셈이 나온 경우
[14, 7]
[2] # 나눗셈이 나온 경우
[2, 1]
연산 결과:  1 # 뺄셈이 나온 경우