this refers to 윤성우의 열혈 자료구조.

1-1. What is Exprssion Tree???

- 수식 트리란 말 그대로 수식을 트리로 표현을 하는 것을 말한다. 

- 다음 수식 트리를 가지고 연산하는 과정이다. 
- 수식 트리에서 자식은 피연산자라는 사실 !!!!!!!

1-2. 이제 진짜 중위 표기법 수식을 가지고 수식 트리를 만들어 보자.

- 일단 바로 수식트리를 만드는 것은 쉽지 않다.
- 컴퓨터가 계산하기 쉽게 전에 스택을 이용해서 후위 수식으로 바꾸듯이
- 후위 수식으로 바꾸고 수식트리를 만들 것이다. 

This_duplication

/// ADT를 보자 

BTreeNode * MakeExpTree(char exp[]);  //  이 함수는 수식트리 만드는 함수
                                      // 후위 수식을 받어 수식트리를 만들고 루트 주소 값을 반환
int EvaluateExpTree(BTreeNode * bt);  // 수식 트리를 가지고 계산한 값을 반환

void ShowPrefixTypeExp(BTreeNode * bt);   // 전위 표기법 방식을 출력
void ShowInfixTypeExp(BTreeNode * bt);   // 중위 표기법 방식을 출력
void ShowPostfixTypeExp(BTreeNode * bt);   // 후위 표기법 방식을 출력

// 위의 함수는 그냥 수식 트리를 전위, 중위, 후위 탐색하면 각 탐색법에
// 맞게 전위, 중위, 후위 표기법의 수식을 출력할 수 있다.
- 후기 표기법에서 먼저 등장하는 피연산자와 연산자를 가지고 트리 하단부터 윗로 트리를 만들어 간다. 

1-3. 후위 표기법을 수식트리로 하는 과정

  • 스택을 이용한다.
  • 피연산자는 무조건 스택으로
  • 연산자를 만나면 트리로 하도 다시 스택으로, 이 과정을 수식의 최대 길이까지 반복한다.

//위의 과정을 코드로 옮겨보자 

BTreeNode * MakeExpTree(char exp[])
{
  Stack stack;
  BTreeNode * pnode;
  int expLen = strlen(exp);
  
  int i;
  
  for(i = 0 ; i  < expLen ; i++)
  {
     pnode= MakeTreeNode();
     if(!isdigit(exp[i]))  // 피연산자라면
     {
        SetData(pnode, exp[i]-'0') // 정수로 변환을 해서 저장
     }
     else // 연산자면  트리로 만든다. 
     {
        MakeLeftSubTree(pnode, SPop(&stack));
        MakeRightSubTree(pnode, SPop(&stack));
        SetData(pnode, exp[i]);
        //위 순서대로 한다.
     }
     
     // 항상 스택에 푸쉬
    SPush(&stack, pnode);
     
  }
  return SPop(&stack);
}
- 전위 순회하여 데이터 출력 결과    :   전위 표기법 수식
- 중위 순회하여 데이터 출력 결과    :   중위 표기법 수식
- 후위 순회하여 데이터 출력 결과    :   후위 표기법 수식
// 위의 방식들의 데이터 출력 결과를 가지고 수식트리가  제대로 만들어 졌는지 검증 할 수 있다. 

void ShowPrefixTypeExp(BTreeNode * bt)
{
    PreoderTraverse(bt, ShowNodeData);
    // 전위 표기법 수식 출력
}

void ShowInfixTypeExp(BTreeNode * bt)
{
    InoderTraverse(bt, ShowNodeData);
    // 중위 표기법 수식 출력
}

void ShowPostfixTypeExp(BTreeNode * bt)
{
    PostoderTraverse(bt, ShowNodeData);
    // 후위 표기법 수식 출력
}

// 위에 피연산자는 정수로 바꿔서 저장했기 때문에 
// 아래와 같이 구현 
void ShowNodeData(int data)
{
  if(0<= data & data <= 9)
    printf("%d ", data); /// 피연산자 출력
  else
    printf("%c ", data); // 연산자 출력
}

//위를 가지고 main 함수를 구성해보자 

int main (void)
{
    char exp[] = "12+7*";
    BTreeNod * eTree = MakeExpTree(exp);
    
    printf("전위 표기법의 수식: ");
    ShowPrefixTypeExp(eTree); printf("\n");
    
    printf("중위 표기법의 수식: ");
    ShowInfixTypeExp(eTree); printf("\n");
    
    printf("후위 표기법의 수식: ");
    ShowPostfixTypeExp(eTree); printf("\n");
    
    printf("연산의 결과 : %d\n", EvaluateExpTree(eTree));

  return 0;
}

///  위의 main 함수의 결과는 

/// 전위 표기법의 수식 : * + 1 2 7

/// 중위 표기법의 수식 : 1 + 2 * 7

/// 후위 표기법의 수식 : 1 2 + 7 *

/// 연산이 결과 : 21


////// 자 그럼 EvaluateExpTree 함수를 코드로 구현해보자