#include<iostream.h>
#include<string.h>
#include<stdlib.h>
#include<conio.h>
#include"stack.hpp"
#include"namedpolynomial.hpp"


template<class Type>
class Calculator
{
public:
	Calculator(){}//Constructor
	void Run();   //多項式的執行函數
	void Clear(); //清空運算數棧s中的內容
private:
	void getOperand();//取得計算器要運算的多項式
	bool isOperator(char ch);//判斷輸入的字符是否為運算符
	bool isIdentifier(char ch);//判斷輸入的字符是否合法的標識符
	void postfix(char p[],char q[]);//將中序表達式轉化為后續表達式
	int icp(char ch);//判斷一個運算符的棧外優先數
	int isp(char ch);//判斷一個運算符的棧內優先數
	void AddOperand(Type value);//運算數進棧
	bool Get2Operands(Type& left, Type& right);//從運算數棧中取兩個運算數作運算
	void DoOperator(char op);//作運算
	
	Stack<Type> s;//暫存運算數的堆棧
	Type* operand;//用戶輸入的運算運算數數組，運算數堆棧將從這里取得符合要求的運算數進棧
	int operandscount;//計算某次計算中計算器總共有幾個不同運算數
};

//////////////////////////////////////////////////////////////////////
template<class Type>
void Calculator<Type>::AddOperand(Type value)
{
	//運算數進棧
	s.Push(value);
}
//////////////////////////////////////////////////////////////////////
template<class Type>
bool Calculator<Type>::Get2Operands(Type& left,Type& right) 
{
	//從運算數棧中取兩個運算數作運算
	if(s.IsEmpty())
	{
		cerr<<"Missing Operand!"<<endl;
		return false;
	}
	right = s.Pop();
	if(s.IsEmpty())
	{
		cerr<<"Missing Operand!"<<endl;
		return false;
	}
	left=s.Pop();
	return true;
}
//////////////////////////////////////////////////////////////////////
template<class Type>
void Calculator<Type>::DoOperator(char op)
{
	Type left, right;
	bool result;
	result=Get2Operands(left,right);
	if(result == true)
	switch(op)
	{
		case '+':  { s.Push(left+right);  break; }
		case '-':  { s.Push(left-right);  break; }
		case '*':  { s.Push(left*right);  break; }
		default:   
			{
				cerr<<"Error!This operation is not defined!"<<endl;
				Clear();
				exit(1);
			}
	}
	else
		Clear();
}
//////////////////////////////////////////////////////////////////////
template<class Type>
void Calculator<Type>::Clear()
{
	s.MakeEmpty();
}
//////////////////////////////////////////////////////////////////////
template<class Type>
int Calculator<Type>::icp(char ch)
{
	//輸出運算符的棧外優先數
	switch (ch)
	{
	    case '=':  return 0;
        case '(':  return 8;
        case '^':  return 6;
        case '*':  
		case '/':  
		case '%': return 4;
        case '+':   
		case '-': return 2;
        case ')': return 1;
    }
	return -1;
}
//////////////////////////////////////////////////////////////////////
template<class Type>
int Calculator<Type>::isp(char ch)
{  
	//輸出運算符的棧內優先數
    switch (ch)
	{
        case '=':  return 0;
        case '(':  return 1;
        case '^':  return 7;
        case '*':  
		case '/':  
		case '%':  return 5;
        case '+':  
		case '-':  return 3;
        case ')':  return 8;
    }
	return -1;
}
//////////////////////////////////////////////////////////////////////
template<class Type>
void Calculator<Type>::Run()
{
	//數組p存放轉化后的后序表達式，q存放原來的中序表達式
	char p[100],q[100];
	getOperand();//先取得所作運算的運算對象
	
	//提示用戶輸入運算對象之間的運算表達式
	cout<<"請輸入所要作的運算的表達式:"<<endl;
	
	//postfix函數將讀入運算的中序表達式，并將它轉化為相應的后序表達式
	//在轉化后的后序表達式中，運算對象之間，運算對象與運算符之間用空格
	//分開，以便下面的while循環解析不同的多項式名，從而在operand數組中取得
	//所需要的運算多項式
	postfix(p,q);

	while( (p[0] != '=') && (p[0]!='\0'))//掃描后序多項式,'='為運算結束標志
	{
		int n=strlen(p);//求得后序多項式字符串的長度
		//如果串的首字符是'+' '-' '*'之一，則執行已經運算
		if( (p[0] == '+') || (p[0] == '-') || (p[0] == '*'))
		{
			DoOperator(p[0]);//執行運算
			//當前運算已完成，將后序表達式串中的內容前移，消去已做的運算符
			//即將字符串中后面n-1個字符(除去已上面已做的運算的運算符)復制到
			//字符串前面
			strncpy(p,p+1,n-1);
		}

		//如果串的首字符是標識符，在operand數組中搜索名字與當前后序
		//表達式的運算對象名字一致的多項式，并執行讀取運算數入棧的工作
		else if( isIdentifier(p[0]) )
		{
			//字符數組記錄當前后序表達式的運算對象的名字
			char* m=new char[100];
			
			//以下語句段將當前后序表達式的運算對象的名字復制到字符串m中
			m[0] = p[0];
			for(int i=1;p[i]!=' ';i++)
				m[i]=p[i];
			m[i]='\0';
			//用m串創建一個String對象
			String s=m;

            //在operand數組中搜索名字與當前后序表達式的運算對象名字
		    //一致的多項式，并執行讀取運算數入棧的工作
			for(int j=0;j<operandscount;j++)
			{
				if( s==operand[j].getName() )
					AddOperand(operand[j]);
			}

			strncpy(p,p+i+1,n-i-1);//當前運算已完成，將后序表達式串中的內
			//容前移，移除已進棧的運算數即將字符串中后面n-i-1個字符(除去已
			//上面已進棧的運算數)復制到字符串前面
		}
		else
		{
			cerr<<"Error!Unknown charactor "<<p[0]<<"!The Calculator can't do it!"<<endl;
			exit(1);
		}
	}
	assert(!s.IsEmpty());//若棧底無數，錯誤！終止
	cout<<"結果多項式:"<<endl;
	cout<<q<<"="<< s.Pop().getPoly()<<endl;//輸出結果（棧底元素）
}
//////////////////////////////////////////////////////////////////////
template<class Type>
void Calculator<Type>::postfix(char p[],char q[])
{
	//將中序表達式轉化為后續表達式，轉化后的后序表達式存于數組p中轉化前
	//的中序表達式存放于q中，兩個數組返回Run中繼續執行計算器的運算
	
	Stack<char> s;//存放運算符的堆棧
	char ch,y;
	int i=0,j=0;//數組p和q的計數器
	s.MakeEmpty();
	s.Push('=');//先將等號進棧
	
	//輸入中序表達式，以'='為結束標志
	while(cin>>ch,ch!='=')
	{
		q[j++]=ch;//記錄中序表達式的內容進數組q
		//判斷輸入的字符，如果是合法的表示符類型，直接將它記入數組p中
		if(isIdentifier(ch))
		{
			p[i]=ch;
			i++;
		}
		//如果輸入字符是')'
		else if(ch==')')
		{
			//首先判斷數組p中的最后一個字符是否表示符，如果是則插入空格
			//以便將計算對象－多項式的名字與運算符分隔開
			if(isIdentifier(p[i-1]))
			{
				p[i]=' ';
				i++;
			}
			//連續從運算符棧中退出運算符，直至'('為止
			for(y=s.GetTop();y!='(';y=s.GetTop())
			{
				s.Pop();
				p[i]=y;
				i++;
			}
			s.Pop();//最后將'('也從棧中退出
		}
		
		//如果輸入的字符是運算符
		else if(isOperator(ch))
		{
			//如果該運算符是'('，并且數組p中的最后一個字符是標識符
			//則在p數組中插入一個空格作為分隔
			if((ch!='(') && isIdentifier(p[i-1]))
			{
				p[i]=' ';
				i++;
			}

			//改運算符是其他類型，比較運算符棧的棧頂元素與當前輸入的運算符
			//的優先數，如果棧頂運算符的isp大于當前輸入字符的icp，則不斷從
			//棧中退出運算符，直至棧頂運算符的isp>當前輸入運算符的icp為止
			for(y=s.GetTop();isp(y)>icp(ch);y=s.GetTop())
			{
				s.Pop();
				p[i]=y;
				i++;
			}
			//最后當棧頂運算符的isp不再大于當前輸入字符的icp，則將ch進棧
			s.Push(ch);
		}
		else //否則輸入字符不合法，提示并中止程序
		{
			cerr<<"Error!未知字符 "<<ch<<" 被輸入！運算器無法完成計算！"<<endl;
			exit(1);
		}
	}
	//判斷數組p中的最后一個字符是否表示符，如果是則插入空格
	if(isIdentifier(p[i-1]))
	{
		p[i]=' ';
		i++;
	}
	//最后從運算符棧中連續退出運算符存入p數組中，以完成后序表達式的轉換
	while(!s.IsEmpty())
	{
		y=s.Pop();
		p[i]=y;
		i++;
	}
	//為p和q數組加上字符串結束符
	q[j]='\0';
	p[i]='\0';
}
//////////////////////////////////////////////////////////////////////
template<class Type>
bool Calculator<Type>::isIdentifier(char ch)
{
	//判斷輸入的字符是否合法的標識符，合法的表示符由數字，字母和下劃線組成
	if( ((ch>='a')&&(ch<='z')) || ((ch>='A')&&(ch<='Z')) || ((ch>='0')&&(ch<='9'))||(ch=='_'))
		return true;
	else 
		return false;
}
//////////////////////////////////////////////////////////////////////
template<class Type>
bool Calculator<Type>::isOperator(char ch)
{
	//判斷輸入的字符是否為運算符
	switch(ch)
	{
	case '+':
	case '-':
	case '*':
	case '(':
	case ')':return true;
	}
	return false;
}
//////////////////////////////////////////////////////////////////////
template<class Type>
void Calculator<Type>::getOperand()
{
	//取得計算器要運算的多項式
	cout<<"您總共需要輸入多少個多項式作為計算對象?請輸入:"<<endl;
	cin>>operandscount;
	operand=new namedPolynomial[operandscount];
	
	for(int i=1;i<=operandscount;i++)
	{
		cout<<"輸入多項式"<<i<<":"<<endl;
		cin>>operand[i-1];
	}
	
}
//////////////////////////////////////////////////////////////////////
//主函數
void main()
{
	cout<<"本程序為多項式計算器。用于完成多項式的加，減，乘等多項式的復合運算。"<<endl;
	cout<<endl;
	cout<<endl;
	cout<<"程序即將開始。若要啟動多項式計算器請按任意鍵。"<<endl;
	cout<<endl;
	cout<<endl;
	getch();

	char y='y';
	while(y=='y')
	{
		Calculator<namedPolynomial> a;
	    a.Run();
		cout<<endl;
		cout<<endl;
		cout<<"需要繼續做其他多項式運算嗎?y－繼續，n－退出。請輸入你的選擇:"<<endl;
		cin>>y;
	}

	cout<<endl;
	cout<<endl;
	getch();
	cout<<"多項式計算器程序結束!感謝使用!"<<endl;
	cout<<endl;
	cout<<endl;
}