数据结构表达式求值代码.doc

/代码部分：#includeusing namespace std;#define MAXSIZE 100typedef char ElemType;/定义栈typedef structchar aMAXSIZE;int top;/栈顶指针SqStack;char op8=+,-,*,/,(,),#;/运算符集char ch77= /运算符优先关系集 , , , , , , , ,= ;void InitStack(SqStack &s) for(int i=0;iMAXSIZE;i+)s.ai=0;s.top=0;char Push(SqStack &s,ElemType e)if (s.top=MAXSIZE-1) coutOverflow!endl;elses.top=s.top+1;s.as.top-1=e;return e;ElemType Pop(SqStack &s,ElemType &e)if (s.top=0) coutStack is empty!endl; return(-1);else e=s.as.top-1;s.top=s.top-1;return e;ElemType GetTop(SqStack s,ElemType& e)if (s.top=0) coutStack is empty!endl; return(-1); elsee=s.as.top-1;return e;bool ifnot(char c)/判断是否是运算符for(int i=0;i8;i+)if (c=opi)return 1;return 0;int FirstValue(char ch) /判断字符在数组中的位置int k;switch(ch)case +:k=0;break; case -:k=1;break; case *:k=2;break; case /:k=3;break; case (:k=4;break; case ):k=5;break; case #:k=6;break;return k;char Precede(char ch1,char ch2)/判断优先关系的函数 int i=0,j=0;i=FirstValue(ch1);/调用函数j=FirstValue(ch2);/调用函数return chij;/返回优先关系的字符char Operate(int ch3,char theta ,int b)int result;if(theta=+)result=(ch3-0)+(b-0);if(theta=-)result=(ch3-0)-(b-0);if(theta=*)result=(ch3-0)*(b-0);if(theta=/)result=(ch3-0)/(b-0);return (result+0);int main() char c;/用来接收字符char x,theta,e,b,a1,m;/定义临时的字符变量x=m=theta=e=b=a1=NULL;/给临时变量赋值SqStack OPTR,OPND;/定义运算符栈和操作数栈InitStack(OPTR);Push(OPTR,#);/初始化，让#是运算符栈底元素InitStack(OPND);/初始化操作数栈cout请输入表达式，以#结束endl;c=getchar();while(c!=#|GetTop(OPTR,e)!=#)if(!ifnot(c)/判断是否是运算符Push(OPND,c);c=getchar();/不是运算符则进栈elseswitch (Precede(GetTop(OPTR,e),c)case:Pop(OPTR,theta);Pop(OPND,b);Pop(OPND,a1);/退栈并将运算结果入栈Push(OPND,Operate(a1,theta,b);break;/s