계산 방법
사용할 데이터와 자료구조
postfix 방식으로 표기된 계산식 스트림
수와 연사자만 존재한다고 가정 (괄호는 postfix 표기법에서 필요 없음)
알고리즘
스트림에서 꺼낸 토큰이 수이면 스택에 push한다.
스트림에서 꺼낸 토큰이 연산자이면 스택에서 수를 2개 pop하여 연산자에 해당하는 연산을 수행한다. 수행한 결과로 나온 수를 다시 스택에 push한다.
처음 pop한 수가 오른쪽 피연산자이고 나중에 pop한 수가 왼쪽 피연산자이다.
스트림을 모두 처리했을때 스택에 남아있는 수가 계산 결과이다.
예시
연산자가 하나인 경우
# 문제
infix : 2 + 3
postfix : 2 3 +
result : 5
# 풀이 (순서대로 스트림, 스택)
[2, 3, +]
[]
[3, +]
[2]
[+]
[2, 3]
[]
[5]
같은 계산 우선순위를 가진 연산자가 2개 이상 있는 경우
# 문제
infix : 2 + 3 - 4
postfix : 2 3 + 4 -
result : 1
# 풀이 (순서대로 스트림, 스택)
[2, 3, +, 4, -]
[]
[3, +, 4, -]
[2]
[+, 4, -]
[2, 3]
[4, -]
[5]
[-]
[5, 4]
[]
[1]
# 문제
infix : 3 * 4 / 5
postfix : 3 4 * 5 /
result : 2.4
# 풀이 (순서대로 스트림, 스택)
[3, 4, *, 5, /]
[]
[4, *, 5, /]
[3]
[*, 5, /]
[3, 4]
[5, /]
[12]
[/]
[12, 5]
[]
[2.4]
높은 계산 우선순위를 가진 연산자가 먼저 오고 낮은 계산 우선순위를 가진 연산자가 나중에 오는 경우
# 문제
infix : 2 * 3 + 4
postfix : 2 3 * 4 +
result : 10
# 풀이 (순서대로 스트림, 스택)
[2, 3, *, 4, +]
[]
[3, *, 4, +]
[2]
[*, 4, +]
[2, 3]
[4, +]
[6]
[+]
[6, 4]
[]
[10]
낮은 계산 우선순위를 가진 연산자가 먼저 오고 높은 계산 우선순위를 가진 연산자가 나중에 오는 경우
# 문제
infix : 2 + 3 * 4
postfix : 2 3 4 * +
result : 14
# 풀이 (순서대로 스트림, 스택)
[2, 3, 4, *, +]
[]
[3, 4, *, +]
[2]
[4, *, +]
[2, 3]
[*, +]
[2, 3, 4]
[+]
[2, 12]
[]
[14]
다른 계산 우선순위를 가진 연산자가 2개 이상 있는 경우
# 문제
infix : 2 + 3 * 4 - 5
postfix : 2 3 4 * + 5 -
result : 9
# 풀이 (순서대로 스트림, 스택)
[2, 3, 4, *, +, 5, -]
[]
[3, 4, *, +, 5, -]
[2]
[4, *, +, 5, -]
[2, 3]
[*, +, 5, -]
[2, 3, 4]
[+, 5, -]
[2, 12]
[5, -]
[14]
[-]
[14, 5]
[]
[9]
# 문제
infix : 2 + 3 * 4 / 5 - 6
postfix : 2 3 4 * 5 / + 6 -
result : -1.6
# 풀이 (순서대로 스트림, 스택)
[2, 3, 4, *, 5, /, +, 6, -]
[]
[3, 4, *, 5, /, +, 6, -]
[2]
[4, *, 5, /, +, 6, -]
[2, 3]
[*, 5, /, +, 6, -]
[2, 3, 4]
[5, /, +, 6, -]
[2, 12]
[/, +, 6, -]
[2, 12, 5]
[+, 6, -]
[2, 2.4]
[6, -]
[4.4]
[-]
[4.4, 6]
[]
[-1.6]
괄호가 포함된 복잡한 식의 경우
# 문제
infix : (7 + 3 - 6) + 5 * (4 / 2 + 1 - 9) + 13 / 5 * 21
postfix : 7 3 + 6 - 5 4 2 / 1 + 9 - * + 13 5 / 21 * +
result : 28.6
# 풀이 (순서대로 스트림, 스택)
[7, 3, +, 6, -, 5, 4, 2, /, 1, +, 9, -, *, +, 13, 5, /, 21, *, +]
[]
[3, +, 6, -, 5, 4, 2, /, 1, +, 9, -, *, +, 13, 5, /, 21, *, +]
[7]
[+, 6, -, 5, 4, 2, /, 1, +, 9, -, *, +, 13, 5, /, 21, *, +]
[7, 3]
[6, -, 5, 4, 2, /, 1, +, 9, -, *, +, 13, 5, /, 21, *, +]
[10]
[-, 5, 4, 2, /, 1, +, 9, -, *, +, 13, 5, /, 21, *, +]
[10, 6]
[5, 4, 2, /, 1, +, 9, -, *, +, 13, 5, /, 21, *, +]
[4]
[4, 2, /, 1, +, 9, -, *, +, 13, 5, /, 21, *, +]
[4, 5]
[2, /, 1, +, 9, -, *, +, 13, 5, /, 21, *, +]
[4, 5, 4]
[/, 1, +, 9, -, *, +, 13, 5, /, 21, *, +]
[4, 5, 4, 2]
[1, +, 9, -, *, +, 13, 5, /, 21, *, +]
[4, 5, 2]
[+, 9, -, *, +, 13, 5, /, 21, *, +]
[4, 5, 2, 1]
[9, -, *, +, 13, 5, /, 21, *, +]
[4, 5, 3]
[-, *, +, 13, 5, /, 21, *, +]
[4, 5, 3, 9]
[*, +, 13, 5, /, 21, *, +]
[4, 5, -6]
[+, 13, 5, /, 21, *, +]
[4, -30]
[13, 5, /, 21, *, +]
[-26]
[5, /, 21, *, +]
[-26, 13]
[/, 21, *, +]
[-26, 13, 5]
[21, *, +]
[-26, 2.6]
[*, +]
[-26, 2.6, 21]
[+]
[-26, 54.6]
[]
[28.6]
# 문제
infix : 1 * 2 - 3 * [{(4 + 5) * 6} + 7 * 8] - (9 + (12 - 15) * 5)
postfix : 1 2 * 3 4 5 + 6 * 7 8 * + * - 9 12 15 - 5 * + -
result : -322
# 풀이 (순서대로 스트림, 스택)
[1, 2, *, 3, 4, 5, +, 6, *, 7, 8, *, +, *, -, 9, 12, 15, -, 5, *, +, -]
[]
[2, *, 3, 4, 5, +, 6, *, 7, 8, *, +, *, -, 9, 12, 15, -, 5, *, +, -]
[1]
[*, 3, 4, 5, +, 6, *, 7, 8, *, +, *, -, 9, 12, 15, -, 5, *, +, -]
[1, 2]
[3, 4, 5, +, 6, *, 7, 8, *, +, *, -, 9, 12, 15, -, 5, *, +, -]
[2]
[4, 5, +, 6, *, 7, 8, *, +, *, -, 9, 12, 15, -, 5, *, +, -]
[2, 3]
[5, +, 6, *, 7, 8, *, +, *, -, 9, 12, 15, -, 5, *, +, -]
[2, 3, 4]
[+, 6, *, 7, 8, *, +, *, -, 9, 12, 15, -, 5, *, +, -]
[2, 3, 4, 5]
[6, *, 7, 8, *, +, *, -, 9, 12, 15, -, 5, *, +, -]
[2, 3, 9]
[*, 7, 8, *, +, *, -, 9, 12, 15, -, 5, *, +, -]
[2, 3, 9, 6]
[7, 8, *, +, *, -, 9, 12, 15, -, 5, *, +, -]
[2, 3, 54]
[8, *, +, *, -, 9, 12, 15, -, 5, *, +, -]
[2, 3, 54, 7]
[*, +, *, -, 9, 12, 15, -, 5, *, +, -]
[2, 3, 54, 7, 8]
[+, *, -, 9, 12, 15, -, 5, *, +, -]
[2, 3, 54, 56]
[*, -, 9, 12, 15, -, 5, *, +, -]
[2, 3, 110]
[-, 9, 12, 15, -, 5, *, +, -]
[2, 330]
[9, 12, 15, -, 5, *, +, -]
[-328]
[12, 15, -, 5, *, +, -]
[-328, 9]
[15, -, 5, *, +, -]
[-328, 9, 12]
[-, 5, *, +, -]
[-328, 9, 12, 15]
[5, *, +, -]
[-328, 9, -3]
[*, +, -]
[-328, 9, -3, 5]
[+, -]
[-328, 9, -15]
[-]
[-328, -6]
[]
[-322]