c++-棧的表達式求值應用，中綴轉後綴

棧的表達式求值應用，中綴轉後綴

程序可以運行，但實現不了表達式求值的功能，問題出在哪裡？

最佳回答：

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<stack>

using namespace std;
#define N 1000

char infix[N];  //中綴表達式（未分離，都在一個字符串裡）
char expression[N][10]; //保存預處理過的表達式，也就是每個元素都分離過的表達式
char suffix[N][10];     //保存後綴表達式的操作數
int count;//表達式中元素的個數（一個完整到數字（可能不止一位數）或者符號）
int suffixLength;//後綴表達式的長度

int level(char a){
    switch(a){
    case '#':return 0;
    case '+':
    case '-':return 1;
    case '*':
    case '/':return 2;
    case '^':return 3;
    default:break;
    }
    return -1;
}

int isDigital(char x){
    if( (x>='0'&&x<='9') || (x>='A'&&x<='Z') || (x>='a'&&x<='z') || (x=='.') )
            return 1;
    return 0;
}

int isNumber(char *str){
    int i;
    for(i=0;str[i];i++){
        if(isDigital(str[i])==0)return 0;
    }
    return 1;
}
/*************************************
預處理中綴表達式，把連續的字符分離成不同的元素，用字符串數組（expression[][]）
保存，方便後面的計算，因為這裡考慮了運算數可能不全是個位數
比如：（12+3）
在處理成後綴表達式時，是123+，容易產生歧義（1+23 ? 12+3）
*************************************/
void pretreatment(char *str){
    int i,j,numberFlag;
    char temp[3];
    char number[10];
    count=0;
    numberFlag=0;
    for(j=0,i=0;str[i];i++){
        if(isDigital(str[i])==0){
            if(numberFlag==1){
                number[j]=0;
                strcpy(expression[count++],number);
                j=0;
                numberFlag=0;
            }
            if(str[i]!=' '){
                temp[0]=str[i];temp[1]=0;
                strcpy(expression[count++],temp);
            }
        }
        else {
            numberFlag=1;
            number[j++]=str[i];
        }
    }

    puts("分離後的表達式為");
    for(i=0;i<count;i++){
        printf("%s ",expression[i]);
    }puts("");
    puts("");
}
/*****************************************
中綴表達式 轉 後綴表達式

遍歷字符串，對於str[i]
str[i]是運算數（或者是字母代替的運算變量）輸出；
str[i]是符號，有兩種情況
(1)，是右括號，棧頂元素輸出，直到與str[i]匹配的左括號出棧（左括號不用輸出打印）
(2)，是運算符，判斷str[i]與棧頂元素的優先級，str[i]優先級 不高於 棧頂符號，則棧
    頂元素輸出，直到棧空 或者 棧頂符號優先級低於str[i]
*****************************************/
void infix_to_suffix(char str[N][10]){

    memset(suffix,0,sizeof(suffix));
    suffixLength=0;

    stack <char*> st;
    int i=0;
    char Mark[2]="#";
    st.push(Mark);
    do{
        if(isNumber(str[i])==1)//運算數直接保存到後綴表達式中
            strcpy(suffix[suffixLength++],str[i]);
        else if(str[i][0]=='(')        //是 左括號，直接入棧
            st.push(str[i]);
        else if(str[i][0]==')'){        //是 右括號，棧頂出棧，直到與其匹配的左括號出棧
            while( strcmp(st.top(),"(")!=0 ){
                char temp[10];
                strcpy(temp,st.top());
                strcpy(suffix[suffixLength++],temp);
                st.pop();
            }
            st.pop();
        }
        else if( strcmp(st.top(),"(")==0 )//是 運算符，且棧頂是左括號，則該運算符直接入棧
            st.push(str[i]);
        else {                    //是 運算符，且棧頂元素優先級不小於運算符，則棧頂元素一直
                                //出棧，直到 棧空 或者 遇到一個優先級低於該運算符的元素
            while( !st.empty() ){
                char temp[10];
                strcpy(temp,st.top());
                if( level(str[i][0]) > level(temp[0]) )
                    break;
                strcpy(suffix[suffixLength++],temp);
                st.pop();
            }
            st.push(str[i]);
        }
        i++;
    }while(str[i][0]!=0);

    while( strcmp(st.top(),"#")!=0 ){        //將棧取空結束
        char temp[10];
        strcpy(temp,st.top());
        strcpy(suffix[suffixLength++],temp);
        st.pop();
    }

    puts("後綴表達式為：");
    for(i=0;i<suffixLength;i++){
        printf("%s",suffix[i]);
    }puts("");
    puts("");
}

/**************************************
計算後綴表達式的值
**************************************/
char kt[N][10];
int stackTop;
void getResult(char str[N][10]){
    stackTop=0;
    /*這裡要注意，內存的分配方案導致 i 的位置就在temp[9]旁邊，然後strcpy()函數直接拷貝內存的話，在temp越界情況下會覆蓋 i 的值*/
    int i;
    char temp[10];
    for(i=0;i<suffixLength;i++){
        if(isNumber(str[i])==1){
            strcpy(kt[stackTop++],str[i]);
        }
        else {
            char a[10],b[10];
            double na,nb,nc;

            strcpy(a,kt[stackTop-1]);
            na = atof(a);
            stackTop--;

            strcpy(b,kt[stackTop-1]);
            nb = atof(b);
            stackTop--;

            if(str[i][0]=='+')nc=nb+na;
            else if(str[i][0]=='-')nc=nb-na;
            else if(str[i][0]=='*')nc=nb*na;
            else if(str[i][0]=='/')nc=nb/na;

            sprintf(temp,"%lf",nc);
            strcpy(kt[stackTop++],temp);
        }
    }
    puts("計算出後綴表達式的結果：");
    printf("%s\n",kt[stackTop-1]);
}
int main(){
    char temp[N];
    while(gets(infix)){
        strcpy(temp,infix);
        pretreatment( strcat(temp," ") );
        infix_to_suffix(expression);
        getResult(suffix);
    }
    return 0;
}