[SWEA] 1224_계산기3 (후위 표기식 이용)

후위표기식,,, 처음 문제로 접했을 땐 대체 이게 뭐지 일단 이해는 안 가지만 하라는 대로 코드짜고 그냥 흐린눈으로 넘어가자!! 생각했는데 그 이후로 후위표기식 문제가 3개나 더 나왔다.. 어쩔수 없이 직면해야만 했던..

우리가 사용하는 중위 표기식을 후위 표기식으로 바꾸는 과정을 간단하게 설명하자면 아래와 같다.

 

#1.

식: 3+(4+5)*6+7

stack : [ ]

출력: 3

-> 숫자이기 때문에 바로 출력

 

#2.

식: 3+(4+5)*6+7

stack : [ + ]

출력: 3

-> 연산자 스택이 비어있기 때문에 스택에 + 추가

 

#3.

식: 3+(4+5)*6+7

stack : [ +, ( ]

출력: 3

-> ( 는 + 보다 우선순위가 높기 때문에 스택에 ( 추가

( ' ( '는 우선순위가 제일 높기 때문에 무조건 stack에 추가를 하게 된다.)

 

#4.

식: 3+(4+5)*6+7

stack : [ +, ( ]

출력: 34

-> 숫자이기 때문에 바로 출력

 

#5.

식: 3+(4+5)*6+7

stack : [ +, (, + ]

출력: 34

-> 스택의 top이 ( 이기 때문에 스택에 + 추가

 

#6.

식: 3+(4+5)*6+7

stack : [ +, (, + ]

출력: 345

-> 숫자이기 때문에 바로 출력

 

#7.

식: 3+(4+5)*6+7

stack : [ + ]

출력: 345+

-> ) 은 ( 이 나올때까지 스택을 계속 pop한다. (단, ( 와 ) 는 출력 X)

 

#8.

식: 3+(4+5)*6+7

stack : [ +, * ]

출력: 345+

-> * 는 + 보다 우선순위가 높기 때문에 스택에 * 를 추가

 

#9.

식: 3+(4+5)*6+7

stack : [ +, * ]

출력: 345+6

-> 숫자이기 때문에 바로 출력

 

#10.

식: 3+(4+5)*6+7

stack : [ + ]

출력: 345+6*+

-> 스택의 top이 +보다 우선순위가 작을때까지 pop하고 마지막에 스택에 연산자 + 추가.

(그런데 +는 우선순위가 제일 낮기 때문에 끝까지 다 pop을 하게 된다.)

 

#11.

식: 3+(4+5)*6+7

stack : [ + ]

출력: 345+6*+7

-> 숫자이기 때문에 바로 출력

 

#12.

식: 3+(4+5)*6+7

stack : [ ]

출력: 345+6*+7+

-> 이제 스택에 남은 연산자 모두 pop

 

결과 : 345+6*+7+

 

📕 문제

문자열로 이루어진 계산식이 주어질 때, 이 계산식을 후위 표기식으로 바꾸어 계산하는 프로그램을 작성하시오.
예를 들어
“3+(4+5)*6+7”
라는 문자열로 된 계산식을 후위 표기식으로 바꾸면 다음과 같다.
"345+6*+7+"
변환된 식을 계산하면 64를 얻을 수 있다.
문자열 계산식을 구성하는 연산자는 +, * 두 종류이며 문자열 중간에 괄호가 들어갈 수 있다.
이 때 괄호의 유효성 여부는 항상 옳은 경우만 주어진다.
피연산자인 숫자는 0 ~ 9의 정수만 주어진다.

 

[입력]

각 테스트 케이스의 첫 번째 줄에는 테스트 케이스의 길이가 주어진다. 그 다음 줄에 바로 테스트 케이스가 주어진다.
총 10개의 테스트 케이스가 주어진다.

 

[출력]

#부호와 함께 테스트 케이스의 번호를 출력하고, 공백 문자 후 답을 출력한다.

 

for tc in range(1, 11):
    N = int(input())
    string = input()
    stack = []
    result = ''
    for i in string:
        if i.isdigit():  # 피연산자인지 아닌지 확인
            result += i
        else:
            if i == '(':
                stack.append(i)
            elif i == '*':
                while stack and stack[-1] == '*':
                    result += stack.pop()
                stack.append(i)
            elif i == '+':
                while stack and stack[-1] != '(':
                    result += stack.pop()
                stack.append(i)
            elif i == ')':
                while stack and stack[-1] != '(':
                    result += stack.pop()
                stack.pop()
    while stack:
        result += stack.pop()

    stack = []
    for i in result:
        if i == '+':
            stack.append(stack.pop() + stack.pop())
        elif i == '*':
            stack.append(stack.pop() * stack.pop())
        else:
            stack.append(int(i))

    print('#{} {}'.format(tc, stack.pop()))

-> 후위표기식을 이용해서 값을 계산하는 코드를 짜고 나니 차라리 이게 더 계산하기 쉽겠다는 생각을 하게 됐다. 우리가 사용하는 중위 표기식을 이용해서 값을 계산하려면 어디를 먼저 계산해야 할지 다 비교해줘야 해서 그게 더 힘들수도... 역시 조상님들의 지혜 👍