Postfix Notation 계산하기
계산 방법
사용할 데이터와 자료구조
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]
Last updated