中缀表达式转后缀表达式求值（栈的应用）

咱们熟悉的四则运算表达式，中缀表达式，例如 （12+3）*2-6/2

利用堆栈的方法把中缀表达式转换成保值的后缀表达式（又称逆波兰表示法），并最终变为计算机可以直接执行的指令，得到表达式的值

挺简单的不假，也好理解，但就是一直无缘无故的卡着，卡的蛋疼……

也不能说完全的无缘无故，其实是手生了吧，太生了……

#include<stdio.h>#include<string.h>#include<stdlib.h>#include<stack>using namespace std;#define N 1000char 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;//Fuck!!!!!!!!!!!//这里我就不明白了，计算后缀表达式的值时候，用STL的stack就出错（最后一个数出不了栈），//自己模拟一个栈就对了……，求解释……void getResult(char str[N][10]){    stackTop=0;    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;}