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