[데이터 구조] 접미사 식 구조 이 진 트 리 를 접미사 식 으로 변환 합 니 다.

#include "stdio.h"  
#include "string.h"  
#include "stdlib.h"  
#include "stack"  
using namespace std;  
  
const char str[] = "3*4+5-2/1";  
  
struct tree  
{  
    char c;  
    struct tree* left;  
    struct tree* right;  
};  
stack subTreeStack;  
stack operatorStack;  
  
  
struct tree*  BuildTree()  
{   
  
    struct tree* node;  
    for (unsigned int pos = 0; pos < strlen(str); pos++)  
    {  
        if (str[pos] - '0' >= 0 && str[pos] - '0' <= 9)    //             
        {  
  
            node = (struct tree*) malloc(sizeof(struct tree));  
            node->c = str[pos];  
            node->left = NULL;  
            node->right = NULL;  
              
          
              
            subTreeStack.push(node);  
        }  
        else if (str[pos] == '*' || str[pos] == '/' || str[pos] == '+' || str[pos] == '-')  
        {  
            if (!operatorStack.empty() && (str[pos] == '+' || str[pos] == '-'))  //            
            {  
                node = (struct tree*) malloc(sizeof(struct tree));  
                node->c = operatorStack.top();  
                node->right = subTreeStack.top();  
                subTreeStack.pop();  
                node->left = subTreeStack.top();  
                subTreeStack.pop();  
                  
                subTreeStack.push(node);  
              
  
                operatorStack.pop();  
                operatorStack.push(str[pos]);  
            }  
            else  
                operatorStack.push(str[pos]);  
        }  
      
      
    }  
      
      
    while(!operatorStack.empty())  
    {  
      
        node = (struct tree*) malloc(sizeof(struct tree));  
        node->c = operatorStack.top();  
        operatorStack.pop();  
        node->right = subTreeStack.top();  
        subTreeStack.pop();  
        node->left = subTreeStack.top();  
        subTreeStack.pop();  
          
        subTreeStack.push(node);  
      
    }  
    return subTreeStack.top();  
  
}  
void PrintTree(struct tree* node)  
{  
    if (node == NULL)  
        return;  
    PrintTree(node->left);  
    printf("%c", node->c);  
    PrintTree(node->right);  
}  
  
  
void main()  
{  
    struct tree* root = BuildTree();  
    PrintTree(root);  
}