수식은 일반적으로 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를 완전하게 괄호로 묶고 연산자를 이동시킬 장소를 표시하면 다음과 같이 된다.
이러한 사실을 알고 중위 표기식이 주어졌을 때 후위 표기식으로 고치는 프로그램을 작성하시오
입력 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 알파벳 대문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 수식은 주어지지 않는다. 표기식은 알파벳 대문자와 +, -, *, /, (, )로만 이루어져 있으며, 길이는 100을 넘지 않는다.
출력 첫째 줄에 후위 표기식으로 바뀐 식을 출력하시오
📝 문제 접근 방법
아이디어
중위 표기식에서 연산자는 우선순위에 따라 스택에 넣고 피연산자는 바로 출력하여 후위 표기식을 생성합니다.
스택을 사용한 연산자 관리
피연산자는 위치를 변경할 필요가 없기 때문에 중위 표기식에서 등장하는 순서 그대로 후위 표기식에 추가합니다.
연산자를 만나면 스택을 활용해 우선순위를 관리하여 출력 순서를 결정합니다.
스택에 이미 있는 연산자와 현재 연산자의 우선순위를 비교합니다. 현재 연산자가 스택 상단의 연산자보다 우선순위가 낮거나 같다면, 스택 상단의 연산자를 먼저 출력합니다.
예를 들어, +나 - 연산자를 만났을 때, 스택에 *나 /가 있다면 이를 먼저 꺼내서 후위 표기식에 추가합니다. (왜냐하면 *와 /가 더 높은 우선순위이기 때문입니다.)
모든 비교가 끝나고 나면, 현재 연산자는 자신보다 높은 우선순위의 연산자들을 모두 꺼낸 후 스택에 넣습니다.
괄호 처리
여는 괄호 (는 특별한 경우로, 연산자 우선순위와 상관없이 무조건 스택에 넣습니다. 이렇게 하면 이후의 연산자들이 괄호 안에 있는 동안만 우선순위에 따라 처리됩니다.
닫는 괄호 )를 만나면 스택에서 여는 괄호 (가 나올 때까지 모든 연산자를 스택에서 꺼내어 후위 표기식에 추가합니다.
괄호는 후위 표기식에 나타나지 않으므로, 여는 괄호 (는 꺼내기만 하고 출력하지 않습니다.
식의 끝에서 남은 연산자 출력
중위 표기식의 끝에 도달하면 스택에 남아 있는 모든 연산자를 차례로 후위 표기식에 추가합니다.
이때 괄호는 이미 모두 처리된 상태이므로, 스택에 남아 있는 것은 연산자뿐이며 이를 차례대로 출력하여 후위 표기식을 완성합니다.
예제
A + B * C - D / E
👩💻 나의 답안
import sys
input = sys.stdin.readline
expression = list(input().strip())
op = []
for char in expression:
if char.isalpha():
print(char, end="")
else:
if char == "(":
op.append(char)
elif char == ")":
while op and op[-1] != "(":
print(op.pop(), end="")
op.pop()
elif char in "*/":
while op and op[-1] in "*/":
print(op.pop(), end="")
op.append(char)
elif char in "+-":
while op and op[-1] != "(":
print(op.pop(), end="")
op.append(char)
while op:
print(op.pop(), end="")
