栈的应用2——超级计算器(中缀与后缀表达式)C语言

时间:2021-11-05 02:34:35

输入中缀表达式输出结果(结果可以是小数,但输入必须是整数) 

 #include<stdio.h>
#include<stdlib.h> //需要两个栈,一个储存结果,一个储存运算符
#define newpc (stype *)malloc(sizeof(stype))
#define newpi (inttype *)malloc(sizeof(inttype)) //定义两个申请地址的宏
typedef struct char_stack
{
char dat;
struct _stack * next;
} stype;
typedef struct int_stack
{
double dat;
struct _stack * next; //建立两个栈类型
} inttype;
void charpush(stype** stacktop,char c) //运算符压栈函数,需要传进栈顶指针本身的地址,而不是它指向的地址
{
stype * ss=newpc;
ss->dat=c;
ss->next=*stacktop;
*stacktop=ss;
}
char charpop(stype** stacktop) //运算符出栈函数
{
char c=(*stacktop)->dat;
stype *ss=(*stacktop);
(*stacktop)=(*stacktop)->next;
free(ss);
return c;
}
void intpush(inttype** stacktop,double c) //数字压栈函数
{
inttype * ss=newpi;
ss->dat=c;
ss->next=*stacktop;
*stacktop=ss;
}
double intpop(inttype** stacktop) //数字出栈函数
{
double c=(*stacktop)->dat;
inttype *ss=(*stacktop);
(*stacktop)=(*stacktop)->next;
free(ss);
return c;
}
void tanchu(char c,inttype ** stacktop) //弹出字符,然后运算,然后进栈
{
double a=intpop(stacktop);
double b=intpop(stacktop);
if (c=='+') intpush(stacktop,b+a);
else if (c=='-') intpush(stacktop,b-a);
else if (c=='*') intpush(stacktop,b*a);
else if (c=='/') intpush(stacktop,b/a);
}
int tance(char c) //探测优先级的函数
{
if (c=='+'||c=='-') return ;
else if (c=='*'||c=='/') return ;
else if (c=='@'||c=='('||c==')') return -;
}
int main() //主函数 功能:处理输入的中缀表达式,输出结果(过程中用到了后缀的转化)
{
stype * sig,* sigtop;
inttype * num,* numtop; //每个栈需要两个指针进行操作
char c=getchar();
sig=newpc;
sig->dat='@';
sig->next=NULL;
sigtop=sig;
num=newpi;
num->next=NULL;
numtop=num; //初始化两个栈
while (c!='\n') //一直读入,直至读到回车符结束
{
//接下来要对读入的当前字符进行处理
if (c>=''&&c<='')
{
int a=c-;
c=getchar();
while(c>=''&&c<='')
{
a=a*+(c-);
c=getchar();
}
intpush(&numtop,a); //如果是个数字字符,就把这个数字一直读进去(因为不一定是几位数),然后压栈到num里
}
else if (c=='(') //如果是左括号,直接压栈到sig里
{
charpush(&sigtop,'(');
c=getchar();
}
else if (c==')') //如果是右括号,就边弹栈边处理结果,直到遇到左括号
{
while (sigtop->dat!='(')
{
tanchu(charpop(&sigtop),&numtop);
}
c=getchar();
charpop(&sigtop);
}
else if (c=='+'||c=='-'||c=='*'||c=='/') //如果是+-*/就比较与栈顶的优先级,如果高,直接压入,否则(等于也不能压入),边弹边处理结果,直到可以压入(和上面有点像)
{
int j=tance(c);
int k=tance(sigtop->dat);
if (j>k)
{
charpush(&sigtop,c);
c=getchar();
}
else{
while(j<=k)
{
tanchu(charpop(&sigtop),&numtop);
k=tance(sigtop->dat);
}
charpush(&sigtop,c);
c=getchar();
}
}
else //否则,忽略这个符号 ,并且显示输入有误
{
c='\n';
printf("输入有误\n");
} }
while (sigtop->dat!='@') //收收尾,把没有弹出的都处理一下
{
tanchu(charpop(&sigtop),&numtop);
}
printf("%.2lf\n",numtop->dat);
c=getchar();
return ;
}