선형 구조와 수식 계산

  자료구조에서 선형 구조(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/

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