数据结构与算法——中缀表达式
#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;
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=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 主函数里为什么调用这个函数结果就不对呢？
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;
}
}
但是在主函数里直接写却可以，调用的话栈顶出栈时没有往下走 原因找到了，调用函数如果要改变栈顶位置或内部的值，需要用地址，改成int switch_temp(sqStack1 *s1,char c_temp,double m,double n)
页:
[1]