sjk1996 2016-06-23 19:22 采纳率: 0%
浏览 1870
已采纳

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

程序可以运行,但实现不了表达式求值的功能,问题出在哪里?图片图片图片图片图片图片图片图片

  • 写回答

3条回答 默认 最新

  • threenewbee 2016-06-23 23:42
    关注
    #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;
    }
    
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(2条)

报告相同问题?

悬赏问题

  • ¥15 用visualstudio2022创建vue项目后无法启动
  • ¥15 x趋于0时tanx-sinx极限可以拆开算吗
  • ¥500 把面具戴到人脸上,请大家贡献智慧
  • ¥15 任意一个散点图自己下载其js脚本文件并做成独立的案例页面,不要作在线的,要离线状态。
  • ¥15 各位 帮我看看如何写代码,打出来的图形要和如下图呈现的一样,急
  • ¥30 c#打开word开启修订并实时显示批注
  • ¥15 如何解决ldsc的这条报错/index error
  • ¥15 VS2022+WDK驱动开发环境
  • ¥30 关于#java#的问题,请各位专家解答!
  • ¥30 vue+element根据数据循环生成多个table,如何实现最后一列 平均分合并