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

1918번 - 후위 표기식

 

단순하지만 머리어픈 그런 문제이다.

 

후위 표기식이 무엇인지 알고 있다면 설명은 그냥 읽지 않아도 된다. 그냥 중위 표기식을 후위 표기식으로 바꾸는 문제이다. 표기식 문제가 나오면 스택을 사용한다는 것은 알고 있어야 한다. 스택을 사용하여 풀 수 있으니 재귀로도 풀 수 있을 것이다.

 

만약 어떻게 구현해야 할지 전혀 모르는 상태에서 시작했는데 빠른 시간 내에 풀어냈다면 정말 머리 좋은 사람이라고 생각한다.

 

딱히 어떤 알고리즘을 사용하는 것은 아니고 괄호와 연산자의 우선순위를 이용해서 말 그대로 적절하게 전환하면 된다.

 

내 코드:

# dawitblog.tistory.com/152
stack,ans = [],[]
# 우선순위 정의
priority = {
    '*':0,
    '/':0,
    '+':1,
    '-':1
}
for char in '('+input()+')':
    # 알파벳이라면
    if char.isalpha():
        ans.append(char)

    # 여는 괄호라면 스택에 추가
    elif char == '(':
        stack.append(char)
    
    # 닫는 괄호라면 해당 괄호 안에 남은 모든 연산자 출력
    elif char == ')':
        while stack[-1] != '(':
            ans.append(stack.pop())
        stack.pop()
    
    # 연산자라면 괄호 내부의 자신보다 우선순위가 높거나 같은 연산자 출력 후 스택에 자신 추가
    else:
        while stack[-1] != '(' and priority[char] >= priority[stack[-1]]:
            ans.append(stack.pop())
        stack.append(char)

print(''.join(ans))

 

먼저 연산자 사이의 우선순위를 정한다. *와 / 를 +와 -보다 낮은 수(높은 우선순위)로 두면 된다.

 

이후에 for 문으로 한번 순회하면서,

 

알파벳인 경우 그냥 출력하면 된다. 연산자의 표기식이 바뀐다 하더라도 알파벳의 순서 자체는 바뀌지 않는다.

 

여는 괄호인 경우 스택에만 추가한다.

 

닫는 괄호라면 해당 괄호를 연 곳까지 남은 모든 연산자를 출력한다.

 

연산자라면 해당 괄호 내에서, 자신보다 우선순위가 높거나 같은(우선순위가 같다면 먼저 나온 연산자를 먼저 계산해야 하므로) 연산자를 스택에서 꺼내어 출력한다.  이전에 닫는 괄호에서 남은 모든 연산자를 그냥 출력해도 우선순위가 꼬일 일이 없는 이유는 이 과정에서 항상 스택의 동일 괄호 내에는 우선순위가 같은 연산자만 남게 되기 때문이다. 따라서 순서대로 그냥 출력할 수 있다.