#include <malloc.h>
#include <stdlib.h>
#include <iostream>
#include <stdlib.h>

using namespace std;

typedef struct tree                // 트리 구성을 위한 구조체 선언부 //
{                               
    char ch;                    // ch : 입력된 후위표현식의 문자값 //   
    int peano;                    // peano : 각 노드 단에서의 peano값 //
    struct tree *left;            // left : 트리의 왼쪽 자식 노드를 가리키는 포인터 //
    struct tree *right;            // right : 트리의 오른쪽 자식 노드를 가리키는 포인터 //
} node;

const int MAX = 100;            /* 트리를 구성하는 자료 구조인 배열의 Max값 정의 */

// 큐 클래스 선언 //


class Queue
{
    public:

      void Queue::init_queue(void)   //Queue를 초기화하는 부분
      {
           front=rear=0;
      }
     
      node Queue::put(node k)   // Queue 구조안에 값을 넣는 put
      {
          if((rear+1)%MAX==front)
          {
                cout<<"\nQueue overflow.";
                return NULL;
          }
            queue[rear]=k;
            rear=++rear%MAX;
            return k;
      }
      node Queue::get(void)  // Queue에서 front값을 얻는다.
      {
             node *i;
            if(front==rear)
            {
                cout<<"\nQueue underflow.";
                return NULL;
            }
            i=queue[front];
            front=++front%MAX;
            return i;
      }

      int Queue::is_queue_empty(void) // Queue가 비어있는지 확인
      {
        return (front==rear);
      }
      protected:                 // Queue 클래스에서 사용되는 변수 선언
          node *queue[MAX];
          int front;
          int rear;
};

// 스택 클래스 선언 //

class Stack
{
    public:
    void Stack::init_stack(void)  //Stack을 초기화
    {
          top=-1;                  // Stack의 top을 -1로 초기화
    }
    node Stack::push(node *t)  // Stack에 Push
    {
        if(top>=MAX-1)            //top의 값이 MAX보다 -1 작을 때
        {
            cout<<"\nStack overflow.";    //Stack이 크기를 초과하는 overflow
            return NULL;
        }
            stack[++top]=t;
            return t;
    }

    node Stack::pop(void) //Stack을 Pop
    {
        if (top<0)            //top이 0보다 작으면 Stack underflow 발생
        {
            cout<<"\nStack underflow.";
            return NULL;
        }
        return stack[top--];
    }
    int Stack::is_stack_empty(void) //Stack이 비어있는지 확인한다.
    {
        return (top=-1);
    }

    protected:
        node *stack[MAX];
        int top;
};

// parse_tree 구성 클래스 선언 //

class ParseTree:public Stack,public Queue
{
    public:
    void ParseTree::init_tree(void)
    {
        node head=new node;
        node tail=new node;
        head->left=tail;
        head->right=tail;
        tail->left=tail;
        tail->right=tail;
    }

    int ParseTree::infix_operator(int k)
    {
        return (k =='.');
    }
    int ParseTree::max(int a, int b)
    {
        if(a>=b) return a;
        else return b;
    }

    node ParseTree::*make_parse_tree(char *p)
    {
        node *t;
        while(*p)
        {
            while(*p==' ')
            p++;
            node t=new node;
            t->ch=*p;
            t->left=tail;
            t->right=tail;
            t->peano=-1;
            if(infix_operator(*p))
            {
                t->right=pop();
                t->left=pop();
                t->peano=max(t->left->peano,(t->right->peano+1));
            }
            push(t);
            p++;
        }
        return pop();
    }

    int ParseTree::is_legal(char *s)
    {
        int f=0;
        while(*s)
        {
            while(*s==' ')
                s++;
            if(infix_operator(*s))
                f--;
            else
                f++;
            if(f<1) break;
                s++;
        }
        return (f=1);
    }

    void ParseTree::visit1(node *t)
    {
        int Pl;
        Pl=t->peano;
        if(Pl>0)
        {
            while(Pl>0)
            {
                --Pl;
                printf("%c",t->ch);
            }
        }
        else if(Pl==0)
        {
        }
        else if(Pl==-1)
        {
            printf("%c",t->ch);
        }
        else
        {
            printf("%c",t->ch);
        }
    }
    void ParseTree::visit2(node *t)
    {
        printf("%c",t->ch);
    }

    void ParseTree::preorder_traverse(node *t)
    {
        if(t!=tail)
        {
            visit2(t);
            preorder_traverse(t->left);
            preorder_traverse(t->right);
        }
    }
    void ParseTree::peanot_traverse(node *t)
    {
        if(t!=tail)
        {
            peanot_traverse(t->left);
            visit1(t);
            peanot_traverse(t->right);
        }
    }
    void ParseTree::postorder_traverse(node *t)
    {
        if(t!=tail)
        {
            postorder_traverse(t->left);
            postorder_traverse(t->right);
            visit2(t);
        }
    }

    void ParseTree::levelorder_traverse(node *t)
    {
        put(t);
        while(!is_queue_empty())
        {
            t=get();
            visit2(t);
            if(t->left!=tail)
                put(t->left);
            if(t->right!=tail)
                put(t->right);
        }
    }
    node *head,*tail;   

};