#include "Stack.h"
#include <iostream>
#include "Priority.h"
using namespace std;

//樹節點的聲明與定義
class Node{
public:
	int oper;
    Node* left;
    Node* right; 
    Node(){left=right=NULL;}
	Node(char op){left=right=NULL;oper=op;}

 };

//表達式語法樹類的聲明
class ExprTree               
{
private:Node *p,*a,*b;
		char Theta;
		LinkStack <char>OperStack;
		LinkStack <Node*>DataStack;
public:Node* t;
       ExprTree();
	   void generateTree(string &exp);
	   int Transfer(char a);
	   void ReTransfer(Node *k);
	   int TraversalSum(Node* k);
	   int cacu(int m,int op,int n);
	   void printtree(Node *t,int i);
	 
};
	
//表達式語法樹類中函數的函數體	

//構造函數,首先將#入棧
ExprTree::ExprTree()
{
	OperStack.Push('#');
}

//語法樹類的構樹函數
void ExprTree::generateTree(string &exp)
{
		Priority compare;
	    int i=0,temp;
		t=NULL;
		while (!OperStack.Empty())
		{
			if (exp[i]<='9' && exp[i]>='0')             //若為數字，則進行入棧處理
			{
				temp=exp[i]-48;
				while (exp[i+1]<='9' && exp[i+1]>='0')
				{
					temp=(temp*10)+(exp[i+1]-48);
					i++;
				}
				p=new Node(temp);
				DataStack.Push(p);
				i++;
			}
			else
			{
				if(exp[i]=='+'||exp[i]=='-'||exp[i]=='*'||exp[i]=='/'||exp[i]=='('||exp[i]==')'||exp[i]=='#') //否則若為運算符,則分情況處理
				{
					switch (compare.PriOPTR(OperStack.GetTop(),exp[i])){
				    case '<':
					   OperStack.Push(exp[i]);
					   i++;
					   break;
				    case '=':
				       OperStack.Pop();
					   i++;
					   break;
				    case '>':
					   Theta=OperStack.GetTop();
					   OperStack.Pop();
					   t=new Node(Transfer(Theta));
					   a=DataStack.GetTop();
					   DataStack.Pop();
					   b=DataStack.GetTop();
					   DataStack.Pop();
					   t->right=a;
					   t->left=b;
					   DataStack.Push(t);
					   break;
					default:
						cout<<"Input Error";
					    cin.clear();     
                        cin.ignore(); 
	                    char a=cin.get();
						exit(0);
				}
				}
				else i++;
			}

		}
		if (DataStack.Empty()){
		cout <<"Input Error";
		cin.clear();     
        cin.ignore(); 
	    char a=cin.get();
		exit(0);
		}

}



//運算符轉換為對應數字的轉換函數
int ExprTree::Transfer(char m)
{
	switch (m)
	{
	case '+':return 1;
	case '-':return 2;
	case '*':return 3;
	case '/':return 4;
	}

}
//數字反轉換為對應該運算符轉換函數
void ExprTree::ReTransfer(Node *k)
{
	if (k->left==NULL&&k->right==NULL)
		cout<<k->oper;
	else switch(k->oper)
		{
		case 1:cout<<"+";break;
	    case 2:cout<<"-";break;
	    case 3:cout<<"*";break;
	    case 4:cout<<"/";break;
		}


}




//計算語法樹的值的函數
int ExprTree::TraversalSum(Node* k)
{
	int m,n;
	if(k==NULL)
	{
		cout<<"Input Error";
	    cin.clear();     
        cin.ignore(); 
	    char a=cin.get();
		exit(0);
	}

	if (k->left==NULL&&k->right==NULL)
	{
		return k->oper;
	}
	if (k->left)
	{
		m=TraversalSum(k->left);
	}
	if (k->right)
	{
		n=TraversalSum(k->right);
	}
	return cacu(m,k->oper,n);
}
//運算符轉換函數2
int ExprTree::cacu(int m,int op,int n)
{
	switch (op)
	{
	case 1:return m+n;
	case 2:return m-n;
	case 3:return m*n;
	case 4:return m/n;
	}

}

//遍歷及打印語法樹
void ExprTree::printtree(Node *t,int i)
{ if(t->right) printtree(t->right,i+1);
   for(int k=1;k<=i;k++)
    cout<<"   ";
    ReTransfer(t);
	cout<<'\n';
 if(t->left)  printtree(t->left,i+1);
}