/*扫描一个算式如#2+5*(5+3)/2-8/9#后算出结果*/
基本思想是从左至右扫描表达式，并
按如下过程进行处理：
⑴ 置shu和fu为空栈；
⑵ 读入表达式的开始操作符c=‘#’，并进fu栈；
⑶ 读入表达式的下一个符号c；
⑷ c<>‘#’或者fu栈顶操作符也不是‘#’时，进行如下操作：
①若c是操纵数，则c进shu栈；
②若c是操作符，则比较它与fu栈顶操作符x的优先关系：
若x<c，则c进fu栈，并读入表达式的下一个符号c；
若x=c，则fu退栈，并读入表达式的下一个符号c；
若x>c，则从shu栈退出x所要求的操作数，x从fu栈退出，
并完 成x的计算，其结果进shu栈；
③重复⑷直到条件不成立；
⑸ 当c=‘#’，同时ops栈顶元素也是‘#’时，shu栈中仅有一个元素，
此即为表达式的值。
#define maxsize 20
typedef struct /*实数栈初始化*/
{
float fbase[maxsize];
int ftop;
}fstack;
typedef struct /*符号栈初始化*/
{
char cbase[maxsize];
int ctop;
}cstack;
void emptyfstack(fstack c) /*实数栈置空*/
{
c.ftop=-1;
}
int emptyf(fstack c) /*判断实数栈是否为空*/
{
if(c.ftop==-1)
return 1;
else
return 0;
}
void emptycstack(cstack c) /*符号栈置空*/
{
c.ctop=-1;
}
int emptyc(cstack c) /*判断符号栈是否为空*/
{
if(c.ctop==-1)
return 1;
else
return 0;
}
void pushfstack(fstack c,float e) /*数字入栈*/
{
if(c.ftop==maxsize-1)
printf("the stack is overflow\n");
else
c.fbase[++c.ftop]=e;
}
void pushcstack(cstack c,char e) /*符号入栈*/
{
if(c.ctop==maxsize-1)
printf("the stack is overflow\n");
else
c.cbase[++c.ctop]=e;
}
void popfstack(fstack c,float e) /*数字退栈*/
{
if(c.ftop==-1)
printf("the stack is underflow\n");
else
e=c.fbase[c.ftop--];
}
void popcstack(cstack c,char e) /*符号退栈*/
{
if(c.ctop==-1)
printf("the stack is underflow\n");
else
e=c.cbase[c.ctop--];
}
float getfstack(fstack c) /*取数字栈栈顶元素*/
{
float e;
if(emptyf(c))
printf("the stack is empty");
else
{
e=c.fbase[c.ftop];
return e;
}
}
char getcstack(cstack c) /*取符号栈栈顶无素*/
{
char e;
if(emptyc(c))
printf("the stack is empty");
else
{
e=c.cbase[c.ctop];
return e;
}
}
int priority(char c) /*符号优先级*/
{
switch(c)
{
case '#':return -1;
case ')':return 0;
case '+':
case '-':return 1;
case '*':
case '/':return 2;
case '(':return 3;
default:return -1;
}
}
void oper(fstack a,cstack b,char c) /*操作数的操作*/
{
float v,v1,v2;char s;
if(priority(getcstack(b))<priority(c))
pushcstack(b,c);
else if(priority(getcstack(b))>=priority(c))
{
if(getcstack(b)=='+')
{popfstack(a,v1);popfstack(a,v2);v=v1+v2;pushfstack(a,v);}
else if(getcstack(b)=='-')
{popfstack(a,v1);popfstack(a,v2);v=v2-v1;pushfstack(a,v);}
else if(getcstack(b)=='*')
{popfstack(a,v1);popfstack(a,v2);v=v1*v2;pushfstack(a,v);}
else if(getcstack(b)=='/')
{popfstack(a,v1);popfstack(a,v2);v=v2/v1;pushfstack(a,v);}
else if(getcstack(b)=='(')
{
if(c==')')
popcstack(b,s);
else
pushcstack(b,c);
}
}
}
#include<stdio.h>
main()
{
fstack shu;
cstack fu;
char c[maxsize];
int i;
float x;
emptyfstack(shu);
emptycstack(fu);
printf("输入算式,开始结束以#号为标识:");
scanf("%s",c);
for(i=0;c[i]!='\0';i++)
{
if(c[i]>='0'&&c[i]<='9')
{
for(x=0.0;c[i]>='0'&&c[i]<='9';i++)
x=x*10+(c[i]-'0');
pushfstack(shu,x);
}
else if(emptyc(fu))
pushcstack(fu,c[i]);
else
oper(shu,fu,c[i]);
}
printf("%f",getfstack(shu));
getch();
}
[此贴子已经被作者于2006-4-2 12:31:52编辑过]
