백준 - 1918 후위표기식

문제

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

풀이

중위 표기식으로 되어있는 수식을 후위 표기식으로 바꾸는 문제
우선 해당 문제를 풀기 위해서는 중위 표기식을 어떤 방법을 이용해서 후위 표기식으로 표현 할 것인지 생각해야한다.
중위 표기식을 후위 표기식으로 바꾸는데 가장 생각난 방법은 두가지가 있다.
1. 스택을 이용한 방법
2. 트리 순회를 이용한 방법
해당 풀이는 스택을 이용하여 문제를 풀어본다.

연산 우선순위 조건에 맞는 스택구조 사용

표기식을 바꾸려면 연산자의 위치를 조건에 맞게 수정해야한다. 따라서 피연산자는 그대로 출력한다.
그리고 문제에서 등장하는 연산자는 +, -, *, /, (, )로 구성되어있다.

따라서 올바른 표기식을 위해서는 연산 순서에 맞게 배치시켜야한다.
누구나 알듯이 연산의 우선순위는 +,- < *,/ < () 순서로 되어있다. 따라서 아래의 세 조건을 만족시켜서 스택에 추가해야한다.

1. 하지만 스택은 후입선출(LIFO)의 특성을 가지기 때문에 항상 가장 마지막에 저장된 연산자가 우선순위가 가장 높아야한다. 연산의 우선순위가 높은게 먼저 연산이 수행되어야하기 때문이다.

   ---

2. 그리고 연산의 우선순위가 같은 연산자가 스택에 존재해서도 안된다. 왜냐하면 같은 연산자가 있으면 등장한 순서대로 연산이 수행되어야하기 때문이다.

   ---

3. 괄호의 경우 연산자 우선순위의 적용이 괄호 안, 밖이 철저하게 구분되어야한다.

그렇다면 이 세 조건을 이용하여 문제에 나와있는 연산자의 조건을 만족시켜보자

1. +, - 의 경우 최하위 우선순위 조건을 가지는 연산자이다. 따라서 +, - 연산자가 등장하게 된다면 저장된 연산자 스택에 있는 모든 연산자를 출력해야한다. (1번, 2번 조건) 하지만 '(' 연산자를 만나게 된다면 해당 연산자를 출력하고 출력을 종료해야한다 (3번 조건)

   ---

2. *, - 연산자의 경우, 두번째로 우선 순위가 높은 연산자이다. 스택에 +,- 연산자가 있으면 스택 최상단에 저장할 수 있다. 하지만 스택 최상단에 동일한 우선순위의 연산자가 있을경우, (2번 조건)때문에 스택 최상단의 연산자를 출력하고 스택에 저장해야한다.

   ---

3. () 연산자의 경우 괄호 안과 밖의 연산 우선순위를 구분하기 위해 존재한다. 따라서 '(' 연산자는 스택 최상단에 들어가고 ')' 연산자의 경우 괄호 안 후위 연산자 출력이 이미 종료되었고 마지막 연산자만 남아있다. 따라서 해당 연산자를 출력시켜주면 된다.

소스코드

import sys
from collections import deque

infix = sys.stdin.readline().rstrip()
result = []
oper = deque()

# 동일 연산자끼리는 들어와있으면 다 빠져있어야함
for word in infix:
    # + - 연산자는 우선순위가 제일 낮음 그래서 들어와서 저장한 연산자는 다 빼야함
    if word == '+' or word == '-':

        #괄호 안의 연산자인지 아닌지 모르기 때문에 일단 괄호 만날 때 까지 연산자 우선으로 다 빼야함
        while oper and oper[-1] != '(':
            result.append(oper.pop())
        oper.append(word)
    elif word == '*' or word == '/':
        while oper:

            # *,/ 연산자는 순서대로 처리해야해서 먼저 들어온거 다 빼야함
            if oper[-1] =='*' or oper[-1] == '/':
                result.append(oper.pop())
            else:
                break
        oper.append(word)
    elif word == '(':
        oper.append(word)
    
    #괄호 끝났으므로 괄호안에 연산자 다 빼야함
    elif word == ')':
        while oper and oper[-1] != '(':
            result.append(oper.pop())
        oper.pop()
    else:
        result.append(word)
while oper:
    result.append(oper.pop())
print(''.join(result))