스택과 계산기

식의 표현

4.2.1) 식의 표현

수식을 표현하는 방법 중에 연산자의 위치를 기준으로 하는 방법이 있다.

전위 표기법(prefix notation) : 연산자가 피연산자 앞에 위치한다. (ex: + 1 2)

중위 표기법(infix notation) : 연산자가 피연산자 사이에 위치한다. (ex: 1 + 2)

후위 표기법(postfix notation) : 연산자가 피연산자 뒤에 위치한다. (ex: 1 2 +)

이 중에 우리에게 익숙한 표기법은 중위 표기법인데위에서 말했지만 연산자의 우선순위가 달라 이대로 분석하기는 어렵다그렇다면 후위 표기법은 어떨까연산자의 위치가 뒤에 있다는 사실은 알고 있는데 이것만으로 연산자의 우선순위에 관한 문제를 해결할 수 있을까?

먼저 이 후위 표기법이라는 것을 직접 사용해보자다음과 같은 중위 표기식이 있다.

1 + 2

위에서도 예시로 보였지만 이 식을 후위 표기법으로 표현하면 다음과 같다.

1 2 +

그렇다면 다음은 어떻게 후위 표기법으로 표기할까?

1 + 2 + 3

이는 각각의 연산을 치환하면 이해하기 쉽다먼저 실수 A, B에 대해 다음이 성립한다.

A + B = A B +

따라서 (1 + 2 = A)로 놓으면 다음이 성립한다.

1 + 2 + 3 = A + 3 = A 3 +

이때 (A = 1 2 +)이므로 다음이 성립함을 보일 수 있다.

1 + 2 + 3 = A 3 + = 1 2 + 3 +

그러면 다음 식은 어떨까?

1 + 2 * 3

먼저 우선순위가 높은 곱셈식부터 문자로 치환해보자. (2 * 3 = A)라고 하면 다음이 성립한다.

1 + 2 * 3 = 1 + A = 1 A +

이때 (A = 2 3 *)이므로 다음이 성립한다.

1 + 2 * 3 = 1 A + = 1 2 3 * +

이와 같은 방법으로 다음의 식들을 모두 후위 표기법으로 표기할 수 있다.

1 + 2 + 3 = 1 2 + 3 +

1 * 2 + 3 = 1 2 * 3 +

1 + 2 * 3 = 1 2 3 * +

1 * 2 * 3 = 1 2 * 3 *

1 + 2 - 3 + 4 = 1 2 + 3 - 4 +

1 + 2 * 3 + 4 = 1 2 3 * + 4 +

(1 + 2) * (3 - 4) = 1 2 + 3 4 - *

5 * (6 + 7 + 8) - 7 * 9 = 5 6 7 + 8 + * 7 9 * -

그러면 이제 변환한 후위 표기식이 잘 변환되었는지 확인해보자후위 표기법으로 표현한 식을 다시 중위 표기법으로 표현하는 것이다이 또한 전혀 어렵지 않은데왜냐하면 방금 우리가 했던 과정을 순서만 바꾸어서 다시 수행하면 되기 때문이다.

위에서 후위 표기법으로 표현된 식을 다시 중위 표기법으로 표현해보자왼쪽부터 분석한다.

1 2 + 3 +

이때 (1 2 + = A)로 놓으면 다음이 성립한다.

1 2 + 3 + = A 3 + = A + 3

또한 (A = 1 + 2)가 성립하므로 다음이 성립한다.

1 2 + 3 + = A + 3 = 1 + 2 + 3

이와 같이 역변환이 성립함을 보일 수 있다다른 예제를 보자.

1 2 3 * +

이때 (2 3 * = A)로 놓으면 다음이 성립한다.

1 2 3 * + = 1 A + = 1 + A

또한 (A = 2 * 3)이 성립하므로 다음이 성립한다.

1 2 3 * + = 1 + A = 1 + 2 * 3

이와 같이 임의의 식을 후위 표기법중위 표기법으로 변환하는 방법을 알아보았다그런데 아직 당신은 왜 후위 표기법으로 표현된 식이 중위 표기법으로 표현된 식보다 분석하기 쉬운지에 대한 설명은 듣지 못했다정확히 무엇이 더 나아진 것일까?

다음 후위 표기식의 피연산자를 무시하고 연산자만 뜯어서 왼쪽부터 차례로 읽어보라.

1 + 2 + 3 = 1 2 + 3 + : + +

1 * 2 + 3 = 1 2 * 3 + : * +

1 + 2 * 3 = 1 2 3 * + : * +

1 * 2 * 3 = 1 2 * 3 * : * *

1 + 2 - 3 + 4 = 1 2 + 3 - 4 + : + - +

1 + 2 * 3 + 4 = 1 2 3 * + 4 + : * + +

(1 + 2) * (3 - 4) = 1 2 + 3 4 - * : + - *

5 * (6 + 7 + 8) - 7 * 9 = 5 6 7 + 8 + * 7 9 * - : + + * * -

연산자만 뜯어서 왼쪽부터 차례로 살펴보면 아주 재미있는 사실을 발견할 수 있는데바로 연산자가 식에서 먼저 연산이 진행되어야 하는 순서로즉 높은 우선순위부터 낮은 우선순위로 연산자가 정렬되어 있다는 것이다후위 표기법으로 표현된 식에는 연산자의 우선순위에 대한 정보가 이미 포함되어있다즉 후위 표기법으로 표현된 식을 분석할 때는 연산자의 우선순위를 고려할 필요가 없다바로 이 점 때문에 중위 표기식보다 후위 표기식이 분석하기 수월하다.

이와 같이 후위 표기식이 중위 표기식보다 분석하기 쉬운 이유를 알 수 있었다.

댓글

댓글 본문
버전 관리
한도영
현재 버전
선택 버전
graphittie 자세히 보기