Postfix Notation 계산하기

계산 방법

사용할 데이터와 자료구조

• postfix 방식으로 표기된 계산식 스트림

  • 의미 단위로 처리한다고 가정

  • 수와 연사자만 존재한다고 가정 (괄호는 postfix 표기법에서 필요 없음)

• 계산 결과를 담을 스택

알고리즘

1. 스트림에서 꺼낸 토큰이 수이면 스택에 push한다.

2. 스트림에서 꺼낸 토큰이 연산자이면 스택에서 수를 2개 pop하여 연산자에 해당하는 연산을 수행한다. 수행한 결과로 나온 수를 다시 스택에 push한다.

   1. 처음 pop한 수가 오른쪽 피연산자이고 나중에 pop한 수가 왼쪽 피연산자이다.

3. 스트림을 모두 처리했을때 스택에 남아있는 수가 계산 결과이다.

예시

연산자가 하나인 경우

# 문제

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]