c语言，中缀式转后缀式前缀式然后求值，无法入栈？

Question

c语言，中缀式转后缀式前缀式然后求值，无法入栈？

发布于
2024-02-28 黑龙江

更新于
2024-02-28

新手上路，请多包涵

我写了一个中缀式转化为后缀式，前缀式，并计算出中前后缀式结果的代码，但是在确保输入格式正确后（我输入的是：11+22*（9-6）/3#），输出为：Have no target!!,我想了好久，觉得是输入的式子没有办法入栈，但是找不出来哪里有问题，能帮我看一下是哪里的问题吗？谢谢各位大佬！

以下是我的代码：

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>

#define STACKSIZE 100
#define SIZECRIMENT 10

typedef struct {
    float *top;
    float *base;
    int stacksize;
}Sqstack1;

typedef struct {
    char *top;
    char *base;
    int stacksize;
}Sqstack2;

void initstack1(Sqstack1 *s){
    s->base=(float*)malloc(STACKSIZE*sizeof(float));
    if(!s->base){
        printf("Don't have enough space!\n");exit(1);}
        s->top=s->base;
        s->stacksize=STACKSIZE;}
    
    
void initstack2(Sqstack2 *s){
    s->base=(char*)malloc(STACKSIZE*sizeof(char));
    if(!s->base){printf("Don't have enough space!\n");exit(1);
    }
    s->top=s->base;
    s->stacksize=STACKSIZE;
}    

void GetTop1(Sqstack1 *s,float *e){
    if(s->top==s->base){
        printf("Have no target!\n");exit(1);
    }
    *e=*(s->top-1);
}
    
void GetTop2(Sqstack2 *s,char *e){
    if(s->top==s->base){printf("Have no target!!\n");exit(1);
    }
    *e=*(s->top-1);
}    

void Push1(Sqstack1 *s,float e){
    if((s->top-s->base)>=s->stacksize){
        printf("The Sqstack1 is full,we are finding more continuous space!\n");
        s->base=(float*)realloc(s->base,(STACKSIZE+SIZECRIMENT)*sizeof(float));    
    if(!s->base){
        printf("Don't have more continuous space!\n");exit(1);}
    s->top=s->base+s->stacksize;
    s->stacksize+=SIZECRIMENT;}
    
    *s->top=e;s->top++;
}

void Push2(Sqstack2 *s,char e){
    if((s->top-s->base)>=s->stacksize){
        printf("The Sqstack2 is full,we are finding more continuous space!\n");
        s->base=(char*)realloc(s->base,(STACKSIZE+SIZECRIMENT)*sizeof(char));
        if(!s->base){
            printf("Don't have enough continuous space!\n");exit(1);}
        s->top=s->base+s->stacksize;
        s->stacksize+=SIZECRIMENT;}
    
    *s->top=e;s->top++;
}

void Pop1(Sqstack1 *s,float *e){
    if(s->top==s->base){
        printf("the Sqstack1 is empty!\n");exit(1);
    }
    *e=*--s->top;
}

void Pop2(Sqstack2 *s,char *e){
    if(s->top==s->base){
        printf("The Sqstack2 is empty!\n");exit(1);
    }
    *e=*--s->top;
}

int priority(char s1,char s2){
    char chars[2]; int prioritys[2];
    int i;
    chars[0]=s1;
    chars[1]=s2;
    for(i=0;i<2;i++){
        switch(chars[i]){
            case'*':
            case'/':
            case'%':prioritys[i]=2;break;
            case'+':
            case'-':prioritys[i]=1;break;
            case'(':
            case')':
            case'#':prioritys[i]=0;break;
        }
    }
    if(prioritys[0]>=prioritys[1])
    return 1;else return 0;
}

void suffix(char *s){
    Sqstack2 S;
    initstack2(&S); //s是中缀表达式数组，s1是后缀表达式数组，S用于操作栈； 
    char s1[100];char e;
    int i=0,j=0;
    Push2(&S,'$');
    while(s[i]!='#'){
        if((s[i]<='9')&&(s[i]>='0')){
        s1[j++]=s[i];}
        else switch(s[i]){
            case'(':Push2(&S,s[i]);break;
            case')':GetTop2(&S,&e);while(e!='('){
                s1[j++]=e;
                Pop2(&S,&e);}break;
            default:while(GetTop2(&S,&e),priority(e,s[i])){//当操作栈不为空且中缀式指针运算符  
            //优先级大于操作栈顶元素时； 
            Pop2(&S,&e);//此时e指针内容为 操作栈顶元素；出操作栈；
            s1[j++]=e;} //出操作栈的运算符写入后缀式；     
            Push2(&S,s[i]);}//找到比s[i]优先级小的运算符或者操作栈空时，将s[i]放入S操作栈； 
        i++;
    }while(GetTop2(&S,&e),e!='$'){
        Pop2(&S,&e);s1[j++]=e;
    }
    s1[j]='\0';
    printf("The suffix expression is:\n");
    puts(s1);
}

void reversal(char *s){
    Sqstack2 S;char e;
    initstack2(&S);
    char s1[100];
    int i=0,j=0;
    Push2(&S,'a');
    Push2(&S,'#');
    while(s[i]!='#'){
        Push2(&S,s[i]);
        i++;
    }
    while(GetTop2(&S,&e),e!='a'){
        Pop2(&S,&e);s1[j++]=e;
    }
    s[j]='\0';
    for(i=0;i<j;i++){
        s[i]=s1[i];
    }
}

void prefix(char *s){
    char s1[100];
     Sqstack2 S;
     initstack2(&S);
     reversal(s);
     char e;
     int i=0,j=0;
     Push2(&S,'$');
     while(s[i]!='#'){
         if((s[i]<='9')&&(s[i]>='0')){
             s1[j++]=s[i];i++;
         }
         else switch(s[i]){
             case ')':Push2(&S,')');i++;break;
             case '(':while(GetTop2(&S,&e),e!=')'){//e内容为S栈顶元素； 
                 Pop2(&S,&e);s1[j++]=e;
             }Pop2(&S,&e);break;//e内容为‘）’；
            default:while(GetTop2(&S,&e),priority(e,s[i])){//此时*e为S操作栈
            //栈顶元素；
            Pop2(&S,&e);s1[j++]=e;} //此时*e为S操作栈栈顶元素； 
            Push2(&S,s[i]);i++;      
         }
     }
     while(GetTop2(&S,&e),e!='$'){
         Pop2(&S,&e);s1[j++]=e;
     }
     reversal(s1);
     s1[j]='\0';
     printf("The prefix expression is:\n");
     puts(s1);
}

void calculate_prefix(Sqstack1 *S,char *s){
    reversal(s);
    initstack1(S);
    float e;int i=0;
    float x,y,z,m;
    while(s[i]!='#'){
        if((s[i]>='0')&&(s[i]<='9')){
            m=s[i]-'0';
            Push1(S,m);i++;
        }
        else {
        Pop1(S,&x);
        Pop1(S,&y);
        switch(s[i]){
            case '+':z=x+y;break;
            case '-':z=y-x;break;
            case '*':z=x*y;break;
            case '/':z=y/x;break;
            case '%':z=(int)y%(int)x;break;
        }
        Push1(S,z);i++;}
    }
    GetTop1(S,&e);
    printf("The prefix_expression's result is:%.2f",e);
}

void calculate_suffix(Sqstack1 *S,char *s){
    initstack1(S);
    float e;int i=0;
    float x,y,z,m;
    while(s[i]!='#'){
        if((s[i]>='0')&&(s[i]<='9')){
            m=s[i]-'0';
            Push1(S,m);i++;
        }
        else {
        Pop1(S,&x);Pop1(S,&y);
        switch(s[i]){
            case '+':z=x+y;break;
            case '-':z=y-x;break;
            case '*':z=x*y;break;
            case '/':z=y/x;break;
            case '%':z=(int)y%(int)x;break;
        }
        Push1(S,z);i++;}
    }
    GetTop1(S,&e);
    printf("The suffix_expression's result is:%.2f",e);
}

void calculate_infix(Sqstack2 *S,char *s){
    Sqstack1 S1;
    initstack2(S); //s是中缀表达式数组，s1是后缀表达式数组，S用于操作栈； 
    char s1[100];char e;char k='$';
    int i=0;int j=0;
    Push2(S,k);
    while(s[i]!='#'){
        if((s[i]<='9')&&(s[i]>='0'))
        s1[j++]=s[i];
        else switch(s[i]){
            case'(':Push2(S,s[i]);break;
            case')':Pop2(S,&e);while(e!='('){
                s1[j++]=e;
                Pop2(S,&e);}break;
            default:GetTop2(S,&e);//此时的e指针内容为 操作栈顶元素； 
            while(GetTop2(S,&e),priority(e,s[i])){//当操作栈不为空且中缀式指针运算符  
            //优先级大于操作栈顶元素时； 
            Pop2(S,&e);//此时e指针内容为 操作栈顶元素；出操作栈；
            s1[j++]=e;} //出操作栈的运算符写入后缀式；     
            Push2(S,s[i]);}break;//找到比s[i]优先级小的运算符或者操作栈空时，将s[i]放入S操作栈； 
        i++;
    }while(GetTop2(S,&e),e!='$'){
        Pop2(S,&e);s1[j++]=e;
    }
    calculate_suffix(&S1,s1);
}

int main(){
    Sqstack1 S1;
    Sqstack2 S;
    char s[100];
    printf("Please input the infix expression!");
    fgets(s,100,stdin);
    puts(s);    
    suffix(s);
    prefix(s);
    calculate_infix(&S,s);
    printf("Please input the suffix expression!");
    fgets(s,100,stdin);
    calculate_suffix(&S1,s);
    printf("Please input the prefix expression!");
    fgets(s,100,stdin);
    calculate_prefix(&S1,s);
    return 0;
}

主函数中将

suffix(s);
prefix(s);
alculate_infix(&S,s);

改为

calculate_infix(&S,s);    
suffix(s);
prefix(s);

输出变成了“The Sqstack2 is empty!”

试过修改initstack1(*S);为Stack1 S; initstack1(&S);输出从原来什么也没有变成了上述问题；

查了谷歌，谷歌说puts函数不稳定，试过把原来的puts函数改为fputs函数，但是问题没有解决；

试过把Pop,Push函数里参数，加删*，加删&，并调整整体相关部分运行代码，但是还是上述问题，所以我觉得是我输入的式子压根没有入栈；

希望能输出后缀式和前缀式，并输出计算结果。

////我在switch语句中加了case：‘$’:priority[i]=0;break;现在后缀表达式输出了，但是前缀表达式依旧是老问题

////谢谢，原来是我Pop，Push函数中的逻辑错误，导致该弹栈的时候把栈提前清空了，等再弹栈的时候没有元素了，把逻辑理清了就解决了。

c

阅读 1k

1 个回答

得票最新

peterhuan

68121581

发布于
2024-02-28 山东

✓ 已被采纳

void suffix(char *s) {
...
  default:while(GetTop2(&S,&e),priority(e,s[i])){//当操作栈不为空且中缀式指针运算符  
            //优先级大于操作栈顶元素时； 
            Pop2(&S,&e);//此时e指针内容为 操作栈顶元素；出操作栈；
            s1[j++]=e;} //出操作栈的运算符写入后缀式；     
            Push2(&S,s[i]);}//找到比s[i]优先级小的运算符或者操作栈空时，将s[i]放入S操作栈；
}

GetTop2(&S,&e)得到的不一定是一个操作符啊。

当操作栈不为空且中缀式指针运算符优先级大于操作栈顶元素时；

这个注释写的和代码表述的矛盾啊?应该是操作栈顶元素优先级大于中缀式指针运算符吧。还有一种情况没有考虑，当优先级相等且为左结合的时候，也要Pop出来。

查看全部 1 个回答

推荐问题

迟到问题，知道其他解法，但是想探求为什么以下解法不行？
题目描述学校和 yyy 的家之间的距离为 s 米，而 yyy 以 v 米每分钟的速度匀速走向学校。在上学的路上，yyy 还要额外花费 10 分钟的时间进行垃圾分类。学校要求必须在上午 8:00 到达，请计算在不迟到的前提下，yyy 最晚能什么时候出门。由于路途遥远，yyy 可能不得不提前一点出发，但是提前的时间不会超过一天。输入格式...
1 回答999 阅读

相似问题

找不到问题？创建新问题

c语言，中缀式转后缀式前缀式然后求值，无法入栈？

迟到问题，知道其他解法，但是想探求为什么以下解法不行？