문제링크
https://school.programmers.co.kr/learn/courses/30/lessons/67257
접근
expression의 길이가 100 이하인 문자열이라 시간에 대한 걱정은 크게 하지 않았다.
연산식을 계산할 때 스택 자료구조를 사용하면 좋을 것이라 생각했고, 중위표기법을 후위표기법으로 바꿔주면 된다고 판단하였다.
풀이
연산자의 종류는 +, -, * 세가지 뿐이고, 괄호도 없어서 연산자의 우선순위만 결정하면 풀리는 문제이다.
연산자가 세개가 주어졌으므로 가능한 연산자 우선순위 조합은 3!, 즉 6가지이고 이를 미리 딕셔너리로 만들어놓았다.
priorities = [
{'+':3, '-':2, '*':1},
{'+':3, '*':2, '-':1},
{'-':3, '+':2, '*':1},
{'-':3, '*':2, '+':1},
{'*':3, '+':2, '-':1},
{'*':3, '-':2, '+':1},
]그리고 String 타입으로 주어진 expression을 연산하기 편하게끔 리스트 형태로 바꿨다.
이후 각 우선순위에 따른 결과값을 구하는 함수 cal()을 호출한다.
exp_li = [] # 식을 리스트 형태로 바꿀 것
prev = 0
for i in range(len(expression)):
if expression[i] in "*+-":
exp_li.append(int(expression[prev:i]))
exp_li.append(expression[i])
prev = i+1
exp_li.append(int(expression[prev:]))
for pri in priorities: # 우선순위별 최대값
answer = max(answer, abs(cal(exp_li,pri)))cal(exp, pri)
식의 값을 우선순위에 따라 계산해주는 함수이다.
def cal(exp, pri):
post_exp = postfix(exp,pri) # 중위연산식을 후위연산식으로 바꿔줌
st = []
for el in post_exp:
if type(el) == int:
st.append(el)
else:
b = st.pop()
a = st.pop()
st.append(eval(str(a)+el+str(b)))
return st[0]전제는 후위연산식으로 된 연산식을 필요로 한다는 점이다.
계산 과정은 그냥 후위연산식을 계산하는 방식으로 구현했다
후위연산식 계산 방식
1. 후위연산식의 요소(피연산자와 연산자)를 하나씩 검증
2. 만약 숫자(피연산자)면 스택에 바로 넣음
3. 만약 연산자면 스택에 있는 두 피연산자를 꺼내고 계산된 값을 다시 스택에 넣음
4. 1~3 반복후 맨 마지막에 스택에 남은 값이 최종 결과값임
postfix(exp, pri)
이번에는 중위연산식을 후위연산식으로 바꿔주는 함수이다
def postfix(exp,pri):
result, st = [], []
for el in exp:
if type(el) == int: # 숫자면 곧바로 result에 넣음
result.append(el)
else: # 연산자면
while st and pri[el] <= pri[st[-1]] : # 지금 뽑은거보다 우선순위 높은거 다 뽑음
result.append(st.pop())
st.append(el) # 지금 뽑은거 스택에 넣어줌
while st: # 스택에 남은 연산자 다 붙임
result.append(st.pop())
return result- 원래는 괄호에 대한 처리도 해줘야하지만, 이 문제에서 괄호가 나오지 않으므로 고려하지 않는다.
중위연산식을 후위연산식으로 바꾸는 과정은 다음과 같다
중위연산식 -> 후위연산식
1. 중위연산식의 요소(피연산자와 연산자)를 하나씩 검증
2. 만약 숫자(피연산자)면result에 바로 넣음 (result가 곧 후위연산식임)
3. 만약 연산자면 스택에 넣지만, 바로 넣지 않고 우선순위를 따져본다. 지금 새로 뽑은 연산자el이상의 우선순위를 가진 연산자가 스택의 맨 위에 있으면 이를 전부result에 넣어줌
4. 1~3을 반복하고, 마지막에 스택에 남은 연산자를 전부result에 붙여준다
정답코드
def postfix(exp,pri):
result, st = [], []
for el in exp:
if type(el) == int: # 숫자면 곧바로 result에 넣음
result.append(el)
else: # 연산자면
while st and pri[el] <= pri[st[-1]] : # 지금 뽑은거보다 우선순위 높은거 다 뽑음
result.append(st.pop())
st.append(el) # 지금 뽑은거 스택에 넣어줌
while st: # 스택에 남은 연산자 다 붙임
result.append(st.pop())
return result
def cal(exp, pri):
post_exp = postfix(exp,pri) # 중위연산식을 후위연산식으로 바꿔줌
st = []
for el in post_exp:
if type(el) == int:
st.append(el)
else:
b = st.pop()
a = st.pop()
st.append(eval(str(a)+el+str(b)))
return st[0]
def solution(expression):
answer = 0
priorities = [
{'+':3, '-':2, '*':1},
{'+':3, '*':2, '-':1},
{'-':3, '+':2, '*':1},
{'-':3, '*':2, '+':1},
{'*':3, '+':2, '-':1},
{'*':3, '-':2, '+':1},
]
exp_li = [] # 식을 리스트 형태로 바꿀 것
prev = 0
for i in range(len(expression)):
if expression[i] in "*+-":
exp_li.append(int(expression[prev:i]))
exp_li.append(expression[i])
prev = i+1
exp_li.append(int(expression[prev:]))
for pri in priorities:
answer = max(answer, abs(cal(exp_li,pri)))
return answer- 참고로 eval()은 원래 사용을 지양해야하는 것으로 알고있는데, 귀찮아서 그냥 썼다... 굳이 바꾸자면 각 연산자별로 조건을 달면 될 것 같다
