#include<iostream>
#include<vector>
#include<string>
#include <cmath> 
using namespace std;
const double PRECISION = 1E-6;		//精度，以防在做一些除法運算時由于精度問題導致出錯

/*遞歸函數Compute*/
/*************************************************************************/
/*一 遞歸算法值得注意考慮的地方
	  1 遞歸中需要考慮臨時變量的生存時間，在遞歸函數中定義到的臨時變量，其實質上相當于在
		不同的函數定義了一個相同的變量名 如int a；這個變量在每一層遞歸中都重新賦值，而在
        每一層遞歸結束時，返回到上一層，該變量則又從堆棧中返回，這是遞歸的巧妙之處，該遞
		歸返回可以用于回溯一路過來的數據
	  2 再說臨時變量問題，由于臨時變量僅在每一層遞歸中存在一個值，在深一層其會重新由于定
        義而重新被初始化，所以其值如果要在下一層利用，則需要用一個全局變量（我覺得用遞歸
		的形式參數可以）把它存儲起來，然后在深一層遞歸中利用。例如對下面的變量c,利用了vector
        存儲起來。而對于返回時，由于“錯位”（個人認為叫錯位）導致返回時的變量不是同一層次時
        如下面Compute函數，如果僅僅設置一個變量Exp，兩者在合成一個表達式Exp后，由于合并在上一層，
		而如果返回的話，得到的結果將會覺得不是同一層次的數據，而且無法把它分離開重新調用遞歸，
		故需要設置變量把其分離開Exp1，Exp2，這樣的話，返回的a，b 將和Exp1，Exp2在同一層次，
		可以很好把表達式列出來
	  3	到目前的程序為止，都是將遞歸中的形式參數作為該遞歸函數的“全局變量”，用于存儲數據進入
		深一層的遞歸，如Number，Exp
  二，利用遞歸的思想考慮問題
	  到目前為止所編寫的利用遞歸思想進行的算法，包括字符排列，漢諾塔，24點算術等，這些問題中
	  都要考慮到一個問題的相似性，如字符排列的去一字符對余下字符進行全排列，漢諾塔的經典遞歸，
	  24點算術中遞歸對所有可能的算術結果，這些問題都是比較循環得到，只是在各層遞歸中，所進行
	  一些操作不同，包括遞歸中的循環，遞歸中的排列等。
  三 一些小問題
		遞歸函數的bool值，返回利用一層一層的返回return true/false，要注意的是要保證出口唯一而
		且一定存在出口，小心忘記return false，最好把這句放到遞歸的最后一層，還有函數的結束，因為
		如果遞歸結束時是返回上一層的最后一行程序，所以可以很好的返回上一層的遞歸結果
*/

/*思想：a,b,c,d => a,b,(c+*-/d)=>a,b,c=>a,c=>c==Ans?然后逐層返回計算
*/
bool Compute_Ans(vector<double>Number,string Exp,int Ans,int Con_record = 0)	
{
	if(Number.size() == 1)
	{
		if(fabs(Number[0]-Ans)<PRECISION)
		{
			cout<<"Success..."<<endl;
			cout<<Exp<<" = "<<Ans<<endl;
			return true;
		}
		else
		{
			return false;
		}
	}
	else
	{
		string Exp1,Exp2;
		double a,b,c;
		char ch_a,ch_b;
		Exp1 = Exp;

		a = Number[Number.size()-1];
		ch_a = a+48;
		Number.pop_back();
		b = Number[Number.size()-1];
		ch_b = b+48;
		Exp2 = ch_b;
		Number.pop_back();
		c = a+b;
		Number.push_back(c);

		if(Con_record>0)
		{
			Exp1 = ch_a;
		}
		Exp = '('+Exp1+'+'+Exp2+')';
		if(Compute_Ans(Number,Exp,Ans)) return true;
		
		Number.pop_back();
		c = a*b;
		Number.push_back(c);
		Exp = '('+Exp1+'*'+Exp2+')';
		if(Compute_Ans(Number,Exp,Ans)) return true;

		Number.pop_back();
		{
			if(a>b)
			{
				c = a-b;
				Number.push_back(c);
				Exp = '('+Exp1+'-'+Exp2+')';
			}
			else
			{
				c = b-a;
				Number.push_back(c);
				Exp = '('+Exp2+'-'+Exp1+')';
			}
		}
		if(Compute_Ans(Number,Exp,Ans)) return true;

		Number.pop_back();
		if(fabs(b)>PRECISION)
		{
			c = a/b;
			Number.push_back(c);
			Exp = '('+Exp1+'/'+Exp2+')';
			if(Compute_Ans(Number,Exp,Ans)) return true;
		}

	 	Number.pop_back();
		if(fabs(a)>PRECISION)
		{
			c = b/a;
			Number.push_back(c);
			Exp = '('+Exp2+'/'+Exp1+')';
			if(Compute_Ans(Number,Exp,Ans)) return true;
		}
	}
	return false;
}

/*Insert_Char函數用于在某一位置插入字符*/
void Insert_Char(char c1,string &str,int i)
{
	if(i == 0)
	{
		str = c1 + str;
	}
	else
	{
		string Temp_str = str.substr(i);
		str.erase(i,str.size()-i);
		str = str + c1 +Temp_str;
	}
}
/*Rotate 函數用來對所輸入的數字進行全排列，利用的是非遞歸的全排列方式，主要是因為在某一情況下
計算算式中已經利用到了遞歸的方法，故另外利用函數編寫一個非遞歸的，可以從中調用遞歸函數，而且這
樣會減少占用?？臻g
對輸入數字進行全排列的方法是：1首先對下標進行全排列。
							  2然后將各個數字按所排列好的下標取數字即可得到某一數列的全排列
*/
void Rotate(vector<double>Number,string Exp,int Ans,int Con_record)
{
	int count = Number.size();
	
	vector<string>temp;
	vector<string>store;

	store.push_back("0");
	
	string T_Str;
	char ch_i;

	for(int i = 1;i<count;i++)  //遞推方法 隔位插入字符，得到全排列
	{
		for(int j = 0;j<store.size();j++)
		{
			T_Str = store[j];
			for(int t = 0;t<=store[j].size();t++)
			{
				ch_i = i+48;
				Insert_Char(ch_i,T_Str,t);
				temp.push_back(T_Str);
				T_Str = store[j];
			}
		}
		while(!store.empty())
		{
			store.pop_back();
		}
  		store = temp;
		while(!temp.empty())
		{
			temp.pop_back();
		}
	}
//以上得出下標排列
	
	vector<double>Sort_Number;
	int T_int;
	bool test = false;
	for(i = 0;i<store.size();i++)
	{
		for(int j = 0;j<Number.size();j++)
		{
			T_int = store[i][j];
			T_int = T_int-48;
			Sort_Number.push_back(Number[T_int]);
		}
		if(Compute_Ans(Sort_Number,Exp,Ans,Con_record))
		{
			test = true;
			break;
		}
		while(!Sort_Number.empty())
		{
			Sort_Number.pop_back();
		}

	}
	if(!test)
		cout<<"Fail To Compute..."<<endl;

}