[백준] #1918 후위 표기식(python)

📌문제

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

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

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

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

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

결과: ABC*+DE/-

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

입력

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

출력

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

예제 입력1

A*(B+C)

예제 출력1

ABC+*

예제 입력2

A+B

예제 출력2

AB+

예제 입력3

A+B*C

예제 출력3

ABC*+

예제 입력4

A+B*C-D/E

예제 출력4

ABC*+DE/-

백준 1918번 문제

💡Idea

중위 표기식을 후위 표기식으로 바꾸는 방법만 알면 쉽게 풀 수 있는 문제입니다.

Stack을 사용하여 중위 표기식을 후위 표기식으로 바꾸어 봅시다!

1. 피연산자가 들어오면, 출력한다.
2. 연산자가 들어오면, 스택에서 자신보다 같거나 높은 우선순위를 가지는 연산자들을 pop하여 출력한 뒤 자신을 스택에 push한다.
3. 여는 괄호 (가 들어오면, 스택에 push한다.
4. 닫는 괄호 )가 들어오면, 스택에서 여는 괄호 (가 나올 때까지 pop하여 출력한다.
5. 수식을 모두 확인했다면, 스택에 남아있는 것들을 모두 pop하여 출력한다.

💻코드

• ⏰ 시간 : 40 ms / 메모리 : 30616 KB

import sys

expressions = sys.stdin.readline().strip()
stack = []
op = {'+': ['+', '-', '*', '/'], '-': ['+', '-', '*', '/'], '*': ['*', '/'], '/': ['*', '/']}

for ex in expressions:
    if ex.isalpha():
        print(ex, end='')
    elif ex == '(':
        stack.append(ex)
    elif ex == ')':
        tmp = stack.pop()
        while tmp != '(':
            print(tmp, end='')
            tmp = stack.pop()
    else:
        while stack and stack[-1] in op[ex]:
            print(stack.pop(), end='')
        stack.append(ex)
        
while stack:
    print(stack.pop(), end='')

📝코드 설명

변수

• stack : 스택
• op : key보다 높은 우선순위를 가지는 연산자들을 value로 가지는 딕셔너리

수식의 연산자와 피연산자들을 하나씩 확인하며, 아래와 같은 과정을 실행합니다.

1. ex가 알파벳(피연산자)인 경우 : 출력
2. ex가 여는 괄호 (인 경우 : stack에 push
3. ex가 닫는 괄호 )인 경우 : stack에서 여는 괄호 (를 만날 때까지 pop 하여 출력
4. ex가 괄호 외 연산자인 경우 : stack에서 해당 연산자와 같거나 높은 우선순위를 pop 하여 출력

👇 연산자 간 우선순위를 파악하는 또 다른 좋은 방법을 발견하여 이것도 함께 정리해보려고 합니다!

priority_map = {'+': 0, '-': 0, '*': 1, '/': 1, '(': -1}

위 코드의 op에 대응되는 딕셔너리로, {연산자 : 우선순위}의 값을 가집니다.

그러면 각 연산자에 대응되는 숫자의 대소 비교를 통해, 4번 과정의 연산자 간 우선순위 비교를 쉽게 할 수 있습니다.

Reference

중위 표기법을 후위 표기법으로 변환후 계산하기