수학의 연산자뿐만 아니라 프로그래밍 언어의 연산자 역시 우선순위라는 개념이 존재한다. 이는 여러 가지 연산자가 포함된 수식에서 어떤 연산자를 먼저 연산해야 하는지를 지칭하는 순서이다. 우선순위가 정의되는 경우 일반적으로 두 연산자의 우선순위 관계는 불변이므로, 임의의 개수의 연산자에 대해 우선순위가 높은 순서대로 1-based index를 매길 수 있다.

FORTRAN I Compiler는 우선순위의 index를 이용하여 연산자의 연산 순위를 올바르게 반영하는 parenthesized string으로 연산식을 치환한다. 이는 우선순위 정보를 갖고 있지 않더라도 식을 평가할 수 있게 하며, 연산식 파싱을 간단한 괄호 문자열 스위핑 문제로 환원한다. 그 구체적인 알고리즘은 다음과 같이 서술할 수 있다.

  1. 연산자의 우선순위가 높은 순서대로 1-based index를 부여한다. 임의의 두 연산자가 서로 우선순위가 같다면 같은 index가 부여되어도 무관하다. index가 부여된 연산자 $*$의 해당 index를 $I_*$라 하자. 또한 $M=\displaystyle\max_{\forall \text{operator }*}I_*$으로 $M$을 정의하자.
  2. 연산식을 한 쌍의 괄호로 감싼다.
  3. $($과 $)$를 각각 $\overbrace{((...(}^{M+1}$과 $\overbrace{))...)}^{M+1}$로 치환한다.
  4. 모든 연산자 $*$에 대해 연산식 내의 $*$를 $\overbrace{))...)}^{I_*}*\overbrace{((...(}^{I_*}$로 치환한다.

$1+(2*3+4)*5$를 예시로 알고리즘을 적용해보자.

  1. $I_*=1,I_+=2,M=2$
  2. $(1+(2*3+4)*5)$
  3. $(((1+(((2*3+4)))*5)))$
  4. $(((1))+(((((2)*(3))+4))))*(5)))$

알고리즘의 결과로 $(((1))+(((((2)*(3))+4))))*(5)))$라는 수식을 얻을 수 있고, 이는 괄호만으로 원래의 연산자 계산 순서를 보장하는 문자열이다.

과연 이 알고리즘은 항상 올바른 괄호 문자열, 그것도 연산자 계산 순서를 동일하게 보장하는 문자열을 생산할까? 

 

Lemma 1. 입력에 괄호가 없을 경우 알고리즘은 올바른 괄호 문자열을 생산한다.

수식을 순서대로 읽을 때 $($의 개수에서 $)$의 개수를 뺀 값을 $P$라 하자. 알고리즘의 2번 단계에서 추가된 괄호에 의해 초기에 $P$는 $M+1$이다.

$M$의 정의에 의해 각각의 연산자가 치환 후 그 직전에 갖는 $)$의 개수는 $M$개 이하이므로 모든 시점에서 $P$는 1 이상이다. 또한 $*$가 치환된 $\overbrace{))...)}^{I_*}*\overbrace{((...(}^{I_*}$는 각각 ${I_*}$개의 $($과 $)$를 포함하므로 치환된 문자열을 처리하기 전과 후의 $P$는 동일하다. 따라서 각각의 연산자를 처리하며 $P$는 최소 1의 값을 가지며 마지막 $M+1$개의 $)$ 처리하기 직전에는 $P=M+1$이다. 따라서 수식을 전부 처리하면 $P=0$이므로 알고리즘의 출력은 올바른 괄호 문자열이다.

Lemma 2. 입력이 올바른 수식일 경우 알고리즘은 올바른 괄호 문자열을 생산한다.

입력에 괄호가 없는 경우는 Lemma 1에서 증명하였으므로 입력에 괄호가 존재하는 경우를 증명하자.

입력된 수식은 유한하므로, 양끝에 각각 하나의 $($와 $)$를 가지며 이외에는 괄호를 포함하지 않는 부분 수식 $(S)$를 고를 수 있다. 그렇지 않은 경우 무한히 부분 수식을 택하여 무한한 $($와 $)$가 문자열에 포함되어 수식이 유한한 길이를 갖는다는 조건에 모순된다.

이때 $(S)$가 치환된 문자열은 입력에 괄호가 없는 수식 $S$가 알고리즘에 입력됐을 때의 출력과 동일하다. Lemma 1에 의해 $(S)$가 치환된 문자열은 올바른 괄호 문자열이다.

즉 $(S)$가 치환된 문자열의 전후에서 $P$의 값이 동일하며, Lemma 1의 증명에서 언급한 것과 같이 연산자가 치환된 문자열에 의해서는 괄호 문자열이 올바르지 않게 될 수 없다. 따라서 귀납적으로 알고리즘의 전체 출력은 올바른 괄호 문자열이다.

Lemma 3. 입력에 괄호가 없을 경우 알고리즘은 연산 순서가 유지된 수식을 생산한다.

연산자가 위치한 곳에서의 $P$ 값이 높을수록 알고리즘의 출력 수식의 expression tree에서 depth가 깊다. 즉, $P$ 값이 높은 연산자일수록 먼저 계산된다. $P$ 값이 동일하며 우선순위가 서로 다른 연산자가 존재한다면 이 성질은 성립하지 않을 수 있지만, 알고리즘에 의하여 입력에 괄호가 없을 경우 어떤 연산자 $*$에서의 $P$는 $M+1-I_*$이기 때문에, 우선순위가 서로 다른 연산자는 서로 다른 $P$ 값을 가진다. 즉 위 성질이 성립하여 연산자 우선순위가 괄호에 의해 보존되게 된다.

Theorem 1. 입력이 올바른 수식일 경우 알고리즘은 연산 순서가 유지된 수식을 생산한다.

Lemma 2와 마찬가지로 양끝에 각각 하나의 $($와 $)$를 가지며 이외에는 괄호를 포함하지 않는 부분 수식 $(S)$를 고를 수 있다. $(S)$가 치환된 문자열은 입력이 $S$일 때의 Lemma 3를 적용할 수 있다. 이후 $(S)$를 포함하는 $(S)$가 아닌 최소 길이의 부분 수식 $(T)$에 대해, $(S)$는 하나의 상수 $C$로 치환하여도 수식 $(T)$의 치환 전후 연산 순서 동일성에 영향을 주지 않는다(괄호 내부는 원래 먼저 계산하므로). 따라서 $(T)$에 포함된 모든 $(S)$들을 어떤 상수로 치환하면 Lemma 3에 의해 $(T)$ 역시 치환 전후의 연산 순서가 변화하지 않는다. 이러한 논리를 귀납적으로 적용하면 입력 전체에 대해 연산 순서가 치환 전후로 변화하지 않는다는 것을 알 수 있다.

 

따라서 Theorem 1에 의해, 위 알고리즘은 항상 의도한 바대로 동작함을 알 수 있다.

'알고리즘' 카테고리의 다른 글

[BOJ Solution] BOJ2727 - 2,3 거듭제곱의 합  (0) 2022.06.28
[BOJ Solution] BOJ1078 - 뒤집음  (0) 2022.06.21
[BOJ Solution] BOJ9556 - 수학 숙제  (0) 2022.06.19

+ Recent posts