문제
수식은 일반적으로 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을 넘지 않는다.
출력
첫째 줄에 후위 표기식으로 바뀐 식을 출력하시오
예제 입력 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/-
간단한 문제 설명
스택(stack) 을 사용하는 대표적인 문제다.
우선 연산자(+,-,/,*) 와 피연산자(문자 혹은 숫자. 이 문제에서는 문자) 로 구분하여 따로 생각한다.
피연산자인 경우에는, 출력할 문자열에 그냥 추가 하면된다.
연산자인 경우 약간 복잡한데,
- 여는 괄호( ’(’ ) 의 경우 stack에 추가할 것.
- stack이 비어있을 경우, 다음에 들어오는 기호는 추가할 것.
- stack이 비어있지 않을 경우, 현재 들어오는 기호의 우선순위 > stack의 top기호의 우선순위 가 될 때까지 stack에서 기호를 pop해서 문자열에 추가할 것.
- 닫는 괄호( ’)’ ) 의 경우 여는 괄호가 나올 때까지 그 사이의 기호를 pop해서 문자열에 추가할 것.
- 문자열을 다 순회하고 나서, stack에 남는 기호가 있다면, 맨 끝에 붙여서 출력할 것.
기호의 우선순위를 따지는 이유는, 중위연산식에서는 눈으로보고 우선순위대로 차례로 계산할 수 있지만 ( 괄호 → *,/ → +,-) 후위 연산식에서는 앞에서부터 차례로 계산하기 때문에 */ 가 +- 보다 앞서서 출력되어야 하기 때문이다.
내 코드는 다음과 같다.
1. append와 pop을 사용하는 방법
# 1918 후위표기식
stack = []
icp = {"+":1, "-":1, "*":2, "/":2, "(":3}
isp = {"+":1, "-":1, "*":2, "/":2, "(":0}
words = input()
postfix = ""
for word in words:
# 만약 피연산자이면 postfix에 추가하고
if word.isalpha():
postfix += word
# 연산자인 경우,
else:
# 만약 stack이 비었다면 push 한다.
if not stack:
stack.append(word)
# stack이 비지 않았다면,
else:
# 만약 닫는 괄호가 들어오면, 여는 괄호가 올 때까지 pop한다.
if word == ")":
top = stack[-1]
while top != "(":
postfix += stack.pop()
if stack:
top = stack[-1]
# 여는 괄호를 없애준다.
stack.pop()
# 다른 문자가 들어온다면,
else:
# stack의 top보다 우선순위보다 들어오는 단어의 우선순위가 크면 push 한다.
top = stack[-1]
if isp[top] < icp[word]:
stack.append(word)
# stack의 top의 우선순위보다 들어오는 우선순위가 같거나 낮으면,
else:
# 우선순위가 낮은게 나올 때까지 팝한다.
while len(stack)!=0 and isp[top] >= icp[word]:
postfix += stack.pop()
if stack:
top = stack[-1]
# 다 끝난 후에 append 해준다.
stack.append(word)
# 단어를 다 순회하고 나서 stack에 남아있는 문자를 다 더해준다.
while stack:
postfix += stack.pop()
print(postfix)2. top을 사용하는 방법 (더 빠르다.)
icp = {"+":1, "-":1, "*":2, "/":2, "(":3}
isp = {"+":1, "-":1, "*":2, "/":2, "(":0}
postfix = ""
top = -1
words = input()
n = len(words)
stack = [0]*n
for i in range(n):
# 만약 문자이면 postfix에 더한다
if words[i].isalpha():
postfix += words[i]
# 연산자이면
else:
# top = -1 이면(즉, 스택이 비어있으면)
if top == -1:
# stack에 push 한다.
top += 1
stack[top] = words[i]
# 그렇지 않으면 (즉, 스택이 비어있지 않으면)
else:
# 닫는 괄호가 들어오면, 여는괄호가 나올때까지 pop한다.
if words[i] == ")":
while stack[top] != "(":
postfix += stack[top]
top -= 1
# "(" 을 pop한다. (즉 top을 하나 낮춘다.)
top -= 1
else:
# icp(stack(top)) > isp(i)을 비교한다.
if isp[stack[top]] < icp[words[i]]:
# stack에 push 한다.
top += 1
stack[top] = words[i]
# icp(top) <= isp(i) 라면,
else:
# top = -1 이거나 icp(top) < isp(i)가 될때까지 pop 한다.
while top != -1 and isp[stack[top]] >= icp[words[i]]:
postfix += stack[top]
top -= 1
# push 한다.
top += 1
stack[top] = words[i]
# 반복문을 다 돌고 stack에 남아있는 것이 있다면
# postfix에 붙인다.
while top != -1:
postfix += stack[top]
top -= 1
print(postfix)Uploaded by N2T