实现算术表达式求值程序（栈的运用）

Question

实现算术表达式求值程序（栈的运用）。C语言
设操作数：0，1，2，……，8，9（可扩充）；
运算符：+，－，*，/，（，），#（#号为结束）。
输入中缀表达式，如：5+(4－2)*3 #，将其转换成后缀表达式：542－3*+#，
然后计算，本例结果为11。
程序结构： 类型说明；
函数：Clearstack(S)、Emptystack(S)、 Getstop(S) 、 Push(S)、Pop(S)；
中缀到后缀转换的函数：Mid-post(E[n]，B[n])；
后缀表达式求值的函数：Postcount(B[n])；
main（）
{ 变量说明；
输入中缀表达式，存入E[n]；
调用Mid-post(E，B)；
调用Postcount(B)；
打印表达式结果；
Y 继续？
N
停止 }

Answer 1

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <string.h>

typedef struct node
{ char data;
struct node *next;
}snode,*slink;

int Emptystack(slink S)
{ if(S==NULL)return(1);
else return(0);
}

char Pop(slink* top)
{ char e;
slink p;
if(Emptystack(*top))
return(-1);
else
{ e=(*top)->data;
p=*top;
*top=(*top)->next;
free(p);
return(e);
}
}

void Push(slink* top,char e)
{ slink p;
p=(slink)malloc(sizeof(snode));
p->data=e;
p->next=*top;
*top=p;
}

void Clearstack(slink* top)
{ slink p;
while(*top!=NULL)
{ p=(*top)->next;
Pop(top);
*top=p;
}
*top=NULL;
}

char Getstop(slink S)
{ if(S!=NULL)
return(S->data);
return(0);
}

/*
int Precedence(char x)
{switch(x)
{case '+':
case '-':return(1);break;
case '*':
case '/':return(2);break;
}
}

void Mid_post(char E[],char B[])
{
slink S=NULL;
//给栈底放入'@'字符，它具有最低优先 级0
//Push(&S,'#');
//定义i,j分别用于扫描S1和指示S2串中待存字符的位置
int i=0,j=0;
//定义ch保存S1串中扫描到的字符，初值为第1个字符
char ch=E[i];
//依次处理中缀表达式中的每个字符
while(ch!='#')
{
//对于空格字符不做任何处理，顺序读取下一个字符
if(ch==' ') ch=E[++i];
//对于左括号，直接进栈
else if(ch=='(') {
Push(&S,ch);ch=E[++i];
}
//对于右括号，使括号内的仍停留在栈中运算符依次出栈并写入S2
else if(ch==')') {
while(Getstop(S)!='(') B[j++]=Pop(&S);
Pop(&S); //删除栈顶的左括号
ch=E[++i];
}
//对于运算符，使暂存于栈顶且不低于ch优先级的运算符依次出栈并写入S2
else if(ch=='+'|| ch=='-' || ch=='*' || ch=='/') {
char w=Getstop(S);
while(Precedence(w)>= Precedence(ch)) {
//Precedence(w)函数返回运算符形参的优先级
B[j++]=w;Pop(&S);
w=Getstop(S);
}
Push(&S,ch); //把ch运算符写入栈中
ch=E[++i];
}
//此处必然为数字或小数点字符，否则为中缀表达式错误
else {
//若ch不是数字或小数点字符则退出运行
if((ch<'0' || ch>'9') && ch!='.') {
printf("error!\n");
exit(1);
}
//把一个数值中的每一位依次写入到S2串中
while((ch>='0' && ch<='9') || ch=='.') {
B[j++]=ch;
ch=E[++i];
}
//被放入S2中的每个数值后面接着放入一个空格字符
B[j++]=' ';
}
}
//把暂存在栈中的运算符依次退栈并写入到S2串中
ch=Pop(&S);
while(ch!='#') {
if(ch=='(') { printf("expression_r error!\n");exit(1);}
else {
B[j++]=ch;
ch=Pop(&S);
}
}
//在后缀表达式的末尾放入字符串结束符
B[j++]='\0';
}

*/

int Precedence(char x,char y)
{switch(x)
{case '(':x=0;break;
case '+':
case '-':x=1;break;
case '*':
case '/':x=2;break;
}
switch(y)
{case '+':
case '-':y=1;break;
case '*':
case '/':y=2;break;
case ')':x=3;break;
}
if(x>=y)
return(1);
else return(0);
}

void Mid_post(char E[],char B[])
{
slink S=NULL;
//给栈底放入'@'字符，它具有最低优先 级0
//Push(&S,'#');
//定义i,j分别用于扫描S1和指示S2串中待存字符的位置
int i=0,j=0;
//定义ch保存S1串中扫描到的字符，初值为第1个字符
//Push(&S,'#');
char ch;
//依次处理中缀表达式中的每个字符
do
{
//对于空格字符不做任何处理，顺序读取下一个字符
if(ch==' ') ch=E[++i];
ch=E[i++];
switch(ch)
{ case '#':
{ while(!Emptystack(S))
B[j++]=Pop(&S);
}break;
case ')':
{while(Getstop(S)!='(')
B[j++]=Pop(&S);
Pop(&S);
}break;
case '+':
case '-':
case '*':
case '/':
case '(':
{ while(Precedence(Getstop(S),ch))
B[j++]=Pop(&S);
Push(&S,ch);
}break;
default:B[j++]=ch;
}
}while(ch!='#');
B[j++]='#';
B[j]='\0';
}

int Postcount(char B[])
{int i=0;
char x;
float z,a,b;
slink S=NULL;
while(B[i]!='#')
{x=B[i];
switch(x)
{case '+':b=Pop(&S);a=Pop(&S);z=a+b;Push(&S,z);break;
case '-':b=Pop(&S);a=Pop(&S);z=a-b;Push(&S,z);break;
case '*':b=Pop(&S);a=Pop(&S);z=a*b;Push(&S,z);break;
case '/':b=Pop(&S);a=Pop(&S);z=a/b;Push(&S,z);break;
default : x=B[i]-'0';Push(&S,x);
}
i++;
}
if(!Emptystack(S)) return(Getstop(S));
}

void main()
{ char B[255],E[255]=" ";
char check[2];
int i=1;
int round = 1;
while(i<2)
{printf("please input 中缀表达式：");
//scanf("%s",E);
if(round > 1){getchar();}
gets(E);
//puts(E);
//strcpy(B,E); //将B填充为与E相同的空间(其实是忘了加'#')
//gets(B);
//puts(B);
printf("后缀表达式为:");
Mid_post(E,B);
puts(B);
printf("the result is %d\n",Postcount(B));
printf("\ncontine?(Y/N)");
scanf("%s",check);
round ++;
if(check[0]=='N')
break;
if(check[0]!='Y'&&check[0]!='N')
{printf("您输入了规定以外的字符\n");
break;
}
}
printf("------------FIN------------");
getch();
}

就是这样