数据结构与算法——中缀表达式

荆轲 · 发表于 2022-4-20 09:03:27

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

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

#define STACK_INIT_SIZE 20 //栈的初始化空间大小
#define STACKINCREMENT 10 //每次增加的栈空间大小
#define MAXBUFFER 10 //缓冲区大小

typedef char ElemType;
typedef struct
{
int stackSize;
ElemType *base;//指向栈底的指针
ElemType *top;//指向栈顶的指针
}sqStack;

void initStack(sqStack *s)
{
s->base=(ElemType *)malloc(STACK_INIT_SIZE*sizeof(ElemType));
if(!s->base)
{
exit(0);
}
s->top=s->base;
s->stackSize=STACK_INIT_SIZE;
}

void Push(sqStack *s,ElemType e)//进栈
{
if(s->top - s->base >= s->stackSize)
{
s->base=(ElemType *)realloc(s->base,(s->stackSize+STACKINCREMENT)*sizeof(ElemType));
if(!s->base)
{
exit(0);
}
s->top=s->base+s->stackSize;
s->stackSize=s->stackSize+STACK_INIT_SIZE;//大小要更新，不然会误认为容量不够又继续申请内存
}
*(s->top)=e;//把e对应的元素压入栈顶
s->top++;//栈顶上移
}

void Pop(sqStack *s,ElemType *e)//出栈
{
if(s->top==s->base)
{
return;
}
*e=*(--(s->top));
}

int stackLen(sqStack s)
{
return (s.top-s.base);
}

/***********************************************/
typedef double ElemType1;
typedef struct
{
int stackSize;
ElemType1 *base;//指向栈底的指针
ElemType1 *top;//指向栈顶的指针
}sqStack1;

void initStack1(sqStack1 *s)
{
s->base=(ElemType1 *)malloc(STACK_INIT_SIZE*sizeof(ElemType1));
if(!s->base)
{
exit(0);
}
s->top=s->base;
s->stackSize=STACK_INIT_SIZE;
}

void Push1(sqStack1 *s,ElemType1 e)//进栈
{
if(s->top - s->base >= s->stackSize)
{
s->base=(ElemType1 *)realloc(s->base,(s->stackSize+STACKINCREMENT)*sizeof(ElemType1));
if(!s->base)
{
exit(0);
}
s->top=s->base+s->stackSize;
s->stackSize=s->stackSize+STACK_INIT_SIZE;//大小要更新，不然会误认为容量不够又继续申请内存
}
*(s->top)=e;//把e对应的元素压入栈顶
s->top++;//栈顶上移
}

void Pop1(sqStack1 *s,ElemType1 *e)//出栈
{
if(s->top==s->base)
{
return;
}
*e=*(--(s->top));
}

int stackLen1(sqStack1 s)
{
return (s.top-s.base);
}

int switch_temp(sqStack1 s1,char c_temp,double m,double n)
{
switch(c_temp)
{
case '+'://两个出栈，并相加
Pop1(&s1,&m);//出栈第一个数
Pop1(&s1,&n);//出栈第二个数
Push1(&s1,n+m);
break;

case '-'://两个出栈，并相减
Pop1(&s1,&m);//出栈第一个数
Pop1(&s1,&n);//出栈第二个数
Push1(&s1,n-m);
break;

case '*'://两个出栈，并相乘
Pop1(&s1,&m);//出栈第一个数
Pop1(&s1,&n);//出栈第二个数
Push1(&s1,n*m);
break;

case '/'://两个出栈，并相除
Pop1(&s1,&m);//出栈第一个数
Pop1(&s1,&n);//出栈第二个数
if(c_temp !=0)
{
Push1(&s1,n/m);
}
else
{
printf("\n错误：除数为零!\n");
return -1;
}
break;
}
}

#if(1)
int main()
{
sqStack s;
sqStack1 s1;
char c,e;
char str[MAXBUFFER];
int i=0,j=0;
double m,n,p;

initStack(&s);
initStack1(&s1);

printf("请输入中缀表达式，按#键结束：");
scanf("%c",&c);

while(c!='#')
{
      while( (c>='0' && c<='9') || c=='.')
      {
         printf("%c",c);

str[i]=c;//
str[++i]='\0';//
if(i>=MAXBUFFER)//字符串溢出
{
printf("\n出错：输入的单个数据过长!\n");
return -1;
}//+

         scanf("%c",&c);
         if( (c<'0' || c>'9') && c!='.' )
         {
            printf(" ");

p=atof(str);//+
Push1(&s1,p);//+
i=0;//i初始化，进入下一个循环+
break;//+
         }
      }

if( c==')' )
{
Pop(&s,&e);
while( e!='(' )
{
printf("%c ",e);

// switch_temp(s1,e,n,m);//+
switch(e)
{
case '+'://两个出栈，并相加
Pop1(&s1,&m);//出栈第一个数
Pop1(&s1,&n);//出栈第二个数
Push1(&s1,n+m);
break;

case '-'://两个出栈，并相减
Pop1(&s1,&m);//出栈第一个数
Pop1(&s1,&n);//出栈第二个数
Push1(&s1,n-m);
break;

case '*'://两个出栈，并相乘
Pop1(&s1,&m);//出栈第一个数
Pop1(&s1,&n);//出栈第二个数
Push1(&s1,n*m);
break;

case '/'://两个出栈，并相除
Pop1(&s1,&m);//出栈第一个数
Pop1(&s1,&n);//出栈第二个数
if(c !=0)
{
Push1(&s1,n/m);
}
else
{
printf("\n错误：除数为零!\n");
return -1;
}
break;
}

Pop(&s,&e);
}
}

else if(c=='+' || c=='-')
{
if(!stackLen(s))
{
Push(&s,c);
}
else
{
do
{
Pop(&s,&e);
if( e=='(')
{
Push(&s,e);
}
else
{
printf("%c ",e);

// switch_temp(s1,e,n,m);//+
/*******************************************************/
switch(e)
{
case '+'://两个出栈，并相加
Pop1(&s1,&m);//出栈第一个数
Pop1(&s1,&n);//出栈第二个数
Push1(&s1,n+m);
break;

case '-'://两个出栈，并相减
Pop1(&s1,&m);//出栈第一个数
Pop1(&s1,&n);//出栈第二个数
Push1(&s1,n-m);
break;

case '*'://两个出栈，并相乘
Pop1(&s1,&m);//出栈第一个数
Pop1(&s1,&n);//出栈第二个数
Push1(&s1,n*m);
break;

case '/'://两个出栈，并相除
Pop1(&s1,&m);//出栈第一个数
Pop1(&s1,&n);//出栈第二个数
if(c !=0)
{
Push1(&s1,n/m);
}
else
{
printf("\n错误：除数为零!\n");
return -1;
}
break;
}
/********************************************************/
}
}while(stackLen(s) && e!='(');
Push(&s,c);
}
}

else if(c=='*' || c=='/' || c=='(')
{
Push(&s,c);
}

else if(c=='#')
{
break;
}

else
{
printf("输入格式错误!\n");
return -1;
}

scanf("%c ",&c);
}

while(stackLen(s))
{
Pop(&s,&e);
printf("%c ",e);
// switch_temp(s1,e,m,n);//+
//
switch(e)
{
case '+'://两个出栈，并相加
Pop1(&s1,&m);//出栈第一个数
Pop1(&s1,&n);//出栈第二个数
Push1(&s1,n+m);
break;

case '-'://两个出栈，并相减
Pop1(&s1,&m);//出栈第一个数
Pop1(&s1,&n);//出栈第二个数
Push1(&s1,n-m);
break;

case '*'://两个出栈，并相乘
Pop1(&s1,&m);//出栈第一个数
Pop1(&s1,&n);//出栈第二个数
Push1(&s1,n*m);
break;

case '/'://两个出栈，并相除
Pop1(&s1,&m);//出栈第一个数
Pop1(&s1,&n);//出栈第二个数
if(c !=0)
{
Push1(&s1,n/m);
}
else
{
printf("\n错误：除数为零!\n");
return -1;
}
break;
}
//
}

Pop1(&s1,&m);//最终的结算结果放在n里 +
printf("计算结果为：%f\n",m);//+

return 0;
}
#endif

荆轲 · 发表于 2022-4-20 09:04:33

主函数里为什么调用这个函数结果就不对呢？
int switch_temp(sqStack1 s1,char c_temp,double m,double n)
{
            switch(c_temp)
            {
                     case '+'://两个出栈，并相加
                              Pop1(&s1,&m);//出栈第一个数
                              Pop1(&s1,&n);//出栈第二个数
                              Push1(&s1,n+m);
                              break;

                              case '-'://两个出栈，并相减
                              Pop1(&s1,&m);//出栈第一个数
                              Pop1(&s1,&n);//出栈第二个数
                              Push1(&s1,n-m);
                              break;

                              case '*'://两个出栈，并相乘
                              Pop1(&s1,&m);//出栈第一个数
                              Pop1(&s1,&n);//出栈第二个数
                              Push1(&s1,n*m);
                              break;

                              case '/'://两个出栈，并相除
                              Pop1(&s1,&m);//出栈第一个数
                              Pop1(&s1,&n);//出栈第二个数
                              if(c_temp !=0)
                              {
                                    Push1(&s1,n/m);
                              }
                              else
                              {
                                    printf("\n错误：除数为零!\n");
                                    return -1;
                              }
                              break;
            }
}

荆轲 · 发表于 2022-4-20 09:05:17

但是在主函数里直接写却可以，调用的话栈顶出栈时没有往下走

荆轲 · 发表于 2022-4-20 09:32:05

原因找到了，调用函数如果要改变栈顶位置或内部的值，需要用地址，改成int switch_temp(sqStack1 *s1,char c_temp,double m,double n)

账号		自动登录	找回密码
密码			立即注册

[技术交流] 数据结构与算法——中缀表达式

马上注册，结交更多好友，享用更多功能^_^