/**///////////////////////////////////////////////////////////////////////////
  //                      ExpressionCalculator
  //                            Version 0.1
  //                        Powered by nankezhishi
  //                          All Right reserved.
  //      本計算器支持帶括號的四則、乘方運算。并可包含獨立的負號。
  /**///////////////////////////////////////////////////////////////////////////
#include "iostream"
#include "string"
#include "cmath"
using namespace std;

//用于kind的值
#define NUMBER 1000    
#define MYERROR 1001
#define END    1002
//詞法分析器的當前狀態
int state;
//讀取的內容
string input; 
//字符串的長度
int inputlength;
//字符串讀取的位置.
int i = 0;  
//詞法分析器的返回值
int returnvalue;
//讀取到數字時的值 
string strval;
double yylval = 0;

///////////////////////////////////////////////////////////////////////////
//詞法分析器
/**///////////////////////////////////////////////////////////////////////////
bool isdigit(char c){
    return (c >= '0' && c <= '9')?true:false;
}

bool isoperator(char c){
   return (c == '+'||c == '-'||c == '*'||c == '/'||c == '^'||c == '('||c == ')'||c == '=')?true:false;
}

//識別數字的DFA的狀態轉移函數
int move(int state, char c){              
     if (isdigit(c)){
       return (state==0)?1:state;
    }
    else if (state == 1 && c == '.'){
        return 2;
    }
    else if (( state == 2 || state == 1) && (c == ' ' || c == '\n' || c == 0 || isoperator(c))){
        i--;                              //操作符
        return 3;                          //接受
    }
    else
        return 0;
}

int lexer()
{
    if (i == inputlength)
        return END;
    if (isoperator(input[i]))
    {
        i++;
        return input[i-1];        //返回非數字運算符
    }
    int start = i;
    for (;i < inputlength;)
    {
        state = move(state,input[i++]);
        if (state == 0)
            return MYERROR;
        else if (state == 3)
        {
            strval = input.substr(start,i-start);
            yylval = atof(strval.c_str());
            return NUMBER;
        }
    }
}


/**///////////////////////////////////////////////////////////////////////////
//語法分析器采用自上而下的分析方法.
/**///////////////////////////////////////////////////////////////////////////
void match(int t){
    if (returnvalue == t)
        returnvalue = lexer();
    else{
        cout << "EXPRESSION ERRON IN MATCH!" << endl;
    }
}

double E();

double M(){
    double temp;
    switch(returnvalue)
    {
		case NUMBER:
			temp = yylval;
        match(NUMBER);
        return temp;
		case '(':
        match('(');
        temp = E();
        match(')');
        return temp;
    default:
        cout << "EXPRESSION ERROR IN M()!" << endl;
        return 0;
    }
}

double N();

double N_(){
    switch(returnvalue)
    {
    case '+':
    case '-':
    case '*':
    case '/':
    case ')':
    case END:
        return 1;
    case '^':
        match('^');return N();
    default:
        cout << "EXPRESSION ERROR IN N_()!" << endl;
        return 0;
    }
}

double N(){
    double m,n_;
    switch(returnvalue)
    {
    case NUMBER:
    case '(':
        m = M();
        n_ = N_();
        return pow(m,n_);    //這里不可以寫做pow(M(),N_())因為參數壓棧的順序是從右向左,這樣就會先調用N_()而產生錯誤.
    default:
        cout << "EXPRESSION ERROR IN N()!" << endl;
        return 0;
    }
}

double F(){
    switch(returnvalue)
    {
    case '-':
        match('-');return -N();
    case NUMBER:
    case '(':
        return N();
    default:
        cout << "EXPRESSION ERROR IN F()!" << endl;
       return 0;
    }
}

double T_(){
    switch(returnvalue)
    {
    case '+':
    case '-':
    case ')':
    case END:
        return 1;        //對于乘法,這里要返回1.
    case '*':
        match('*');return F() * T_();
    case '/':
        match('/');return 1/(F() / T_());
    default:
        cout << "EXPRESSION ERROR IN T_()!" << endl;
        return 0;
    }
}

double T(){
    switch(returnvalue)
    {
    case NUMBER:
    case '-':
    case '(':
        return F() * T_();
    default:
        cout << "EXPRESSION ERROR IN T()!" << endl;
        return 0;
    }
}

double E_(){
    switch(returnvalue)
    {
    case '+':
        match('+');return T() + E_();
    case ')':
    case END:
        return 0;
    case '-':
        match('-');return -(T() - E_());
    default:
        cout << "EXPRESSION ERROR IN E_()!" << endl;
        return 0;
    }
}

double E(){
    switch(returnvalue)
    {
    case NUMBER:
    case '-':
    case '(':
        return T() + E_();
    default:
        cout << "EXPRESSION ERROR IN E()!" << endl;
        return 0;
    }
}

int main()
{
	cout<<"請輸入一個算數表達式：";
	cin>>input;
	inputlength=input.length();

	state=0;i=0;
	returnvalue=lexer();
	cout<<E()<<endl;
    //while ((cin >> input) && (inputlength = input.length()) > 0)
    //{
    //    state = 0;
    //    i = 0;
    //    returnvalue = lexer();
    //    cout << E() << endl;
    //}

    /**///////////////////////////////////////////////////////////////////////////
    /*詞法分析器測試程序*/
    /**///////////////////////////////////////////////////////////////////////////
    //while (i < inputlength)
    //{
    //   returnvalue = lexer();
    //    if (returnvalue == NUMBER)
    //    {
    //        cout << yylval << endl;
    //    }
    //    else if (returnvalue == MYERROR)
    //    {
    //        cout << "表達式錯誤" << endl;
    //    }
    //    else
    //        cout << (char)returnvalue << endl;
    //}

}