이진트리 + 산술적 파싱

트리는 확장성이 좋은 자료구조가 필요하다.

연결된 목록이 필요하지..(list)

트리의 각 노드는 하나의 연결 목록이 되고 목록의 각 노드는 트리의 다른 노드들을 가리키도록 하자.

트리를 탐색할때는 두종류의 반복자가 필요함.

1. 트리의 현재 노드 2. 현재 노드의 현재 자식노드

 

트리 반복자는 이전에 나왔던 연결 목록 반복자와는 다르다 연결 목록 반복자는 연결 목록에서 뽑아내는 식으로 생성

트리 반복자의 경우 가리키고자 하는 트리 노드를 생성자에 전달

 

이진트리

일반적 트리에는 없는 몇가지 특성

1. 포화성(새로운 수준을 하나 더 추가하지 않는 한 더 이상 노드들을 추가할 수 없음)

2. 조밀성(최하위 수준바로 전까지는 꽉 차 있으며 최하위 수준의 모든 말단 노드들이 왼쪽부터 채워져 있는 것)

* AVL 트리와  RBT(red black tree)는 상당히 보잡하여 게임프로그래밍에서는 별로 나타나지 않음

 

 

구성방법

1) 연결된 이진트리

일반트리는 자식들을 하나의 연결목록에 담지만 이건 고정된 두 포인터를 사용함.

이진트리 노드를 그린다면..

왼쪽 자료 부모 오른쪽(부모는 꼭 필요한게 아니지만 순행할때 매우 편리해짐..)

 

2) 배열로된 이진트리

이진 트리의 자식 개수가 항상 2로 고정되어 있다는 점을 이용한 것

번호 즉 색인은 왼쪽에서 오른쪽으로 위에서 아래로 차례대로 번호를 매겨야 한다.

꽉 찬 이진트리에서 한 수준의 노드 개수는 이전 수준의 두 배이다. 즉 수준 n의 노드 개수는 2^n - 1이다

예를들어 수준 5의 노드 개수는 2^4 16개이다

트리 전체의 노드 개수는 수준들의 개수에 의해 결정된다. 깊이가 n일때 전체노드 개수는 (2^n) - 1이다.

예를들어 4수준 트리의 전체노드 개수는 (2^4) - 1 즉, 15개이다.

 

 

배열로된 이진트리를 운행할 때에는 반복자가 필요없음

1) 임의의 노드의 왼쪽 자식 노드의 색인은 노드 색인의 두배이다.

left=index*2;

2) 임의의 노드의 오른쪽 자식 노드의 색인은 노드 색인의 두배 + 1이다.

right=index*2 + 1;

3) 부모 노드의 색인은 왼쪽 자식 색인을 구하는 공식을 뒤집으면 된다.

parent=index/2;

오른쪽 자식으로 해도 정수나누기 때문에 0.5 절하되기 때문에 사용가능

 

* 배열된 이진트리는 연결된 트리보다 많이 쓰지이진 않음. 공간 때문에

*이진트리의 경우 그냥 포인터를 반복자로 사용해도 되기 때문에 개별적인 반복자 클래스를 만들 필요가 없다.

 

일반트리 구조에도 운행방식이 전위와 후외가 있다. 그런데 이진트리는 한개가 더 있다 중위!

아래는 연결된 이진트리

이진트리의 운행

1) 전위 운행 의사코드 : 자식들 이전에 현재 노드 처리

Preorder(node)

  process(node)

  Preorder(node.left) //자식이 2개 이므로 왼쪽 처리 후 오른쪽 처리함

  Preorder(node.right)

End Preorder

오른쪽 노드보다 왼쪽 노드가 먼저 처리된다

 

**일반트리의 전위운행 의사코드

Preorder(node)

  process(node)

  For each Child   //이진트리와는 다른점이 여기다. 일반 트리에선 자식개수를 모르니 for문으로 순회

  Preorder(child)

  End For

End Preorder

 

 

2) 후위 운행 의사코드 : 자식들 이후에 현재 노드 처리

Postorder(node)
  Postorder(node.left) //자식이 2개 이므로 왼쪽 처리 후 오른쪽 처리함

  Postorder(node.right)

  process(node)

End Postorder

자식들을 먼저 처리하고 난 후에 현재노드를 처리

 

** 일반트리에서의 후위운행

Postorder(node)
  For each Child  //이진트리와는 다른점이 여기다. 일반 트리에선 자식개수를 모르니 for문으로 순회

  Postorder(node.left)

  End For

  process(node)

End Postorder

 

 

3) 중위 운행 의사코드 : 자식 노드들 사이에 현재 노드를 처리

Inorder(node)

  Inorder(node.left)

  process(node) //운행처리코드

  Inorder(node.right)

End Inorder

이 중위 운행은 자료의 정렬에서 쓰이게 됨

** 중위 운행은 일반트리에서는 없음

 

 

---

파싱이란 문장을 좀 더 이해하기 쉬운 조각들로 나누는것을 말한다.

 

산술식이란 말 그대로 어떤 숫자를 계산하기 위한 수식 x=24 + y 이런것..

산술식의 파싱은 자신만의 스크립팅 시스템을 만들기 위한 첫 걸음.

 

2*(y/z) 산술식을 보자

각 연산자(나누기, 또는 곱셈) 의 왼쪽, 오른쪽에는 각각 하나의 항이 있다.

즉, 이진트리이다.

연산자를 하나의 노드로 생각하고 양쪽의 항을 각각 좌우 자식노드라 하면됨.

 

놀랍게도 이진트리로 만든 후 후위운행을 하면 산술식이 계산이 됨.

 

재귀적인 하향식 산술식 파싱 만들기

첫째 산술식을 토큰들의 목록으로 만드는것. enum

* union은 변수들 중 가장 큰 값의 메모리를 공용해서 사용함. 그래서 구조체와는 다른 구조체는 각각 다른 메모리 사용

 

둘쨰 스캐닝

텍스트 문자열을 토큰들의 스트림으로 변환하는 공정을 스캐닝 또는 토큰화라고 함(스캐닝 함수)

스캐닝을 수행하는 스캐너는 표현식의 각 부분을 하나의 문자열로 읽어 들이고 그 부분이 무엇인지 즉 연산자인지 아니면 변수나 괄호인지를 판단

순서

1. 문자 하나를 읽는다.

2. 그 문자가 네 변수 중 하나이면 그에 해당하는 변수 토큰을 생성

3. 그 문자가 네 연산자들 중 하나이면 그에 해당하는 연산자 토큰을 생성

4. 그 문자가 숫자이면 숫자의 나머지를 다 읽어 들이고 그에 해당하는 숫자 토큰을 생성

5. 토큰을 대기열에 넣는다.

6. 이를 산술식 끝까지 반복

 

셋째 파싱

산술식은 2가지 형태이다.

1. 하나의 상수 또는 변수

2. 연산자 좌, 우에 두 상수 또는 변수들이 있는 형태

파서의 임무는 토큰들의 대기열에서 토큰들을 뽑아 하나의 이진 트리로 구축하는 것이다.

파서는 하나의 재귀함수이다.

*의사코드

아까 위 스캐닝부분에서 대기열에 넣은것을 이번 파서에서 하나씩 받아서 트리를 돌려준다.

Tree Parse(Queue)

Tree left, center, right //세개의 트리 노드들

IF Queue.First==LPAREN //왼쪽 괄호일떄 1

Queue.Dequeue //괄호를 제거함 1

left=Parse(Queue) //괄호를 제거한 나머지를 다시 파서에 넣는다.(결과는 왼쪽 트리에 저장됨) 1

Queue.Dequeue //1-1

Else IF Queue.First==VARIABLE or NUMBER //변수 또는 숫자일때 3

left=VARIABLE or NUMBER

Queue.Dequeue //3

 

IF Queue.Empty or Queue.Front == RPAREN //3

return left

 

IF Queue.Front == OPERATOR //4

center=OPERATOR

Queue.Dequeue

 

IF Queue.First==LPAREN //4

Queue.Dequeue;

right=Parse(Queue)

Queue.Dequeue

Else IF Queue.First==VARIABLE or NUMBER //4

right=VARIVABLE or NUMBER

Queue.Dequeue

 

cetner.left=left

center.right=right

return cetner

 

대기열의 첫 번째 토큰은 왼쪽 괄호이거나 변수 또는 숫자 이어야한다.

첫 번쨰 토큰이 왼쪽 괄호이면 그 괄호를 열에서 제거하고 대기열의 나머지를 다시 파서에 넣는다. // 1

그 재귀 호출의 결과는 왼쪽 트리 노드에 저장된다.  //1

재귀 호출된 파서는 첫 번째 왼쪽 괄호 이후부터 그에 해당하는 오른쪽 괄호 직전까지를 대기열에서 뽑아낼 것이므로 호출이 끝난 후의 대기열의 첫 번째 토큰은 오른쪽 괄호가 된다. //1

재귀가 끝나면 대기열의 첫 번째가 오른쪽 괄호로 됨..그때 그 오른쪽 괄호도 대기열로부터 뽑아낸다. //1-1

 

첫 번째 토큰이 변수나 숫자(상수)이면 왼쪽 트리 노드는 말단 노드가 되며, 그 노드에는 첫 번쨰 토큰의 변수 또는 숫자가 담긴다. 그런 다음에는 토큰을 대기열에서 제거한다. // 3

이러면 첫 번쨰 토큰에 대한 처리가 끝난 것이다.

 

그런 다음에는 현재의 항이 하나의 변수나 숫자인지 아니면 연산자들 중심으로하는 두 변수 또는 숫자인지, 괄호인지 판단 후 위와 같은 재귀를 실행한다. //4

 

 

넷째 트리의 수행

트리가 만들어졌다면 실제의 계산 결과가 나와야한다. 후위 운행을 하면 나온다.

트리 자체가 재귀적인 자료구조이므로 트리를 사용하는 함수들 역시 자연스럽게 재귀적으로 되야한다.

후위운행으로 트리를 평가

float Evaluate(BinaryTree<Token>* p_tree)
 {
  if (p_tree == nullptr)
  {
   return 0.0f;
  }

  float left = 0.0f;
  float right = 0.0f;

  switch (p_tree->m_data.m_type)
  {
  case VARIABLE:
   return p_tree->m_data.m_varibale;
   break;
  case NUMBER:
   return p_tree->m_data.m_numver;
   break;
  case OPERATOR:
   left = Evaluate(p_tree->m_left);
   right = Evaluate(p_tree->m_right);
   switch (p_tree->m_data.m_oeprator)
   {
   case 0:
   case 1:
    break;
   }
  }
  return 0.0;
 }