[ch 06-4] 계산기 프로그램 구현_1(전위/중위/후위표기법 개념)

[구현하는 계산기 기능]

- '후위 표기법 변환 알고리즘'을 사용하여 구현

└ 중위 표기법 수식 방식으로 사용자에게 입력 받음 → 프로그램에서 후위 표기법 수식으로 변경 → 계산 및 출력

  ※ 이유: 연산자의 우선순위를 신경쓰지 않아도 되고, 소괄호도 처리할 필요가 없기 때문

[구현 시 중요한 부분]

- 소괄호를 파악하여 그 부분을 먼저 연산

- 연산자의 우선순위를 근거로 연산의 순위를 결정

[구현 시 제한사항]

- 수식을 이루는 피연산자는 한자리 숫자(0~9)로만 이뤄진다고 가정

[수식의 표기법]

※ 예) 5 + 2 / 7

1. 중위 표기법(infix notation): 5 + 2 / 7

- 피연산자 사이에 연산자가 존재하는 일반적인 표기법

2. 전위 표기법(prefix notation): + 5 / 2 7

- 각 피연산자 왼쪽에 연산자가 존재하는 표기법

3. 후위 표기법(postfix notation): 5 2 7 / +

- 피연산자 오른쪽에 연산자들이 존재하는 표기법

[중위 표기법과 전위/후위 표기법 수식의 차이점]

- 전위/후위 표기법으로 작성된 수식에는 '배치순서'를 근거로 한 연산순서의 정보가 존재

└ 연산자의 우선순위를 알 필요가 없으며, 소괄호에 대한 처리도 불필요

---

[중위 표기법 → 후위 표기법 변환 과정]

1. 소괄호가 없는 수식

- '사용자에게 입력 받은 수식'에서 맨 왼쪽부터 하나씩 처리

- 피연산자는 무조건 별도의 처리없이 비어있는 위치 중 가장 왼쪽에 배치

- 연산자는 전용 공간(스택)에서 잠시 저장

- 피연산자는 즉시 새로운 위치로 이동

- 연산자를 스택에 넣을 때 기존 연산자가 존재하면 정의한 연산자 우선순위에 따라 다르게 처리

  ※ 연산자 우선순위: '+' = '-' < '*' = '/'

  ※ 새로운 연산자는 우선순위 비교 시 스택에 있는 모든 연산자와 차례대로 1:1 비교

// 스택에 있던 기존 연산자의 우선순위가 '높을' 경우 or '같을' 경우

- 기존 연산자는 스택에서 빠져나와 변경된 수식에 배치

- 새로운 연산자는 스택에 저장

// 스택에 있던 기존 연산자의 우선순위가 '낮을' 경우

- 기존 연산자는 그대로인 상태에서 그 위에 새로운 연산자를 저장

- 계속해서 피연산자는 즉시 새로운 위치로 이동

- 수식에 더 이상 처리해야 할 데이터가 없으면 스택에 있던 연산자를 스택 추출 방식으로(마지막에 넣은 연산자가 먼저) 새로운 위치로 이동

[정리]

- 피연산자는 새로운 위치로 무조건 이동

- 연산자는 스택에 저장. 기존에 연산자가 들어가 있는 경우 우선순위를 비교하여 처리

- 사용자에게 입력 받은 수식에서 옮길 데이터가 더 이상 없을 경우 스택에 남아있던 연산자를 차례대로 이동

---

2. 소괄호가 있는 수식

- '사용자에게 입력 받은 수식'에서 맨 왼쪽부터 하나씩 처리

- 소괄호 '('는 스택에 저장

- 피연산자는 변경된 새로운 위치로 이동

- 연산자는 스택에 저장

  ※ 소괄호는 연산자 중에 우선순위가 가장 낮게 정의

- 피연산자는 변경된 새로운 위치로 이동

- '/' 연산자가 '-'연산자 보다 우선순위가 높으므로 '-' 다음으로 스택에 저장

- 피연산자는 변경된 새로운 위치로 이동

- 소괄호 ')'는 스택에 '(' 다음으로 저장된 모든 연산자들을 추출하여 변경된 수식의 위치로 이동하라는 명령을 나타냄

  ※ 소괄호 ')'는 스택에 저장되지 않음

- 추출 과정 중에 소괄호 '('가 조회되면 수식에 넣어지지 않고 삭제됨

- 연산자는 스택에 저장

- 피연산자는 변경된 새로운 위치로 이동

- 수식에 더 이상 처리해야 할 데이터가 없으면 스택에 있던 연산자를 스택 추출 방식으로 변경된 새로운 위치로 이동