用栈的方式实现表达式求值.doc

一、程序设计任务 掌握栈的用法，实现表达式求值这一栈的典型应用问题：以字符序列的形式从终端输入语法正确的、不含变量的算术表达式，利用算符优先关系，实现对算术四则混合运算表达式求值。当用户输入一个合法的表达式后，能够返回正确的结果。能够计算的运算符包括：加、减、乘、除、括号 。 二、具体代码实现如下 #includeiostream.h #includefstream.h #includestring.h #includestdlib.h #includemath.h #includecstdio //cstdio本来就只是将stdio.h的内容用C++的头文件形式表现出来。 #define NULL 0 typedef struct node //定义一个结点结构体 { char date; struct node *next; }SNode; SNode *InitStack()//初始化空链栈 { SNode *top; top=new SNode;//top=(SNode *)malloc(sizeof(SNode)); top-next=NULL; return top; } void PushOptr(SNode *top,char x)//运算符进栈函数 { SNode *p; p=new SNode; p-date=x; p-next=top-next; top-next=p; } char PopOptr(SNode *top)//运算符出栈函数 { SNode *p; char x; if(top==NULL) return NULL; p=top-next; x=p-date; top-next=p-next; delete p; return x; } void PushOpnd(SNode *top,char x)//操作数进栈函数 { SNode *p; p=new SNode; p-date=x; p-next=top-next; top-next=p; } char PopOpnd(SNode *top)//操作数出栈函数 { SNode *p; char x; if(top==NULL) return NULL; p=top-next; x=p-date; top-next=p-next; delete p; return x; } char GetTop(SNode *top)//取栈顶元素 { return (top-next)-date; } int In(char c) { int n; switch(c) { case +: case -: case *: case /: case (: case ): case %: case ^: case #: n=1;break; default : n=0;break; } return n; } char Precede(char x,char y) //符号优先级规则说明 { int i,j; int form[9][9]= { {1,1,-1,-1,-1,1,-1,-1,1}, {1,1,-1,-1,-1,1,-1,-1,1}, {1,1,1,1,-1,1,1,-1,1}, {1,1,1,1,-1,1,1,-1,1}, {-1,-1,-1,-1,-1,0,-1,-1,2}, {1,1,1,1,2,1,1,1,1}, {1,1,1,1,-1,1,1,-1,1}, {1,1,1,1,-1,1,1,1,1}, {-1,-1,-1,-1,-1,2,-1,-1,0} }; //定义一个二维数组存放运算符优先级 switch(x) { case +:i=0;break; case -:i=1;break; case *:i=2;break; case /:i=3;break; case (:i=4;break; case ):i=5;break; case %:i=6;break; case ^:i=7;break; case #:i=8;break; } switch(y) { case +:j=0;break; case -:j=1;break; case *:j=2;break; case /:j=3;break; case (:j=