백준 1918번 파이썬

문제 링크

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

1918번: 후위 표기식

 

시간 제한 / 메모리 제한

2 초

128 MB

문제

수식은 일반적으로 3가지 표기법으로 표현할 수 있다. 연산자가 피연산자 가운데 위치하는 중위 표기법(일반적으로 우리가 쓰는 방법이다), 연산자가 피연산자 앞에 위치하는 전위 표기법(prefix notation), 연산자가 피연산자 뒤에 위치하는 후위 표기법(postfix notation)이 그것이다. 예를 들어 중위 표기법으로 표현된 a+b는 전위 표기법으로는 +ab이고, 후위 표기법으로는 ab+가 된다.

이 문제에서 우리가 다룰 표기법은 후위 표기법이다. 후위 표기법은 위에서 말한 법과 같이 연산자가 피연산자 뒤에 위치하는 방법이다. 이 방법의 장점은 다음과 같다. 우리가 흔히 쓰는 중위 표기식 같은 경우에는 덧셈과 곱셈의 우선순위에 차이가 있어 왼쪽부터 차례로 계산할 수 없지만 후위 표기식을 사용하면 순서를 적절히 조절하여 순서를 정해줄 수 있다. 또한 같은 방법으로 괄호 등도 필요 없게 된다. 예를 들어 a+b*c를 후위 표기식으로 바꾸면 abc*+가 된다.

중위 표기식을 후위 표기식으로 바꾸는 방법을 간단히 설명하면 이렇다. 우선 주어진 중위 표기식을 연산자의 우선순위에 따라 괄호로 묶어준다. 그런 다음에 괄호 안의 연산자를 괄호의 오른쪽으로 옮겨주면 된다.

예를 들어 a+b*c는 (a+(b*c))의 식과 같게 된다. 그 다음에 안에 있는 괄호의 연산자 *를 괄호 밖으로 꺼내게 되면 (a+bc*)가 된다. 마지막으로 또 +를 괄호의 오른쪽으로 고치면 abc*+가 되게 된다.

다른 예를 들어 그림으로 표현하면 A+B*C-D/E를 완전하게 괄호로 묶고 연산자를 이동시킬 장소를 표시하면 다음과 같이 된다.

결과: ABC*+DE/-

이러한 사실을 알고 중위 표기식이 주어졌을 때 후위 표기식으로 고치는 프로그램을 작성하시오

 

입력

첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 알파벳 대문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 수식은 주어지지 않는다. 표기식은 알파벳 대문자와 +, -, *, /, (, )로만 이루어져 있으며, 길이는 100을 넘지 않는다. 

출력

첫째 줄에 후위 표기식으로 바뀐 식을 출력하시오

예제 입력

A+B*C-D/E

예제 출력

ABC*+DE/-

 

문제 풀이를 위해 생각한 것

1. 연산자 우선순위는 어떻게 설정할까?
   1. '+', '-'  <  '*', '/' < '(', ')'
   2. 같은 우선순위라면 먼저 등장한 연산자가 우선
2. 연산자의 우선순위를 알고리즘의 어떤 단계에서 어떻게 고려해야 할까?
   1. 스택에 원소가 없거나, 스택 최상단 원소가 현재 검사하는 원소보다 우선순위가 낮은 연산자라면 현재 원소를 stack에 push한다. (스택의 LIFO 특징에 따라 먼저 연산하기 위해)
   2. 입력받은 중위표기식의 원소를 하나씩 검사하며, 스택의 최상단 원소와 현재 원소 비교
   3. 스택의 최상단 값이 현재 연산자 원소보다 우선순위가 높거나, 우선순위는 동일한데 먼저 등장한 연산자이면 스택의 최상단 원소를 pop해 prefix에 추가(연산)한다.
      
      1. 이때 '('의 등장은 괄호 내 연산자의 우선순위를 높여주기에, '(' 이전까지만 pop해 prefix에 추가한다. '('가 없으면 스택 내에서 현재 원소보다 우선순위가 높은 원소를 모두 pop해 prefix에 추가한다.
      2. 현재 원소가 ')'이면 '(' 가 스택의 최상단 원소가 될 때까지 pop해 prefix에 추가한다 (괄호 내 연산자로 연산).
   4. 알고리즘이 끝나고 남은 스택 원소는 최상단부터 순차적으로 pop해 prefix에 추가한다.

 

사용한 자료구조 / 알고리즘

스택

 

풀이 코드

infix = input()
prefix = ''
stack = []

for ch in infix:  # 중위표기식의 각 원소에 대해
    if ch.isalpha():  # 알파벳이면 prefix에 곧바로 추가
        prefix += ch
    else:
        if ch == '(':
            stack.append(ch)
        elif ch in ('+', '-'):  # 가장 우선순위가 낮은 연산자
            while stack and stack[-1] != '(':  # 여는 괄호를 만나면 멈추고
                prefix += stack.pop()  # 그렇지 않으면 stack 원소를 prefix에 추가
            stack.append(ch)
        elif ch in ('/', '*'):
            # 동일 우선순위 연산자는 먼저 나오는 연산자가 우선
            while stack and stack[-1] in ('/', '*'):
                prefix += stack.pop()
            stack.append(ch)
        elif ch == ')':  # 닫는 괄호를 만나면
            while stack and stack[-1] != '(':  # 괄호 내 모든 연산자를 prefix에 추가
                prefix += stack.pop()
            stack.pop()

# 알고리즘이 끝나고 스택에 원소가 있으면 모두 prefix에 추가
while stack:
    prefix += stack.pop()

print(prefix)

 

시간 복잡도 분석

O(N).

 

스택의 삽입, 삭제 연산은 O(1)이다.

원소가 알파벳인 경우 삽입 연산만 수행하기에 시간복잡도는 O(N)이고, 원소가 연산자인 경우 삽입, 삭제를 한 번씩 수행해 O(2N)이지만, 계수를 제외한 알고리즘의 시간복잡도는 O(N)이다.

 

문제에서 중요한 부분

LIFO라는 특징이 있는 스택 자료구조를 통해 후위표기식을 만들 수 있음을 떠올려야 했다.

연산자 우선순위와 스택 원소 pop, push 조건의 연관성을 파악해야 했다.