Stack을 이용하여 infix notation을 postfix notation으로 변경하기

변경 방법

사용할 데이터와 자료구조

• 원본 입력 스트림 -> "입력스트림"

• 스택 1개 -> "스택"

• 최종 결과를 담을 리스트 -> "결과리스트"

알고리즘

1. 사용자가 입력하는 수식을 의미 단위로 처리한다고 가정한다. (수, 연산자, 괄호 단위로 처리)

2. 공백 문자는 무시한다.

3. 사용자가 수를 입력한 경우 결과리스트에 넣는다.

4. 사용자가 연산자 ( $+, -, *, /$ )를 입력한 경우

   1. 스택이 비어있는 경우 스택에 push한다.

   2. 스택이 비어있지 않은 경우 pop하여 맨 뒤 토큰을 가져온다.

      1. 스택에서 뽑은 토큰이 사용자가 입력한 연산자와 같거나 높 계산 우선순위를 갖는 연산자이면 토큰을 결과리스트에 넣고 4번 과정을 다시 반복한다.

      2. 스택에서 뽑은 토큰이 사용자가 입력한 연산자보다 낮은 계산 우선순위를 갖는 연산자이면 토큰을 스택에 다시 push하고 사용자가 입력한 연산자를 스택에 push한다.

      3. 스택에서 뽑은 토큰이 여는 괄호이면 토큰을 스텍에 다시 push하고 사용자가 입력한 연산자를 스택에 push한다.

5. 사용자가 괄호를 입력한 경우

   1. 여는 괄호일 경우 스택에 push한다.

   2. 닫는 괄호일 경우 스택에서 닫는 괄호와 쌍을 이루는 여는 괄호가 나올때까지 토큰을 pop하여 결과리스트에 넣는다. 이때 사용자가 입력한 닫는 괄호와 스택에서 pop한 쌍을 이루는 여는 괄호는 결과리스트에 넣지 않고 버린다.

6. 입력스트림이 비워졌을 때 스택이 비어있지 않은 경우 스택의 모든 토큰을 하나씩 pop하여 결과리스트에 넣는다.

예시

연산자가 하나인 경우

# 문제

infix   : 2 + 3
postfix : 2 3 +

# 풀이 (순서대로 원본스트림, 스택, 결과리스트)

[2, +, 3]
[]
[]

[+, 3]
[]
[2]

[3]
[+]
[2]

[]
[2, 3]
[+]

[]
[2, 3, +]
[]

같은 계산 우선순위를 가진 연산자가 2개 이상 있는 경우

# 문제

infix   : 2 + 3 - 4
postfix : 2 3 + 4 -

# 풀이 (순서대로 원본스트림, 스택, 결과리스트)

[2, +, 3, -, 4]
[]
[]

[+, 3, -, 4]
[]
[2]

[3, -, 4]
[+]
[2]

[-, 4]
[+]
[2, 3]

[4]
[-]
[2, 3, +]

[]
[-]
[2, 3, +, 4]

[]
[]
[2, 3, +, 4, -]

# 문제

infix   : 3 * 4 / 5
postfix : 3 4 * 5 /

# 풀이 (순서대로 원본스트림, 스택, 결과리스트)

[3, *, 4, /, 5]
[]
[]

[*, 4, /, 5]
[]
[3]

[4, /, 5]
[*]
[3]

[/, 5]
[*]
[3, 4]

[5]
[/]
[3, 4, *]

[]
[/]
[3, 4, *, 5]

[]
[]
[3, 4, *, 5, /]

높은 계산 우선순위를 가진 연산자가 먼저 오고 낮은 계산 우선순위를 가진 연산자가 나중에 오는 경우

# 문제

infix   : 2 * 3 + 4
postfix : 2 3 * 4 +

# 풀이 (순서대로 원본스트림, 스택, 결과리스트)

[2, *, 3, +, 4]
[]
[]

[*, 3, +, 4]
[]
[2]

[3, +, 4]
[*]
[2]

[+, 4]
[*]
[2, 3]

[4]
[+]
[2, 3, *]

[]
[+]
[2, 3, *, 4]

[]
[]
[2, 3, *, 4, +]

낮은 계산 우선순위를 가진 연산자가 먼저 오고 높은 계산 우선순위를 가진 연산자가 나중에 오는 경우

# 문제

infix   : 2 + 3 * 4
postfix : 2 3 4 * +

# 풀이 (순서대로 원본스트림, 스택, 결과리스트)

[2, +, 3, *, 4]
[]
[]

[+, 3, *, 4]
[]
[2]

[3, *, 4]
[+]
[2]

[*, 4]
[+]
[2, 3]

[4]
[+, *]
[2, 3]

[]
[+, *]
[2, 3, 4]

[]
[]
[2, 3, 4, *, +]

다른 계산 우선순위를 가진 연산자가 2개 이상 있는 경우

# 문제

infix   : 2 + 3 * 4 - 5
postfix : 2 3 4 * + 5 -

# 풀이 (순서대로 원본스트림, 스택, 결과리스트)

[2, +, 3, *, 4, -, 5]
[]
[]
    
[+, 3, *, 4, -, 5]
[]
[2]
    
[3, *, 4, -, 5]
[+]
[2]

[*, 4, -, 5]
[+]
[2, 3]

[4, -, 5]
[+, *]
[2, 3]

[-, 5]
[+, *]
[2, 3, 4]

[5]
[-]
[2, 3, 4, *, +]

[]
[-]
[2, 3, 4, *, +, 5]

[]
[]
[2, 3, 4, *, +, 5, -]

# 문제

infix   : 2 + 3 * 4 / 5 - 6
postfix : 2 3 4 * 5 / + 6 -

# 풀이 (순서대로 원본스트림, 스택, 결과리스트)

[2, +, 3, *, 4, /, 5, -, 6]
[]
[]

[+, 3, *, 4, /, 5, -, 6]
[]
[2]

[3, *, 4, /, 5, -, 6]
[+]
[2]

[*, 4, /, 5, -, 6]
[+]
[2, 3]

[4, /, 5, -, 6]
[+, *]
[2, 3]

[/, 5, -, 6]
[+, *]
[2, 3, 4]

[5, -, 6]
[+, /]
[2, 3, 4, *]

[-, 6]
[+, /]
[2, 3, 4, *, 5]

[6]
[-]
[2, 3, 4, *, 5, /, +]

[]
[-]
[2, 3, 4, *, 5, /, +, 6]

[]
[]
[2, 3, 4, *, 5, /, +, 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 * +

# 풀이 (순서대로 입력스트림, 스택, 결과리스트)

[(, 7, +, 3, -, 6, ), +, 5, *, (, 4, /, 2, +, 1, -, 9, ), +, 13, /, 5, *, 21]
[]
[]

[7, +, 3, -, 6, ), +, 5, *, (, 4, /, 2, +, 1, -, 9, ), +, 13, /, 5, *, 21]
[(]
[]

[+, 3, -, 6, ), +, 5, *, (, 4, /, 2, +, 1, -, 9, ), +, 13, /, 5, *, 21]
[(]
[7]

[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]
[(, -]
[7, 3, +]

[), +, 5, *, (, 4, /, 2, +, 1, -, 9, ), +, 13, /, 5, *, 21]
[(, -]
[7, 3, +, 6]

[+, 5, *, (, 4, /, 2, +, 1, -, 9, ), +, 13, /, 5, *, 21]
[]
[7, 3, +, 6, -]

[5, *, (, 4, /, 2, +, 1, -, 9, ), +, 13, /, 5, *, 21]
[+]
[7, 3, +, 6, -]

[*, (, 4, /, 2, +, 1, -, 9, ), +, 13, /, 5, *, 21]
[+]
[7, 3, +, 6, -, 5]

[(, 4, /, 2, +, 1, -, 9, ), +, 13, /, 5, *, 21]
[+, *]
[7, 3, +, 6, -, 5]

[4, /, 2, +, 1, -, 9, ), +, 13, /, 5, *, 21]
[+, *, (]
[7, 3, +, 6, -, 5]

[/, 2, +, 1, -, 9, ), +, 13, /, 5, *, 21]
[+, *, (]
[7, 3, +, 6, -, 5, 4]

[2, +, 1, -, 9, ), +, 13, /, 5, *, 21]
[+, *, (, /]
[7, 3, +, 6, -, 5, 4]

[+, 1, -, 9, ), +, 13, /, 5, *, 21]
[+, *, (, /]
[7, 3, +, 6, -, 5, 4, 2]

[1, -, 9, ), +, 13, /, 5, *, 21]
[+, *, (, +]
[7, 3, +, 6, -, 5, 4, 2, /]

[-, 9, ), +, 13, /, 5, *, 21]
[+, *, (, +]
[7, 3, +, 6, -, 5, 4, 2, /, 1]

[9, ), +, 13, /, 5, *, 21]
[+, *, (, -]
[7, 3, +, 6, -, 5, 4, 2, /, 1, +]

[), +, 13, /, 5, *, 21]
[+, *, (, -]
[7, 3, +, 6, -, 5, 4, 2, /, 1, +, 9]

[+, 13, /, 5, *, 21]
[+, *]
[7, 3, +, 6, -, 5, 4, 2, /, 1, +, 9, -]

[13, /, 5, *, 21]
[+]
[7, 3, +, 6, -, 5, 4, 2, /, 1, +, 9, -, *, +]

[/, 5, *, 21]
[+]
[7, 3, +, 6, -, 5, 4, 2, /, 1, +, 9, -, *, +, 13]

[5, *, 21]
[+, /]
[7, 3, +, 6, -, 5, 4, 2, /, 1, +, 9, -, *, +, 13]

[*, 21]
[+, /]
[7, 3, +, 6, -, 5, 4, 2, /, 1, +, 9, -, *, +, 13, 5]

[21]
[+, *]
[7, 3, +, 6, -, 5, 4, 2, /, 1, +, 9, -, *, +, 13, 5, /]
 
[]
[+, *]
[7, 3, +, 6, -, 5, 4, 2, /, 1, +, 9, -, *, +, 13, 5, /, 21]

[]
[]
[7, 3, +, 6, -, 5, 4, 2, /, 1, +, 9, -, *, +, 13, 5, /, 21, *, +]

# 문제

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 / + -

# 풀이 (순서대로 입력스트림, 스택, 결과리스트)

[1, *, 2, -, 3, /, [, {, (, 4, +, 5, ), *, 6, }, +, 7, /, 8, ], -, (, 9, +, (, 12, -, 15, ), /, 5, )]
[]
[]

[*, 2, -, 3, /, [, {, (, 4, +, 5, ), *, 6, }, +, 7, /, 8, ], -, (, 9, +, (, 12, -, 15, ), /, 5, )]
[]
[1]

[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, )]
[-]
[1, 2, *]

[/, [, {, (, 4, +, 5, ), *, 6, }, +, 7, /, 8, ], -, (, 9, +, (, 12, -, 15, ), /, 5, )]
[-]
[1, 2, *, 3]

[[, {, (, 4, +, 5, ), *, 6, }, +, 7, /, 8, ], -, (, 9, +, (, 12, -, 15, ), /, 5, )]
[-, /]
[1, 2, *, 3]

[{, (, 4, +, 5, ), *, 6, }, +, 7, /, 8, ], -, (, 9, +, (, 12, -, 15, ), /, 5, )]
[-, /, []
[1, 2, *, 3]

[(, 4, +, 5, ), *, 6, }, +, 7, /, 8, ], -, (, 9, +, (, 12, -, 15, ), /, 5, )]
[-, /, [, {]
[1, 2, *, 3]

[4, +, 5, ), *, 6, }, +, 7, /, 8, ], -, (, 9, +, (, 12, -, 15, ), /, 5, )]
[-, /, [, {, (]
[1, 2, *, 3]

[+, 5, ), *, 6, }, +, 7, /, 8, ], -, (, 9, +, (, 12, -, 15, ), /, 5, )]
[-, /, [, {, (]
[1, 2, *, 3, 4]

[5, ), *, 6, }, +, 7, /, 8, ], -, (, 9, +, (, 12, -, 15, ), /, 5, )]
[-, /, [, {, (, +]
[1, 2, *, 3, 4]

[), *, 6, }, +, 7, /, 8, ], -, (, 9, +, (, 12, -, 15, ), /, 5, )]
[-, /, [, {, (, +]
[1, 2, *, 3, 4, 5]

[*, 6, }, +, 7, /, 8, ], -, (, 9, +, (, 12, -, 15, ), /, 5, )]
[-, /, [, {]
[1, 2, *, 3, 4, 5, +]

[6, }, +, 7, /, 8, ], -, (, 9, +, (, 12, -, 15, ), /, 5, )]
[-, /, [, {, *]
[1, 2, *, 3, 4, 5, +]

[}, +, 7, /, 8, ], -, (, 9, +, (, 12, -, 15, ), /, 5, )]
[-, /, [, {, *]
[1, 2, *, 3, 4, 5, +, 6]

[+, 7, /, 8, ], -, (, 9, +, (, 12, -, 15, ), /, 5, )]
[-, /, []
[1, 2, *, 3, 4, 5, +, 6, *]

[7, /, 8, ], -, (, 9, +, (, 12, -, 15, ), /, 5, )]
[-, /, [, +]
[1, 2, *, 3, 4, 5, +, 6, *]

[/, 8, ], -, (, 9, +, (, 12, -, 15, ), /, 5, )]
[-, /, [, +]
[1, 2, *, 3, 4, 5, +, 6, *, 7]

[8, ], -, (, 9, +, (, 12, -, 15, ), /, 5, )]
[-, /, [, +, /]
[1, 2, *, 3, 4, 5, +, 6, *, 7]

[], -, (, 9, +, (, 12, -, 15, ), /, 5, )]
[-, /, [, +, /]
[1, 2, *, 3, 4, 5, +, 6, *, 7, 8]

[-, (, 9, +, (, 12, -, 15, ), /, 5, )]
[-, /]
[1, 2, *, 3, 4, 5, +, 6, *, 7, 8, /, +]

[(, 9, +, (, 12, -, 15, ), /, 5, )]
[-]
[1, 2, *, 3, 4, 5, +, 6, *, 7, 8, /, +, /, -]

[9, +, (, 12, -, 15, ), /, 5, )]
[-, (]
[1, 2, *, 3, 4, 5, +, 6, *, 7, 8, /, +, /, -]
 
[+, (, 12, -, 15, ), /, 5, )]
[-, (]
[1, 2, *, 3, 4, 5, +, 6, *, 7, 8, /, +, /, -, 9]

[(, 12, -, 15, ), /, 5, )]
[-, (, +]
[1, 2, *, 3, 4, 5, +, 6, *, 7, 8, /, +, /, -, 9]

[12, -, 15, ), /, 5, )]
[-, (, +, (]
[1, 2, *, 3, 4, 5, +, 6, *, 7, 8, /, +, /, -, 9]

[-, 15, ), /, 5, )]
[-, (, +, (]
[1, 2, *, 3, 4, 5, +, 6, *, 7, 8, /, +, /, -, 9, 12]

[15, ), /, 5, )]
[-, (, +, (, -]
[1, 2, *, 3, 4, 5, +, 6, *, 7, 8, /, +, /, -, 9, 12]

[), /, 5, )]
[-, (, +, (, -]
[1, 2, *, 3, 4, 5, +, 6, *, 7, 8, /, +, /, -, 9, 12, 15]

[/, 5, )]
[-, (, +]
[1, 2, *, 3, 4, 5, +, 6, *, 7, 8, /, +, /, -, 9, 12, 15, -]

[5, )]
[-, (, +, /]
[1, 2, *, 3, 4, 5, +, 6, *, 7, 8, /, +, /, -, 9, 12, 15, -]

[)]
[-, (, +, /]
[1, 2, *, 3, 4, 5, +, 6, *, 7, 8, /, +, /, -, 9, 12, 15, -, 5]

[]
[-]
[1, 2, *, 3, 4, 5, +, 6, *, 7, 8, /, +, /, -, 9, 12, 15, -, 5, /, +]

[]
[]
[1, 2, *, 3, 4, 5, +, 6, *, 7, 8, /, +, /, -, 9, 12, 15, -, 5, /, +, -]