[SW Expert Academy] 1224. 계산기3

1224. 계산기3

---

문제)

 

문자열로 이루어진 계산식이 주어질 때, 이 계산식을 후위 표기식으로 바꾸어 계산하는 프로그램을 작성하시오.

예를 들어

“3+(4+5)*6+7”

라는 문자열로 된 계산식을 후위 표기식으로 바꾸면 다음과 같다.

"345+6*+7+"

변환된 식을 계산하면 64를 얻을 수 있다.

문자열 계산식을 구성하는 연산자는 +, * 두 종류이며 문자열 중간에 괄호가 들어갈 수 있다.

이 때 괄호의 유효성 여부는 항상 옳은 경우만 주어진다.

피연산자인 숫자는 0 ~ 9의 정수만 주어진다.

[입력]

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

총 10개의 테스트 케이스가 주어진다.

[출력]

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

 

 

 

 

 

풀이)

def postfix(a):
    stack = []
    fix = ""
    operator = {"*": 3, "/": 3, "+": 2, "-": 2, "(": 1} # 우선 순위 // 딕셔너리로 우선순위 파악
 
    for i in a:
        if i == "(": # 괄호 먼저 처리
            stack.append(i)
 
        elif i == ")":
            while stack[-1] != "(":
                fix += stack.pop()
            else:
                stack.pop() # 남아있는 "(" 처리
 
        elif not stack and i in operator: # 스택이 비어있고, i가 연산자이면
            stack.append(i)
 
        elif stack and i in operator: # 스택이 비어있지 않고, i가 연산자이면
            while stack: # 스택안에 요소가 있는 동안 반복, 자신보다 스택안에 있는 것이 순위가 같거나 높으면 다 꺼낸다.
                if operator[i] <= operator[stack[-1]]:
                    fix += stack.pop()
                else: # 다 꺼내고 멈출 수 있도록
                    break
            stack.append(i)
        else: # 피연산자인 경우 바로 출력
            fix += i
    else:
        for j in range(len(stack)):
            fix += stack.pop()
    return fix # 모든 과정이 끝난 후 fix를 리턴
 
 
def cal(b):
    stack = []
    operator = ["*", "/", "+", "-"]
    for i in b:
        if not i in operator: # 피연산자이면 stack에 push
            stack.append(i)
 
        else:
            y = int(stack.pop())
            x = int(stack.pop())
            if i == "*":
                stack.append(x * y)
            elif i == "/":
                stack.append(x // y)
            elif i == "+":
                stack.append(x + y)
            else:
                stack.append(x - y)
    else:
        return stack
 
for _ in range(10):
    n = int(input())
    sentence = input()
    a = postfix(sentence)
    print(f"#{_ + 1}", *cal(a))

 

 

---

문제 출처 : https://swexpertacademy.com/main/main.do

SW Expert Academy

※ SW Expert 아카데미는 원칙적으로 문제를 무단 복제하는 것을 금지합니다.

학습용으로 문제를 가져왔으나, 문제가 될 시 수정 및 삭제하겠습니다.