[ 자료구조 ] 2. 중위 표기법을 후위 표기법으로 변환하여 계산하기

본 포스팅에는 오류가 있습니다. 시간날 때 수정하겠습니다.

  일반적으로 우리가 알고 있는 대수학의 표기법인 중위 표기법을 컴퓨터에게 계산하도록 만들고 싶으면 후위 표기법으로 변환한 뒤에 계산하는 과정이 필요합니다. 실제로 계산기 등이 내부적으로 수행하고 있는 방법이기도 합니다. 재미있는 점은 중위 표기법을 후위 표기법으로 바꿀 때는 오직 스택(Stack)만 있으면 됩니다. 스택을 적절히 활용하면 처리할 수 있다는 점이 매우 큰 특징입니다.

  컴퓨터가 수식을 계산하는 방법은 다음의 두 절차를 따르면 됩니다.

 ① 중위 표기법을 후위 표기법으로 변환하기

  중위 표기법을 후위 표기법으로 바꿀 때는 다음의 절차를 따르면 됩니다.

  1) 피연산자가 들어오면 바로 출력합니다.

  2) 연산자가 들어오면 자기보다 우선순위가 높거나 같은 것들을 빼고 자신을 스택에 담습니다.

  3) 여는 괄호 '('를 만나면 무조건 스택에 담습니다.

  4) 닫는 괄호 ')'를 만나면 '('를 만날 때까지 스택에서 출력합니다.

  한 번 중위 표기식 ( a + b - c ) * d * e을 위 공식에 따라서 후위 표기법으로 변환해봅시다.

  변환 결과: a b + c - d e * *

  숫자를 이용해 표현해봅시다. ( 5 + 6 - 7 ) * 1 * 5 이 경우도 다음과 같이 변환할 수 있습니다.

  변환 결과: 5 6 + 7 - 1 5 * *

  이러한 과정을 의사코드로 표현하면 다음과 같습니다.

------------------------------------------------------------------------------------------------

void translation(exp) {

while((token = getChar(exp)) != NULL) {

if(token == 피연산자) print(token);

else if(token == ')') {

while(stack[top] != '(') print(pop());

pop();

}

else {

while(getPriority(stack[top]) >= token) print(pop());

push(token);

}

}

while((token = getChar(exp)) != NULL) print(token);

}

------------------------------------------------------------------------------------------------

 ② 후위 표기법을 계산하기

  후위 표기법을 계산할 때는 다음의 절차를 따르면 됩니다.

  1) 피연산자를 만나면 스택에 담습니다.

  2) 연산자를 만나면 스택에서 두 개의 연산자를 꺼내서 연산한 뒤에 그 결과를 스택에 담습니다.

  3) 연산을 마치고 스택에 남아있는 하나의 피연산자가 연산 수행 결과입니다.

  후위 표기식: 5 6 + 7 - 1 5 * *

  계산 결과: 20

  이러한 과정을 의사코드로 표현하면 다음과 같습니다.

------------------------------------------------------------------------------------------------

void calculate(exp) {

int x, y, z;

while((token = getChar(exp)) != NULL) {

if(token == 피연산자) push(token);

else if(token == 연산자) {

x = pop();

y = pop();

z = y 연산자 x;

push(z); 

}

}

print(pop());

}

------------------------------------------------------------------------------------------------