棧-表達式求值

表達式求值是程式設計語言編譯中的一個最基本問題。它的實作是棧應用的有一個典型例子。

這裡使用算符優先法。

輸入:一個表達式.

輸出：輸出其字尾表達式并且進行表達式的求值。

運作結果：

算法思想：

拿目前掃描的運算符号與上一個比較優先級，目前掃描符号低或相等則進行上一個運算，需取最近的兩個數。否則掃下個。

設操作符棧與操作數棧，運算符棧最初壓如‘#’，逐個掃描符号。遇操作數則直接入棧，繼續讀下一字元。遇運算符則與棧頂運算符比較優先級，目前運算符優先級高，前面的運算還不應執行，則目前運算符入棧，讀下一符号。否則棧頂運算符出棧，兩操作數出棧，進行運算，所得結果入數棧，開始下次循環，不掃描新符号，重新比較剛才掃描到的運算符，與新棧頂運算符。如此重複直到棧頂運算符與目前符号均為#。

字尾表達式：對于掃描到的數字除了入數棧之外，同時入到另一個用于求字尾表達式的PEXP，當執行一次運算時，将執行的算符同時壓入PEXP中，所有運算結束後，從棧底到棧頂輸出序列即為表達式的字尾表達式。

現在還有一個問題：表達式中肯定有小數或者多位數，不一定是個位數，我們需要表示它們。首先定義一個c1字元表示上一個字元，如果上一個字元是.說明正在讀取一個小數，然後用flag計算小數的位數，出現小數後就修改棧頂元素。反之，如果上一個元素是整數，說明讀取的是一個多位數，就計算并修改棧頂元素。如果是個位數直接壓入棧即可。

首先給出輔助函數：

判定運算符的棧頂運算符與讀入的運算符之間優先關系。

char Precede(char c1,char c2){
	//判定運算符的棧頂運算符與讀入的運算符之間優先關系
    char c;
    switch(c1){
        case '+':
        case '-':
	    switch(c2){
	        case '+':
                case '-':
	        case ')':
                case '#':
		    c='>';
                break;
	        default:
		    c='<';
	    }
        break;
        case '*':
        case '/':
            if(c2=='(')
		c='<';
	    else
		c='>';
            break;
        case '(':
	    if(c2==')')
		 c='=';
	    else
		 c='<';
            break;
        case ')':
	    c='>';
            break;
        case '#':
	    if(c2=='#')
		c='=';
	    else
		c='<';
    }
    return c;
}
           

進行二進制運算 a theta b。

double Operate(double a,char theta,double b){
	//進行二進制運算 a theta b
	double sum;
    switch(theta)
    {
       case '+':
	   sum=a+b;
	   break;
       case '-':
	   sum=a-b;
	   break;
       case '*':
           sum=a*b;
           break;
       case '/':
           sum=a/b;
	   break;
    }
    return sum;
}
           

判斷是不是運算符.

Status In(char c,char *OP){
    //判斷是不是運算符
    for(int i=0;i<7;i++)
       if(c==OP[i])   //是運算符
          return TRUE;
    return FALSE;
}
           

算法實作：

double EvaluateEvaluation(char * s){
    //進行多項式的求值以及字尾表達式的輸出
    int i=0,len,flag=0;
    double a,b,sum;
    char c1=s[0],e;
    char OP[7]={'+','-','*','/','(',')','#'}; //運算符數組
    SqStack<char> OPTR; //運算符棧
    SqStack<double> OPND; //運算數棧
    SqStack<char> PEXP;     //字尾表達式棧
    InitStack(OPTR); //初始化棧
    InitStack(OPND);
    InitStack(PEXP);
    len=strlen(s);
    s[len]='#';
    s[len+1]='\0';
    Push(OPTR,'#');//壓入一個‘#’
    while(s[i]!='#'||GetTop(OPTR)!='#'){ //掃描每一個字元 如果同為‘#’退出循環
        if(!In(s[i],OP)){ //如果不是運算符
            Push(PEXP,s[i]);
	    if(In(s[i+1],OP)) //如果後一個字元是運算符壓入一個空格
		Push(PEXP,' ');
            if(c1=='.') //如果上一個字元是小數點
	        flag++;
	    if(flag) {
		SetTopElem(OPND,GetTop(OPND)+(double)(s[i]-'0')/pow(10,flag));//修改棧頂元素
		flag++;
            }
            if(s[i]!='.'&&!flag){
                if(!In(c1,OP)&&!StackEmpty(OPND))//如果上一個字元是數字，修改棧頂元素
                    SetTopElem(OPND,GetTop(OPND)*10+s[i]-'0');
                else//否則壓入運算數棧
                     Push(OPND,(double)(s[i]-'0'));
	    }
            c1=s[i++]; //讀取下一個字元
	}
        else{//如果是運算符
            flag=0;
            switch(Precede(GetTop(OPTR),s[i])){
                 case '>':  //目前運算符優先級低
	             Pop(OPTR,e); //運算符出棧
	             Pop(OPND,b);
                     Pop(OPND,a);
	             Push(PEXP,e);
	             Push(OPND,Operate(a,e,b)); //将計算結果壓入運算符棧
                     break;
                 case '=': //優先級相等
	             Pop(OPTR,e); //彈出運算符棧頂元素
	             c1=s[i++];
                     break;
                 case '<':
	             Push(OPTR,s[i]); //目前運算符優先級高 壓入運算符棧
	             c1=s[i++];
                     break;
	     }
        }//else
    }//while
    PrintStack(PEXP);//輸出字尾表達式
    sum=GetTop(OPND);
    DestroyStack(OPTR);
    DestroyStack(OPND);
    DestroyStack(PEXP);

    return sum; //傳回運算數棧頂元素
}//intc