계산기 모듈^#

내가 맡은 계산기 모듈은 "(2*(3+6/2)+2)/4+3"과 같은 수식이 입력되었을 경우, 우선순위에 따라서 계산 할 수 있도록 마련해주는 것이다. 계산을 위해 후위표기법을 이용할 텐데, 이것은 스택을 이용하여 계산하는 방식으로 해당 알고리즘은 "C로 배우는 알고리즘"이란 책을 참고하였다.

 

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

위와 같은 수식을 중위표기법이라고 하는데, 이것을 우선순위별로 계산하도록 유도하기 위해선 후위표기법으로 변환해야 한다. 후위표기법은 아래와 같은 수식을 말한다.

2362/+*2+4/3+

이렇게 변환된 수식은 우선 순위를 고려할 필요 없이 아래와 같은 규칙을 통하면 계산이 손쉽게 이루어진다.

1. 숫자를 만나면 숫자는 스택에 푸시한다.
2. 연산자를 만나면 스택에서 팝을 두 번하여 그 두 데이터를 가지고 연산한 다음 그 결과를 스택에 다시 푸시한다.

일단, 계산은 박성철 회원이 담당하기로 했고, 필자는 중위표기법으로 표현된 수식을 우선순위를 고려한 후위표기법으로 표현하기만 하면 된다.

변환 알고리즘은 아래와 같다.

1. '('를 만나면 스택에 푸시한다.
2. ')'를 만나면 스택에서 ')'가 나올 때까지 팝하여 출력하고 '('는 팝하여 버린다.
3. 연산자를 만나면 스택에서 그 연산자보다 낮은 우선순위의 연산자를 만날 때까지 팝하여 출력한 뒤에 자신을 푸시한다.
4. 피연산자는 그냥 출력한다.
5. 모든 입력이 끝나면 스택에 있는 연산자들을 모두 팝하여 출력한다.

변환 과정 예시 ^#

문자	화면	스택(상단-하단)	설명
( 2 * ( 3 + 6 / 2 ) + 2 ) / 4 + 3 끝	2 2 2 2 3 2 3 2 3 6 2 3 6 2 3 6 2 2 3 6 2 / + 2 3 6 2 / + * 2 3 6 2 / + * 2 2 3 6 2 / + * 2 + 2 3 6 2 / + * 2 + 2 3 6 2 / + * 2 + 4 2 3 6 2 / + * 2 + 4 / 2 3 6 2 / + * 2 + 4 / 3 2 3 6 2 / + * 2 + 4 / 3 +	( ( * ( ( * ( ( * ( + ( * ( + ( * ( / + ( * ( / + ( * ( * ( + ( + ( + ( / / + +	'('는 푸시 피연산자는 출력 '*'가 '('보다 우선순위 높음 '('는 푸시 피연산자는 출력 '+'가 '('보다 우선순위 높음 피연산자는 출력 '/'가 '+'보다 우선순위 높음 피연산자는 출력 '('까지 팝하여 출력, '('는 무시 '*'는 '+'보다 높으므로 팝 피연산자 출력 '('까지 팝하여 출력 연산자 푸시 피연산자 출력 '/'가 '+'보다 높으므로 팝 피연산자 출력 끝이므로 모두 팝

"C로 배우는 알고리즘"의 p.203에서 참고함.

어셈블리어로 구현하기 위한 기본 개념^#

변환 알고리즘을 어셈블리어로 그대로 구현하기는 쉬운 일이 아니었다. 필자도 수번의 디버깅을 통해, 버그를 추적한 끝에 어느 정도 만족할 수준의 결과를 얻을 수 있었다. 물론, 구현에 급급한 나머지 코딩을 했기 때문에, 아직 부족한 면이 많을 것이라 생각한다.

첫번째로 고려해야 할 요소는 위에 수식을 메모리에 어떻게 위치시킬 것인가 이다. 다른 회원이 ascii - hex 와 같은 모듈을 구현하기 때문에, 문자열 "2"를 숫자 2로 교체하는 것까지 할 필요가 없었고, 그렇다고 숫자로만 하자니, "+", "*"와 같은 연산자가 문자이기 때문에 또 문제가 있을 것이라 생각했다. 모든 것을 문자열로 처리하기로 했으며, 숫자의 크기도 1byte로 제한을 두기로 했다. 나중에 확장을 고려할 예정이다. 여전히 토큰으로 문자열을 쪼개고, 각 문자열을 연결하기 위한 포인터 배열을 사용해야 하는 등 복잡한 요소들이 기다리고 있다.

데이터 세그먼트^#

일단은, "(1+2)*2/(2-1)"과 같은 수식이 문자열로 메모리에 입력된 상태에서 출발을 했다. 아래 코드는 데이터 세그먼트(데이터 영역)의 정의부이다.

1. DATA SEGMENT PUBLIC
      CALC    DB '(2*(3+6/2)+2)/4+3', 0h ; 계산 수식
      BUFF    DB '                  $'   ; 출력 버퍼
      ERR_MSG DB 'error!$'
   DATA ENDS

CALC이란 이름으로 참조할 수 있는 문자열이 계산할 수식이며, BUFF로 지어진 공간에 후위표기법으로 변환후 저장할 것이다. ERR_MSG는 에러 발생할 경우, 화면에 출력하기 위한 문자열이다. 기타 계산에 필요한 공간은 스택과 레지스터를 사용하였다.

 

코드 세그먼트^#

코드는 엔트리 지점이란 것이 있는데, 이것은 프로그램이 로드되었을 경우, 처음 실행되는 위치이다. 이것을 masm에서는 아래와 같이 정의하게 된다.

1. CODE SEGMENT PUBLIC
      ASSUME CS:CODE, DS:DATA
2. Start:
      mov ax, DATA
      mov ds, ax
3.    .............
   CODE ENDS
      END Start

도스에서 실행되는 대부분의 exe 파일이 위와 같은 구조로 맨 처음 데이터 세그먼트 레지스터(ds)와 사용자가 정의한 데이터 세그먼트 영역을 연결시켜주는 것이다. 물론, 스택 세그먼트 레지스터(ss)와 es도 해주면 좋겠지만, 큰 프로그램이 아니라면 해 줄 필요까진 없다.

위 소스에서 보이다시피, Start Label로 정의된 위치가 프로그램의 시작 위치가 된다. 마지막 줄에 END LABEL 부분에서 시작 지점을 정해줄 수 있다.

 

컴파일 환경 구축^#

컴파일 환경을 구축하는 데에는 그다지 까다롭지 않다. 일단, masm과 link만 있으면 되기 때문이다. 좀 더 편하게 컴파일을 하기 위해선 도스 환경에서 배치 파일을 작성해두면 편리하다.

 위 내용을 as.bat 파일로 저장한다. 물론, 디렉토리는 아래 캡쳐 화면과 같이 c 드라이브 아래 masm에 ml과 link 파일이 존재하고, 그 디렉토리 내에 src 디렉토리를 생성하여 코드를 놓은 상태이다. src 디렉토리에 as.bat 파일도 존재하게 된다.

 

 실행은 아래와 같이 실행 - command 엔터를 누른 후, 해당 디렉토리로 이동 후, 간단하게 as.bat나 as 엔터를 입력하면 된다.

 

 자, 이젠 소스를 수정하고 해당 디렉토리에서 as만 하면 되므로, 컴파일에 대해 신경을 쓰지 않아도 된다.

 

실제 구현 소스 분석^#

그러면, 실제 소스를 보면서 어떻게 후위표기법으로 변환하는 지 알아보자.

• 구현 소스 : calc_t.asm

소스를 살펴보면, 크게 Next: 부분에서 모든 것이 처리됨을 알 수 있다. 비교하여 현재 가리키고 있는 문자가 0(NULL)일 경우, _End_Proc로 점프하게 하여 스택에 아직까지 남아있는 모든 연산자를 버퍼에 저장하고, 프로그램을 종료하게 한다. 이것은 마지막을 위한 것으로, 보통 '('과 '0' ~ '9' 그리고, '+', '-', '/', '*' 를 위한 것으로 되어 있으며, ')'으로 괄호를 해제하게 된다.

구현된 원리는 일단, 아래와 같이 소스에 주석을 넣은 것으로 이해해보자.

 

 

작성 정보 ^#

• 처음으로 작성 -- 2008/10/21 03:24:30