새해 첫 포스팅은… 괄호와 연산자 우선순위가 적용되는 스택 계산기 만들기..;;;;
며칠 전, 연산자와 괄호의 우선순위를 인식하는 계산기가 필요하다는 누군가의 요청에 의해 작성하게 되었음. 문제를 듣자 마자 학교에서 자료구조 시간에 배웠던 ‘스택을 이용한 수식계산’이 떠올랐음.
사실 자료구조 기말고사 문제로 출제되었던 내용이라 어렴풋이 기억이 있었는데, 이런 곳에 써먹을 줄은 꿈에도 몰랐다. 당시엔 스택을 이용한 수식계산을 보고, ‘이렇게 계산하는 방법도 있구나…’라고 생각만 하고 그냥 대강 넘어갔었는데…;;
연산자가 피연산자 가운데 위치하는 중위 표기법(infix notation) ex> 2 + 5
연산자가 피연산자 앞에 위치하는 전위 표기법(prefix notation) ex> + 2 5
연산자가 피연산자 뒤에 위치하는 후위 표기법(postfix notation) ex> 2 5 +
여기서 후위 표기법은 폴랜드 논리학자 Jan Lucasiewicz에 의해 고안되었기 때문에 폴리쉬 표기법(polish notation)이라고도 한다.
후위 표기식은 다음과 같은 두 가지 이점을 가지고 있다.
1. 연산자 우선순위와 관계없이 왼편에서 오른편으로 연산자가 기술된 순서대로 일관되게 계산을 하면 되기 때문에, 연산 순서가 간단하다.
2. 연산 순서를 변경시키는 괄호를 사용하지 않는다. 이런 이점으로 컴퓨터 내부에서는 이 후위 표기법을 사용한다.
라고 책에 나와있다;;;
코드를 만들면서 느낀점.
자바는 API에 있는 스택 덕분에 직접 구현하지 않아도 되어서 무지 편했다.(직접 스택을 구현하라고 했다면 시간도 더 들고, 코드의 양도 늘어났을 것임)
입력 받은 식을 후위 표기법으로 변환하기만 한다면 수식을 연산 하는 것은 무지 쉽다.
혼자서 계산기를 만들라고 했다면 힘들었겠 지만, 다행이 나에겐 ‘자료구조’ 책이 있었다.
자세한 알고리즘을 모두 정리하려면 그림도 있어야 하고 복잡하니, 대강 만든 소스만 일단 올려놓아 본다. 나중에 내가 쓰게 될지도 모르니까.
