1. 소개
간단한 계산기를 C++로 구현했다. 홍정모 교수님의 자료구조 강의 중 스택과 큐를 공부했는데 공부한 것을 활용한 간단한 프로젝트를 해보면 좋을 것 같아서 하게 됐다. 계산기는 C 스타일 문자열(const char*) 형태로 식을 주면 그 식을 읽고 계산한다. 몇 가지 특징은 다음과 같다.
•
계산기에 사용되는 스택과 큐는 클래스 템플릿으로 구현했다.
•
양의 정수, 실수를 피연산자로 사용할 수 있고 자릿수 제한은 없다.
•
연산자와 피연산자 사이 띄어쓰기가 없거나 많아도 계산 가능하다.
•
식 계산에 필요한 메모리 크기는 자동으로 설정된다.
•
사용 가능한 연산자는 +, -, *, / 네 가지다.
•
괄호 () 사용 가능하다.
아래는 구현한 계산기를 테스트하는 짧은 코드다.
Calculator cal;
cal.SetExpression(" 5 + (4 - 9.3 / 3)* 10");
cal.PrintInfixExpression();
std::cout << "= " << cal.EvaluateExpression() << std::endl;
C++
복사
위 코드를 실행했을 때 출력문은 5 + ( 4 - 9.3 / 3 ) * 10 = 14
2. 동작 흐름
SetExpression(const char*)메서드의 인자로 식이 적힌 문자열을 넘기면 식을 순차적으로 탐색하면서 피연산자와 연산자를 새로운 문자열 토큰으로 분리한다. 분리된 토큰은 중위 표기식 큐에 순서대로 집어 넣는다. EvaluateExpression() 를 호출하면 식 계산을 시작한다. 먼저 하는 것은 중위 표기식에 있는 토큰을 꺼내서 순서를 바꿔 후위 표기식 큐에 집어 넣는 것이다. 중위 표기식에서 후위 표기식을 바꾸는 것은 연산자 토큰을 저장하는 스택을 이용해 진행한다. 중위 표기식 큐에서 꺼낸 토큰이 피연산자면 바로 후위 표기식 큐에 넣고, 만약 연산자 토큰이면 연산자 우선순위를 판단해서 연산자 스택에 있는 토큰들을 후위 표기식 큐에 넣거나 그대로 둔 뒤 중위 표기식에서 꺼냈던 연산자 토큰을 스택에 넣는다. 이 과정을 반복하면 후위 표기식이 완성된다. 후위 표기식이 완성되면, 후위 표기식에서 토큰을 하나씩 꺼내는데 토큰이 피연산자면 실수 형태로 형변환을 한 후 피연산자 스택에 들어간다. 연산자 토큰을 꺼내면 해당 연산자에 따라 피연산자 스택에서 피연산자 2개를 꺼내서 계산 후 계산 결과를 다시 스택에 넣는다. 이 과정을 반복하면 후위 표기식 큐에서 모든 토큰을 꺼냈을 때 스택엔 식의 최종 결과 값을 가진 요소 하나만 남게 된다. EvaluateExpression()은 스택에 남은 그 값을 반환한다.
3. 후기
구현 난이도를 올리고 싶어서 표준 라이브러리의 스택, 큐, 문자열을 사용하지 않았다. 그리고 스스로 생각하는 연습을 하기 위해 API를 참고하는 것 외에는 다른 코드를 거의 참고하지 않고 구현했다. 그렇게 어려운 알고리즘이나 자료구조가 사용된 것도 아닌데 참고하는 것을 최소화하고 바닥부터 코드를 짜다보니 자잘한 곳(메모리 복사, 해제, 인덱싱 등)에서 계속 버그가 터져서 내가 생각했던 것보다 구현이 오래 걸렸다. 아직 C++ 코드의 정교함이 떨어지는 것 같다. 또한 다른 코드를 거의 참고하지 않다 보니 이 방법이 최선인가에 대해 고민하는 과정에서 시간을 많은 잡아먹었다. 하지만 그 고민하는 과정이 언젠간 도움이 될 것이라고 믿는다. 진짜 실력은 무엇이 최선인지 모르는 상황에서 남들보다 더 좋은 선택을 내릴 수 있는 능력이라고 생각하기 때문이다.