자료구조 4-1 링크드리스트스택을 활용한 계산기

링크드리스트스택을 이용한 계산기를 만들기 전에, 설명해야 할 개념이 있다. 

바로, 중위표기식과 후위표기식이다. 

중위표기식은 우리가 보통 사용하는 표기식이다 

1+2 처럼 피연산자 사이에 연산자가 위치하는 방식이다.

반면, 후위표기식은, 연산자가 피연산자 뒤에 나타난다. 12+처럼 말이다.

 

후위표기식을 계산하는 법은 다음과 같다.

1. 숫자를 순서대로 스택에 삽입한다 

2. 연산자가 나오면 스택의 피연산자 2개를 꺼내어 연산을 실행한다

3. 결과값을 다시 스택에 넣는다 

---

중위표기식을 입력으로 받아서, 바로 연산할 수 없는 이유는

사칙연산 간의 우선순위 그리고 괄호의 존재 때문이다.

따라서, 우선순위를 먼저 고려한 상태의 수식으로 변환시켜놓고, 계산해야하는 것이다.

 

그럼, 코드로 구성할 것도 크게 2가지다.

1. 중위표기식->후위표기식 변환기

2. 후위표기식 계산기 

---

1번은 아래처럼 구성한다.

 

1. 중위 표기식의 토큰을 읽는다

2. 숫자면 토큰을 통해 값을 받아서 출력한다. 

3. 연산자면, 스택에 넣는다. 숫자 뒤에다가 나중에 일괄적으로 출력할 것이기 때문이다. 

4. 이 때, 스택에 있는 연산자들과 계산 우선순위를 비교한다. 

   우선순위가 높은 연산자가 먼저 출력이 되야 하기 때이다. 

   - 토큰 연산자가 순위가 높으면, 스택에 쌓는다

   - 토큰 연산자가 순위가 낮으면, 스택에 있는 연산자를 출력한다. 

   - ) 괄호가 등장하면, 스택에 있는 연산자를 모두 토해낸다. ( 괄호와 )괄호는 출력하지 않는다 

5. 토큰을 모두 읽으면, 마지막에 스택을 확인하여 연산자를 모두 토해낸다.

---

만들어보았는데, 오류가 많다;;

괄호가 있는 계산식에서 후위표기식을 만드는 데 오류가 있고,

미처 찾지 못했지만, 계산과정에서 자료형을 다루는 데 오류가 있는 듯 싶다.  

 

디버깅만 몇 주에 걸쳐서 며칠을 했더니, 정작 공부 진도를 못 빼고 있다.

이건 링크만 걸어두고 나중에 참조용으로 남겨야 겠다.  

 

GitHub - Sukmin-LanternK/Data-Structure_LLS-Calculator