안경잡이개발자

728x90
반응형

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


  일반적으로 우리가 알고 있는 대수학의 표기법인 중위 표기법을 컴퓨터에게 계산하도록 만들고 싶으면 후위 표기법으로 변환한 뒤에 계산하는 과정이 필요합니다. 실제로 계산기 등이 내부적으로 수행하고 있는 방법이기도 합니다. 재미있는 점은 중위 표기법을 후위 표기법으로 바꿀 때는 오직 스택(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());

}


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


728x90
반응형

728x90
반응형

 선형 구조와 수식 계산


  자료구조에서 선형 구조(Linear Structure)는 말 그대로 데이터를 선형적으로 표현하는 자료구조를 의미합니다. 선형구조에는 배열(Array), 스택(Stack), 큐(Queue), 연결 리스트(Linked List) 등이 포함됩니다. 스택은 일반적으로 수식 계산에 가장 많이 사용됩니다. 공무원 시험이나 대학원 시험 등 어떠한 시험을 치를 때에도 스택과 관련한 문제가 굉장히 많이 출제되므로 모든 선형 구조 중에서 스택은 꼭, 반드시 알고 있어야 합니다. 또한 추가적으로 스택과 큐가 함께 사용되는 구조를 데큐(Deque)라고 합니다.


  일반적으로 소프트웨어에서 수식을 계산할 때는 스택(Stack)을 사용합니다. 이는 컴퓨터의 내부적인 처리 방식과도 연관이 깊습니다. 스택에 대한 자세한 설명은 네이버 블로그 https://blog.naver.com/ndb796/221230937978에서 제가 이전에 정리한 바가 있습니다.


 표기 방식의 세 가지 종류


 ▶ 위 표기(Prefix)


  전위 표기란 연산자를 피연산자 앞에 표기하는 방법입니다.


  EX) * - + a b c * c a


  중위 표기(Infix)


  중위 표기란 연산자를 피연산자의 가운데에 표기하는 방법입니다. 일반적으로 대수학에서 사용되는 표기법입니다.


  EX) ( a + b - c ) * d * e


 ▶ 후위 표기(Postfix)


  후위 표기란 연산자를 피연산자의 뒤에 표기하는 방법입니다. 컴퓨터가 처리하기에 가장 적합한 표기법입니다.


  EX) a b + c - d e * *


  위 세 가지 표기법에서 예시로 든 수식은 사실 모두 동일한 수식입니다. 이를 가장 먼저 전위 표기법을 이진 트리로 표현함으로써 증명해보겠습니다. * - + a b c * c a는 다음과 같이 연산 우선순위를 설정할 수 있습니다.



  이제 이걸 토대로 바로 다음과 같이 이진 트리로 표현할 수 있습니다.



  이진 트리로 표현한 뒤부터는 전위 표기, 중위 표기, 후위 표기로 나타내는 것은 매우 쉽습니다. 전위 표기법으로 표현할 때는 바로 부모 노드를 출력하고, 왼쪽 노드 및 오른쪽 노드에 방문하면 됩니다. 중위 표기법으로 표현할 때는 왼쪽 노드, 부모 노드, 오른쪽 노드로 방문하면 됩니다. 마지막으로 후위 표기법은 왼쪽 노드, 오른쪽 노드, 부모 노드를 차례대로 방문하면 됩니다.


  또한 재미있는 점은 중위 표기법을 제외하고 전위 표기법 및 후위 표기법에서는 괄호가 들어가지 않습니다. 괄호 없이 처리할 수 있다는 점에서 컴퓨터가 처리하기에 있어서는 가장 편리하고 간단한 표기 방식이라고 할 수 있습니다.


 ▶ 중위 표기 및 후위 표기 변환기: https://www.mathblog.dk/tools/infix-postfix-converter/


  또한 이 사이트에서는 중위 표기와 후위 표기를 마음대로 변환할 수 있도록 해줍니다. 상당히 유용해요.






728x90
반응형