열혈 자료구조 - 6-4. 스택을 활용한 계산기 프로그램 구현(1)

구현할 계산기의 성능

- 소괄호 및 연산자에 따라 연산의 우선순위를 파악하는 사칙연산 계산기

- ex) (3+4) * (4/7) + (7 + (9-5))

- 위 수식을 연산하는 알고리즘은 별도이지만 스택을 활용하고 있음

 

수식의 표기법

- 중위 표기법

    -> 우리가 현재 사용하는 표기법

    -> 피연산자 사이에 연산자를 중위(중간)에 배치

    -> 수식 내의 연산의 순서가 담겨있지 않음

    -> 5 + 2 / 7

- 전위 표기법

    -> 연산자가 피연산자들보다 앞에 있음

    -> 수식 내의 연산의 순서가 담겨 있음

    -> + 5 / 2 7

- 후위 표기법

    -> 연산자가 피연산자들보다 뒤에 있음

    -> 수식 내의 연산의 순서가 담겨 있음(소괄호가 필요 없음)

    -> 5 2 7 / +

    -> 나열되는 순서를 기준으로 연산의 순서가 정해짐(위 식으로 봤을 땐 나눗셈 먼저 다음으로 덧셈)

    -> 연산자 앞의 두 피연산자로 계산

- 전위나 후위 표기법의 계산기를 만드는 것이 상대적으로 더 쉬움

- 중위 표기법으로 수식을 받고 후위 표기법으로 변환하여 계산

 

중위 표기법을 후기 표기법으로 변환

- 소괄호가 없는 수식

    -> 왼쪽부터 변환될 수식으로 이동

    -> 연산자는 우선 따로 보관

    -> 연산자가 따로 저장되어 있는데 새로 옮길 연산자가 기존의 연산자보다 우선순위가 높으면 그 위에 저장

    -> 작은 경우에는 기존에 있는 연산자를 수식으로 저장 후 따로 저장

    -> 같은 경우에는 새로 옮길 연산자는 따로 저장된 연산자보다 우선순위가 낮기 때문에 기존의 연산자를 수식으로 옮기고 따로 저장

    -> 두 개 이상의 경우에는 가장 위에 있는 연산자부터 하나씩 비교해서 새로 옮길 것이 우선순위가 높을 때까지 기존의 연산자를 변경될 수식으로 옮김

    -> 이 연산자를 담는 구조에서 스택을 활용

    -> 마지막으로 연산자를 위에서부터 변경될 수식에 저장

- 소괄호가 있는 경우

    -> 소괄호 안에 있는 수식 먼저 위 처럼 원본 수식에서 변경될 수식으로 옮기고 나머지 연산을 다시 변경될 수식 뒤에 붙이듯이 옮김