백준 1918번 파이썬 문제풀이(후위 표기식)

---

 

이 문제는 알면 쉽고 모르면 한없이 어렵다. 사실 스택을 사용해야 한다는 생각을 바로 하기가 쉽지 않다.

 

문제의 풀이는

1. 우선 숫자는 바로 출력한다.

2. 숫자가아닌 연산자를 만나면 연산자를 스택에 담으면 된다.

3. 여기서 연산자를 스택에 어떻게 담을지를 생각해야 한다.

4. 연산자 우선순위를 +,- 는 0 *,/ 는 1 , '(' 는 -1 로 둔다.

5. 스택에 현재 연산자가 존재하지 않는다면 연산자를 한개 넣어준다.

6. 스택에 이미 연산자가 있고 맨위의 연산자가 지금 들어갈 연산자보다 우선순위가 높거나 같다면 스택에 있는 연산자들을 우선순위가 낮은게 남을때까지 빼고 출력한 후 마지막에 스택에 넣어준다.  

7. 열린 괄호는 무조건 연산자에 넣어준다. 

8. 닫힌 괄호를 만났다면 열린괄호와 닫힌괄호 안에 있는 모든 연산자를 출력해준다.

 

import sys

sys.stdin = open('input.txt', 'r')
T = int(input())

order = {  # 순서 정해놓기
    '+': 0,
    '-': 0,
    '*': 1,
    '/': 1,
    '(': -1
}

for order_ in range(1, 1 + T):

    formula = input()

    stack = []
    for i in formula:  # 문자열을 돈다.
        if i.isdigit():  # 만약 숫자라면
            print(i, end="")  # 바로 출력
        else:  # 연산자라면
            if i == ')':  # 만약 닫는 괄호라면
                while True:  # 계속해서 돈다.
                    temp = stack.pop()  # 맨 뒤의 연산자를 하나 꺼낸 후
                    if temp == '(':  # 그 꺼낸게 여는 괄호라면
                        break  # 탈출
                    print(temp, end="")  # 여는괄호가 아니라면 출력
            else:  # 만약 닫는 괄호가 아니라면
                if stack:  # 스택에 연산자가 있다면
                    if i != '(' and order[i] <= order[stack[-1]]:  # 만약 여는괄호가 아니고 연산자의 우선순위가 스택의 맨위의 우선순위보다 작거나 같다면
                        while stack and order[i] <= order[stack[-1]]:  # 스택이 존재하고 연산자의 우선순위가 작거나 같을때까지 반복
                            temp = stack.pop()  # 계속 스택의 맨위의 연산자를 뺀다.
                            print(temp, end="")  # 그것을 출력
                        stack.append(i)  # 반복문을 다돌았으면 해당 연산자를 다시 스택에 추가
                    else:  # 여는괄호이거나 우선순위가 스택 맨위의 연산자보다 높다면
                        stack.append(i)  # 그냥 추가
                else:  # 스택에 연산자가 없다면
                    stack.append(i)  # 그냥 추가

    while stack:  # 만약 스택에 연산자가 남아 있다면 다 꺼내 준다.
        print(stack.pop(), end="")
    print()