用堆栈实现表达式计算

用堆栈实现表达式计算

--------------------------------------------------------------------------------


一个用堆栈实现表达式计算的例子，程序引入两个栈，运算分量栈和运算符栈。程序在对表达式求值时，
按自左至右顺序扫描数字表达式，当遇到数字时，将数进运算分量栈；遇运算符时，先用它的优先级和
运算符栈顶运算符的优先级进行比较，优先级高进栈；反之，则出栈处理。

#include
#include
#include

#define MUL 1
#define ADD 2
#define SUB 3
#define END 4

struct{
char op;
int code;
}opchTbl[]={{'*',1},{'+',2},{'-',3},{'#',4}};

typedef struct node{/* ...堆栈数据... */
double data;
struct node *link;
}LNODE;

int osp[] = {3,1,1,0}; /* ...　×(乘）+（加）-（减）#(结束符）的优先级 ... */
LNODE *optop,*numtop;

void l_push(double x,LNODE * *toppt) /* ...链接存储栈的进栈函数... */
{
LNODE *p = (LNODE *)malloc(sizeof(LNODE));
p->data = x;
p->link = *toppt;
*toppt = p;
}

int l_pop(double *cp,LNODE * *toppt) /* ...链接存储栈的出栈函数... */
{
LNODE *p = *toppt;
if(*toppt == NULL)return 1; /* ...空栈... */
*cp = p->data;
*toppt = p->link;
free(p);
return 0;
}

double eval(char tag,double left,double right)
{
switch(tag){/* */
case MUL : return left*right;
case ADD : return left+right;
case SUB : return left-right;
}
}

My_delay(int n) /* ...延时函数调用... */
{
int i;
for(i=0;idelay(50000);
}

void synError()
{

}

main()
{
int cts[]={40,5,6,7},opTbl[]={3,2,1,4}; /* ...cts算式数据 opTbl算式符数组都可改动... */
double num,op,operand1,operand2,res;
int type,i=0,j=0;

clrscr(); /* ...清屏函数... */
printf("Please wait for...n");
optop = numtop =NULL;
while(1){/* */
num = (double)cts[i++];
printf("num=%fn",num); /* ...调试加的语句可以不要... */
l_push(num,&numtop); /* ...数据进算式分量栈... */
type = opTbl[j++];
printf("type=%dn",type); /* ...调试加的语句可以不要... */
getch();
if(optop==NULL) l_push((double)type,&optop); /* ...运算符栈... */
else{

if(osp[type-1] > osp[(int)optop->data-1]) /* ...栈外算术符优先级高进栈... */
l_push((double)type,&optop);
else{/* */
l_pop(&op,&optop); /* ...运算符出栈.... */
l_pop(&operand2,&numtop); /* ...运算分量2出栈... */
l_pop(&operand1,&numtop); /* ...运算分量1出栈... */
re

s = eval(op,operand1,operand2);
printf("res=%fn",res); /* ...调试加的语句可以不要... */
l_push(res,&numtop); /* ...运算结果进栈... */
if(type==END){
while(!l_pop(&op,&optop)){
l_pop(&operand2,&numtop);
l_pop(&operand1,&numtop);
res = eval(op,operand1,operand2);
l_push(res,&numtop);
}
break;
} /* ...if end... */
l_push((double)type,&optop);
}

}

} /* ...while end... */

if(l_pop(&operand1,&numtop))synError(); /* ...计算结果出栈... */
while(optop != NULL) l_pop(&op,&optop);
while(numtop != NULL) l_pop(&res,&numtop);
printf(" 40%c5%c6%c7=%dn",opchTbl[opTbl[0]-1].op,opchTbl[opTbl[1]-1].op,opchTbl[opTbl[2]-1].op,(int)operand1);
printf(" 2003-11-20n");

My_delay(50);
}