백준 - [Gold 4] 1918번 후위 표기식

문제링크: www.acmicpc.net/problem/1918

1918번: 후위 표기식

---

문제 설명

- 중위표현식의 string이 주어짐.

- 중위 표현식을 후위 표현식으로 변환

ex)

- a+b -> ab+

- a+b*c => (a+(b*c)) =>  bc*a+

- A+B*C-D/E => ((A+(B*C))-(D/E)) -> ABC*+DE/-

 

위와 같이 변경해 주는 것입니다. 잘못된 입력은 주어지지 않고

알파벳 대문자와 +, -, *, /, (, ) 로만 이루어진다고 문제에 명시되어있습니다.

---

풀이

Stack을 활용한 문제입니다. 조건을 잘 따져주면 되는 문제입니다.

1. "(" 여는 괄호는 스택에 쌓아놓기

2. ")" 닫힌 괄호면 "("과 나올 때까지 출력하기 

3. 연산자면 스택에 있는 연산자가 우선순위가 높거나 같으면 출력하기 + 마지막에 스택에 현재 연산자 추가(주의)

4. 문자면 바로 출력

 

위와 같은 규칙에 따라 코드를 짜주면 됩니다.

 

코드

import sys
from sys import stdin
from collections import deque

stdin = open("input.txt", "r")
stack = deque()

operator = ['+', '-', '*', '/']

priority = {
    "*": 2, "/": 2,
    "+": 1, "-": 1,
    "(": 0
}
# 중위 표현식 입력
infix = stdin.readline().strip()

answer = ""
for char in infix:
    # 여는 괄호면 stack에 쌓아놓기
    if char == "(":
        stack.append(char)
    # 닫는 괄호면 여는 괄호가 나올 때까지 팝하기
    elif char == ")":
        while stack and stack[-1] != "(":
            answer += stack.pop()
        stack.pop()
    # 연산자면 스택 내부 살피기
    # 우선순위를 봐서 높거나 같으면 출력
    elif char in operator:
        while stack and priority[char] <= priority[stack[-1]]:
            answer += stack.pop()
        stack.append(char)
    # 문자면 바로출력
    else:
        answer += char

# 나머지 팝
while stack:
    answer += stack.pop()

print(answer)