[BOJ] 1918번 - 후위 표기식

---

문제설명

https://www.acmicpc.net/problem/1918

1918번: 후위 표기식

사고과정

• 스택에 무엇을 넣어야 할지 매우 고민했다. 괄호만? 연산만? 문자열도? 결국 괄호랑 연산을 하나의 스택에, 문자열을 또 하나의 스택에 넣으려고 했다. 나름 풀려고 노력했지만 못 풀었다..
• 다른 분의 풀이를 보니 괄호, 연산을 하나의 스택에 넣는 건 맞았지만 문자열은 그냥 바로 결과값에 붙이면 되었다.
• 해당 문제를 풀이하는 과정을 단계화해보면 아래와같다.
• 1. 스택에는 무엇을 넣을 것인가? 괄호와 연산을 넣었다. 괄호는 스택에서 어느 범위까지 연산을 pop해서 이어 붙일 것인지 위함이고 연산은 연산 간의 우선순위가 있기 때문에 스택에 넣었다.
• 2. 곱하기, 나누기는 가장 우선하는 연산이다. 따라서 현재 곱하기 또는 나누기 연산을 마주쳤을 때, 이미 스택에 존재하고 있는 또 다른 곱하기 또는 나누기 연산이 나올 때까지 pop해서 결과값에 이어 붙인다.
• 3. 더하기, 빼기는 가장 하위의 순위 연산이기 때문에 스택에 열린 소괄호가 마지막 원소가 아니라면 모두 pop해서 이어 붙인다.
• 4. 닫힌 괄호가 문자열로 등장하면, 스택에서 열린 괄호가 마지막 원소가 될 때까지 모두 pop해서 이어 붙인다. 그리고 스택에서 남은 열린 괄호를 없애기 위해 pop해서 날려버린다.
• 5. 문자열을 모두 돈 후, 스택에 남은 연산기호들을 결과값에 마저 이어 붙인다.

풀이(스스로 못 푼 풀이)

import sys

input = sys.stdin.readline
string = input().rstrip()

stack = []  # 스택에는 괄호와 연산 기호를 넣는다
result = ''  # 후위 표기식 결과

for s in string:
    if s.isalpha():
        result += s
    else:
        if s == '(':
            stack.append(s)
        elif s == '*' or s == '/':
            # 스택에서 마지막 원소가 스택에 이미 있던 *, /가 나오면 계속 pop해서 결과에 붙이기 -> stack[-1] != '(' 로 or 조건 붙이면 +,- 인 경우도 붙여버리므로 안 됨!
            while (stack and stack[-1] != '(') and (stack[-1] == '*' or stack[-1] == '/'):
                result += stack.pop()
            # 지금 마주친 * 또는 / 연산 기호 스택에 넣기
            stack.append(s)
        elif s == '+' or s == '-':
            # 스택에서 마지막 원소가 ( 열린괄호일 때까지 계속 pop해서 결과값에 붙이기( +, -는 가장 낮은 연산순위이기 떄문)
            while stack and stack[-1] != '(':
                result += stack.pop()
            # 지금 마주친 + 또는 - 연산 기호 스택에 넣기
            stack.append(s)
        elif s == ')':
            while stack and stack[-1] != '(':
                result += stack.pop()
            # 스택에 있던 ( 열린괄호 날리기
            stack.pop()

# 스택에 남아있는 모든 연산 기호 결과값에 붙이기
while stack:
    result += stack.pop()

print(result)