[C++] infix -> postfix 수식 변환 & 계산기 구현

* 해당 글은 구현을 단순히 기록차 남겨놓은 후기 글 입니다 강의글이 아니므로 따로 자세한 설명을 넣진 않습니다. 자세한 구현 방식은 나중에 자료구조 탭을 추가하여 제대로 작성할 예정입니다.

 

C++ 에서 infix 수식 (중위 표기법) 을 받아서 postfix 수식 (후위 표기법) 으로 변환 후 그 postfix  수식에 대한 값을 계산해 결과값을 출력하는 기능을 구현했습니다. 뭐 이번에도 과제때문에 억지로 구현한거긴 합니다.

 

사실 프로그래밍을 하면서 일반적으로 리터럴에 적는 여러가지 수식들은 자연스럽게 컴퓨터가 읽어내 계산할 수 있도록 컴파일러가 처리해줍니다만, 실제로 수식 문자열을 입력받아서 계산하는 기능은 생각보다 굉장히 어려운 기능입니다.

(당장 수식을 계산하는 방법을 머리 속으로 생각해보면, 정수의 사칙연산 정도는 간단하지만 소수라던가, 공백이라던가 여러 가지를 추가 고려하다보면 머리가 아파집니다.)

 

일반적으로 Python, JavaScript 같은 고추상화 언어에서는 eval() 이라는 함수로써 문자열 수식을 계산하는 기능을 지원하긴 합니다만, 대부분 이런 함수들은 어떻게 구현됐는진 몰라도 허용범위가 너무 넓어서 항상 보안 문제가 발생합니다.

 

어쨌던, 제가 구현한 C++ 수식 계산기의 경우 완벽한 만능 계산기는 아니고 아래와 같이 허용범위가 다소 제한적인 사칙연산 계산기 입니다. (사용자 입력의 경우 제대로 입력했다고 상정하며, 오류 체크는 하지 않습니다.)

 

• 모든 연산자 (+,-,*, /) 는 이항 연산자 입니다. (binary operator)

그렇기 때문에 -2 와 같이 양수 앞에 음수를 표기하기 위해 사용하는 음수 단항 연산자의 경우는 동작하지 않습니다. -2 + 2 와 같은 연산은 불가하다는 뜻입니다. 무조건 이항 연산자기 때문에 0 - 2 + 2 와 같은 형태로 무조건 피연산자를 2개 제공해줘야 합니다. 

• 피연산자는 숫자와 변수입니다

숫자는 우리가 흔히 아는 그냥 숫자들이고 (소수, 정수 모두 가능) 변수는 숫자 이외에 입력한 임의의 문자입니다. 계산 수행 중 변수 발견시 사용자에게 그 값을 입력받아서 계산합니다.

• 수식에 괄호가 들어가 있어도 잘 동작합니다

괄호 쌍만 사용자가 잘 입력했다면 알아서 잘 계산합니다.

 

 

내부적으로는 일반적으로 수식을 infix에서 postfix로 변환하는 작업, postfix 를 계산하는 작업은 모두 스택을 이용하여 수행하면 됩니다. 사실 과제 구현 조건이 이중 연결 리스트(Doubly Linked List) 를 구현하고, 덱(Deque) 을 이용해 수식을 변환하는 것이기에 우선 이중 연결 리스트에서 사용할 node 구조체를 먼저 정의합니다.

 

덱(Deque, Double-Ended-Queue)
 의 경우 조금 생소하실 수 있는데 쉽게 말해서 스택과, 큐의 장점을 모두 합친 자료구조로 양쪽 끝단에서 아이템 삽입 & 삭제가 가능하며, 양쪽단의 삽입 삭제가 시간 복잡도 $O(1)$ 인 우수한 자료구조 입니다. 영어 철자론 Deque, 발음은 "덱" 이라고 읽습니다. Deque를 스택으로써 사용하고 싶으면 앞 또는 뒤에서, 즉 동일한 위치에서만 삽입 삭제 연산을 수행하면 되고, 큐로써 사용하고 싶으면 앞에 넣고 뒤에서 빼거나, 뒤에서 넣고 앞에서 빼면 됩니다.

 

이중 연결 리스트의 경우 단일 연결 리스트와 다르게 한 노드의 링크가 앞의 요소, 뒤의 요소를 모두 가르키고 있어서 어떤 요소를 찾았을 때, 그 요소의 뒤로도 갈 수 있고 앞으로도 갈 수 있는 자유로운 형태입니다.

 

단일 연결 리스트의 경우 노드가 바로 다음 앞에 요소만 가르키고 있어서 어떤 요소를 탐색해서 찾으면 그 이전의 요소로 바로 돌아갈 수 없고, 찾으려면 처음 헤드 포인터 위치부터 다시 탐색해야 합니다.

 

어쨌던.. 본론으로 돌아와서 DLinkedList 라는 이중 연결 리스트를 구현하는데, 연결리스트 node의 첫번째 요소를 가리키는 포인터 head_ptr 과, node의 마지막 요소를 가르키는 tail_ptr 를 이용해 접근하고, head_ptr 위치와 tail_ptr 위치에 node를 동적할당하여 관리할 것이므로 멤버 변수로 node 구조체를 직접 가지진 않습니다.

 

이렇게 삽입 연산 요청이 들어오면 head_ptr 과 tail_ptr을 내부적으로 조정하면서 앞전에 선언한 dnode 를 동적 할당해 포인터로 가르키게 함으로써 접근하게 됩니다.

 

이중 연결리스트, 이중 연결리스트에서 사용하는 node의 경우 전부 템플릿으로 구현되어서 어떤 자료형의 데이터라도 저장이 가능합니다.

 

이제 데이터 저장구조인 Deque 구현입니다. 사실 이중 연결리스트에서 제공하는 함수를 이용하면 스택이건, 덱이건, 큐던 모조리 구현 가능하기 때문에 사실 이중 연결 리스트를 스택처럼 그대로 사용해도 되긴 합니다. (예를 들어서 파이썬에서는 리스트라는 강력한 자료형이 있어서 이걸로 큐나 스택을 마음대로 구현 가능했죠.)

 

실제로도 deque는 방금 구현한 이중 연결 리스트 객체를 멤버 변수로 가져서, 단순히 이중 연결 리스트의 메서드들을 인터페이스 역할로써 호출 해줄 뿐입니다.

 

마지막으로 infix 수식을 입력받아서 postfix 수식으로 변환하는 역할을 수행하는 class type인 evaluator 와 operator_wrapper 입니다. operator_wrapper 의 경우 연산자의 우선순위를 비교하는데 사용합니다.

사실 상세 구현이 말로 설명하기엔 너무 길어지기도 하고 글 목적도 설명이 아니니깐 설명하도록 하겠습니다. (이거만 보면 토나와요 🤮)

 

어쨌던 여러 고생 끝에 잘 작동하는 코드를 얻어내긴 했습니다. C++ 까가 엄청 많던데, 쓰면서 그 이유를 알 거 같긴 합니다. C에서 string 없는게 불편해서 C++을 오면서 암이 치료됐지만 그와 동시에 온갖 혼란한 기능 폭탄을 맞았습니다 ㅡㅡ; 어쨌던 디버깅 툴 없었으면 프로그램 버그를 어떻게 잡았을까 싶네요.. 커널 개발자나 드라이버 개발자, 시스템 개발자들이 참 대단해보이는 하루입니다.