数据结构与算法表达式求值案例.pptx

表达式求值;什么是表达式？;表达式的三大类;从右至左扫描表达式， 遇到数字，将数字压入栈; 遇到运算符，弹出栈顶的两个数， 用运算符对它们做相应的计算（栈顶元素 operate with 次顶元素），并将结果入栈； 重复上述过程直到表达式最左端，最后运算得出的值即为表达式的结果。 ;Eg. 前缀表达式“- × + 3 4 5 6”：;中缀表达式的计算机求值;Eg.中缀表达式“1+((2+3)×4)-5”转换为前缀表达式之后求值;与前缀表达式类似，只是顺序是从左至右 从左至右扫描表达式， 遇到数字，将数字压入栈; 遇到运算符，弹出栈顶的两个数，用运算符对它们做相应的计算（次顶元素 operate with 栈顶元素），并将结果入栈； 重复上述过程直到表达式最右端，最后运算得出的值即为表达式的结果。;Eg.后缀表达式“3 4 + 5 × 6 -”;Eg.将中缀表达式“1+((2+3)×4)-5”转换为后缀表达式之后求值：;利用二叉树将中缀表达式转化为后缀表达式;Eg.表达式3*5+5/2+（3+5）*2，表示成二叉树的形式;操作符优先级;系统设计;模块;typedef int Status; unsigned char Prior[8][8] = { // 制作运算符优先级表 // + - * / ( ) # ^ /*+*/,,,,,,,, /*-*/,,,,,,,, /***/,,,,,,,, /*/*/,,,,,,,, /*(*/,,,,,=, ,, /*)*/,,,, ,,,, /*#*/,,,,, ,=,, /*^*/,,,,,,, }; ;typedef struct StackChar { char c; struct StackChar *next; }SC; //StackChar类型的结点SC typedef struct StackFloat { float f; struct StackFloat *next; }SF; //StackFloat类型的结点SF SC *Push(SC *s,char c) //SC类型的指针Push，返回p { SC *p=(SC*)malloc(sizeof(SC)); p-c=c; p-next=s; return p; } SF *Push(SF *s,float f) //SF类型的指针Push，返回p { SF *p=(SF*)malloc(sizeof(SF)); p-f=f; p-next=s; return p; } ;SC *Pop(SC *s) { //SC类型的指针Pop SC *q=s; s=s-next; free(q); return s; } SF *Pop(SF *s) { //SF类型的指针Pop SF *q=s; s=s-next; free(q); return s; } ;float Operate(float a,unsigned char theta, float b) { //计算加减乘除 switch(theta) { case +: return a+b; case -: return a-b; case *: return a*b; case /: return a/b; case ^: return pow(a,b); default : return 0; } } char OPSET[OPSETSIZE]={+,-,*,/,(,),#,^}; Status In(char Test,char *TestOp) { int Find=false; for (int i=0; i OPSETSIZE; i++) { if(Test == TestOp[i]) Find= true; } return Find; ;} Status ReturnOpOrd(char op,char *TestOp) {??for(int i=0; i OPSETSIZE; i++) {??if (op == TestOp[i])???return i;?}} char precede(char Aop, char Bop) {??return Prior[ReturnOpOrd(Aop,OPSET)][ReturnOpOrd(Bop,OPSET)];?}? float EvaluateExpression(char* MyExpression) {? // 算术表达式求值