BOJ 1918 후위 표기식
https://www.acmicpc.net/problem/1918
시간 2초, 메모리 128MB
input :
- 중위 표기식
- +, -, *, /, (, )
output :
- 후위 표기식으로 바뀐 식을 출력
조건 :
-
중위 표기식을 후위 표기식으로 바꾸는 방법
-
중위 표기식을 연산자의 우선순위에 따라 괄호로 묶어준다.
-
a+bc는 (a+(bc))의 식과 같게 된다.
-
그 다음에 안에 있는 괄호의 연산자 를 괄호 밖으로 꺼내게 되면 (a+bc)가 된다.
-
마지막으로 또 +를 괄호의 오른쪽으로 고치면 abc*+가 된다.
무슨 괄호를 직접 만들고 해야 하는 줄 알았다.
연산자의 우선순위에 따라 괄호로 묶는다는 것이 힌트인 것같다.
*, / 의 경우에는 다른 연산자들보다 우선적으로 계산되어야 한다. 그렇기에 다른 연산자들보다 우선순위를 크게 한다.
왜 우선순위를 크게 할까????
-
우린 어차피 이 문자열을 앞에서 부터 읽을 것이다. 그게 트리를 읽는 방식이니까.
그렇다면, 실제로 괄호를 만들지 않고 어떻게 판별을 할까. 우선 스택을 이용할 거다.
앞에서 부터 나오는 연산자들을 스택에 집어넣고 꺼낼 것이다. -
어떤 기준으로?
알파벳이 들어올 때는 관여를 할 필요가 없다,
if 'A' <= item <= 'Z':
ans.append(item)
연산자가 들어오는 경우를 따져야 하는데
현재 : '+'를 가지고 있다 이 때, 이미 temp배열에 '*'나 '/'가 들어있는 경우 이들의 연산이 우선이다. 이 것을 어떻게 확인 하냐.
각 연산자의 우선순위를 비교하는 것이다. 서로 비교를 해서 자기보다 작은 놈이 나올 때 까지 계속 끄집어내는 것이다.
그렇게 해서 임의의 괄호를 만들어주는 것이다.
operator = {"*":2, "/":2, "+":1, "-":1, "(":0}
else:
while len(temp) > 0 and operator[item] <= operator[temp[-1]]:
ans.append(temp.pop())
temp.append(item)
실제로 괄호가 입력되는 경우에는 그냥 '(' 의 우선순위를 가장 작게 해서 괄호보다 우선순위가 작은 게 없어서 다른 연산자들이 나오지 않도록 한다.
이렇게 하면 괄호 안의 연산자들 부터 계산을 할 수 있다.
elif item == '(':
temp.append(item)
elif item == ')':
while temp[-1] != '(':
ans.append(temp.pop())
temp.pop()
import sys
data = sys.stdin.readline().rstrip()
ans = []
temp = []
operator = {"*":2, "/":2, "+":1, "-":1, "(":0}
for item in data:
if 'A' <= item <= 'Z':
ans.append(item)
elif item == '(':
temp.append(item)
elif item == ')':
while temp[-1] != '(':
ans.append(temp.pop())
temp.pop()
else:
while len(temp) > 0 and operator[item] <= operator[temp[-1]]:
ans.append(temp.pop())
temp.append(item)
while temp:
ans.append(temp.pop())
print("".join(ans))
우선순위를 임의로 만들어 주고, while문을 사용해서 자기보다 우선순위가 작은 놈을 찾는 것이 가장 중요하다.
Author And Source
이 문제에 관하여(BOJ 1918 후위 표기식), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jsin2475/BOJ-1918-후위-표기식저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)