인터프리터...21

역 폴란드 표기법을 사용한 식의 분석

식의 우선순위에 따라 식을 후치 기법으로 변환하는 것을 역 폴란드 표기법이라고 하며 정렬된 식은 괄호와 우선순위가 제거되며 앞에서부터 순서대로 읽어서 사용할 수 있게 된다.

식	역폴란드 표기법	한글로 표기
a + b	a b +	a에 b를 더한다
a + b + c	a b + c +	a에 b를 더한 결과에 c를 더한다
a + b * c	a b c * +	a에 b와 c를 곱한 결과를 더한다
(a + b) * c	a b + c *	a에 b를 더한 결과에 c를 곱한다

 

변환 패턴과 변환 방법

역 폴라드 표기법으로 변환할 때 우선순위가 더 높은 토큰이 입력되는 경우 변환을 잠시 미루고 우선순위가 높은 토큰을 먼저 처리한다.

 

이를 적용해 변환하는 방법은 다음과 같다.

1. 요소의 우선순위를 정한다.
   1. * /
   2. + -
   3. (
2. 식을 변환한다.
   1. 변수나 상수면 그대로 출력
   2. ( 면 PUSH
   3. ) 면 스택의 탑이 ( 가 될 때까지 POP 후 출력 ( 는 POP 후 제거
      • (가 없으면 오류
   4. 마지막 요소면 스택의 모든 요소를 POP 후 출력
      • ( 가 있으면 오류
   5. 그 외의 경우 스택의 탑이 입력된 것 이상의 우선순위를 가지면 POP 후 출력 아니면 PUSH

 

평가 방법

역 폴란드 표기법으로 변환 후에는 앞에서부터 순서대로 읽어서 평가하면 된다. 평가 방법은 다음과 같다.

1. 변수나 상수면 PUSH
2. 연산자면 POP 한 값을 우측 값으로, 다시 POP 한 값을 왼쪽 값으로 하여 연산 후 결과를 PUSH
3. 마지막 요소일 때 스택에서 POP 하여 결과로 사용

 

참고문헌

만들면서 배우는 인터프리터하야시 하루히코 상세보기