题解 | #表达式求值#逆波兰表达法求解

这道题做了好久，看到没有C语言题解咱就写一下，欢迎优化指正OvO- - 本解法采用逆波兰表达式求解，前半段是将中缀表达式变换成后缀表达试（逆波兰表达式） 关于逆波兰表达式大家可以百度知乎一下，算法入门里面也有逆波兰表达式的题，感觉用逆波兰算长表达式是真滴好使- -。 代码如下，大家应该都可以看懂，要注意的是数组下标的值一定要仔细！！还有一点要注意的就是当逆波兰表达式中出现连续的减号时，除了第一个减号剩余减号都要转换成加号，下面也有对应代码注解。如当遇到1-2-3-4时，第一部分变换的表达式时1，2，3，4，-，-，-，但由于有连续减号所以我们需要加一步变换->逆波兰表达式：1,2,3,4,-,+,+, 但如果遇到1-（2-3）的情况由于有（）减号没有形成连续的减号所以就可以直接进行运算啦->逆波兰表达式：1，2，3，-，-。

int solve(char* s ) {
    int topIdx=0;
    char operator[100]={0};
    char temp[100][10]={0};
    int m=0,j=0;
    //******************逆波兰转换，将中缀表达式转换成后缀表达式***********
    int len=strlen(s);
    for(int i=0;i<len;i++){
        if(s[i]=='*'||s[i]=='('){
            operator[topIdx++]=s[i];
        }
         else if(s[i]=='+'||s[i]=='-'){
            if(operator[topIdx-1]=='*'){
                while(operator[--topIdx]!='('&&topIdx>=0)
                    temp[j++][0]=operator[topIdx];
                operator[++topIdx]=s[i];
                topIdx++;
            }
            else
                operator[topIdx++]=s[i];
            }
        else if(s[i]==')'){
            while(operator[--topIdx]!='('&&topIdx>=0)
                temp[j++][0]=operator[topIdx];
        }
     
        else{
            temp[j][m++]=s[i];
            if((s[i+1]<'0'||s[i+1]>'9')&&i<len-1){
                j++;
                m=0;
            }
            else if(i==len-1)
                j++;
        }
    }
     
    for(int i=0,j=1;i<topIdx;i++){
        if(operator[i]=='-')
            while(operator[i+j]=='-'&&(i+j)<topIdx)
                operator[i+j++]='+';
    }
     
     
    int lenoftemp=0;
    if(topIdx!=0){
        for(int i=topIdx-1;i>=0;i--)
            temp[j++][0]=operator[i];
        lenoftemp=j;
    }
     
     //**************用逆波兰表达式求解最终结果***********
    int result=0;
    int integer[100];
   // int *integer=(int *)malloc(sizeof(int)*lenoftemp);
    for(int i=0,topIdx=0;i<lenoftemp;i++){
        if(strcmp(temp[i],"+")==0){
            result=integer[topIdx-2]+integer[topIdx-1];
            topIdx--;
            integer[topIdx-1]=result;
        }
        else if(strcmp(temp[i],"*")==0){
            result=integer[topIdx-2]*integer[topIdx-1];
            topIdx--;
            integer[topIdx-1]=result;
        }
        else if(strcmp(temp[i],"-")==0){
            result=integer[topIdx-2]-integer[topIdx-1];
            topIdx--;
            integer[topIdx-1]=result;
        }
        else
            integer[topIdx++]=atoi(temp[i]);
    }
     
    return integer[0];
}