C|【数据结构】之表达式求值 C语言|表达式求值|数据结构

如要下载编译器，请看我的之前博客
笔者现大三，这篇博文及后面的几篇博文都是对大二所做的题目一些总结，哈哈，感觉自己那时候学的还可以，希望自己这点笔记能对你们有点帮助吧，加油！！！其实数据结构也没传说中的那么难，并且以后在我们面试的时候，数据结构可是面试官的法宝，对吧，咱们不能输在起跑线线上，好了，废话不多说，现在让我们来学习表达式求值。我先把老师给我们出的题目给大家看看吧，不知道我们是不是一样的（纯洁的微笑），题目如下：
利用栈实现算术表达式的求值，表达式中可包含加+、减（负） -、乘*、除/、
乘方^、括号( )运算符，操作数可以为浮点数。可采用直接求中缀表达式的方法，
也可采用先转换成后缀表达式后再求值的方法（参看课件）。
实现时需注意如下：
（ 1）带小数点的数值生成（理解整数数值的生成，小数部分的处理与之类似）。
（ 2）考虑负号的情况。负号与减号形式上一样，如何区分？
? 输入的表达式串中第 1 个字符是’-’
– 可断定此’-’是负号
? 其余的’-’
– 若紧接在’(’之后的’-’可断定是负号
（ 3）负号的处理
? 方法 1：若已断定是负号，可先压入数值 0 进入操作数栈，如此，可
将负号看作减号。
? 方法 2：若已断定是负号，则紧接其后的数字字符转换成数值后，要
将其对应的相反数(负数)压入操作数栈。
工程截图：

先建一个工程，头文件就不贴了，源代码里有，如果有需要，下面有下载地址，我们重点讲如何利用栈进行表达式求值的，
求表达式基本思想就是，首先读取输入的字符串，然后分别读出数字和操作符，如果是数字压入数字栈，如果是操作符与之前的操作符比较优先级，如果大，从数字栈中取出俩个数字运算再放入数字栈，如果小，操作符就压入操作符栈，遇到“=”停止，输入数字栈中的栈顶元素即为运算结果，代码如下(other.cpp)：

#include"Sqstack.h" #include"other.h"double EvluateExpression(char str[],LinkStack &OPTR,LinkStack1 &OPND) { int i=0,t,j,falg=0; double a,b,sum,s; char theta,x; InitStack(OPND); InitStack(OPTR); Push(OPTR,'#'); if(str[0]=='-') { Push(OPND,0); } while(str[i] !='#' || GetTop(OPTR)!='#') { if(str[i]>='0' && str[i]<='9') { sum=0; while(str[i]>='0' && str[i]<='9')//将整数保存到sum中 { sum=sum*10+str[i++]-'0'; } if(str[i]=='.')//如果有小数点，将j移动下一个运算符之前的字符，从那个字符开始往后依次除10，直到小数点之后的那一位字符，与sum相加 { s=0; j=i+1; while(str[j]>='0' && str[j]<='9') { j++; } for(t=j-1; t>i; t--) { s=s/10+str[t]-'0'; } s=s/10; //printf("%lf\n",s); sum=sum+s; i=j; } Push(OPND,sum); } else { if(str[i]=='-' && str[i-1]=='(') { Push(OPND,0); } switch(Precede(GetTop(OPTR),str[i])) { case '<': Push(OPTR,str[i]); i++; break; case '>':Pop(OPTR,theta); Pop(OPND,b); Pop(OPND,a); Push(OPND,Operate(a,theta,b)); break; case '=': Pop(OPTR,x); i++; break; } } } return GetTop(OPND); }char Precede(char a, char b) { int i,j; char Ns[7]={'+','-','*','/','(',')','#'}; char str[7][7]={'>','>','<','<','<','>','>', '>','>','<','<','<','>','>', '>','>','>','>','<','>','>', '>','>','>','>','<','>','>', '<','<','<','<','<','=',' ', '>','>','>','>',' ','>','>', '<','<','<','<','<',' ',' '}; for(i=0; i<7; i++) { if(Ns[i]==a) break; } for(j=0; j<7; j++) { if(Ns[j]==b) break; } return str[i][j]; } double Operate(double a,char op,double b) { switch(op) { case '+':return a+b; break; case '-':return a-b; break; case '*':return a*b; break; case '/':return a/b; break; } }

栈的基本操作函数（Sqstack.cpp）

#include"Sqstack.h" #include"other.h"void InitStack(LinkStack &OPTR) { OPTR=NULL; } void InitStack(LinkStack1 &s) { s=NULL; } void Push(LinkStack &OPTR,char e) { LinkStack p; p=new StackNode; p->data=https://www.it610.com/article/e; p->next=OPTR; OPTR=p; } void Push(LinkStack1 &s,double e) { LinkStack1 p; p=new StackNode1; p->data=https://www.it610.com/article/e; p->next=s; s=p; } charGetTop(LinkStack &OPTR) { if(OPTR!=NULL) return OPTR->data; } doubleGetTop(LinkStack1 &s) { if(s!=NULL) return s->data; } void Pop(LinkStack &s,char &e) { LinkStack p; e=s->data; p=s; s=s->next; delete p; } void Pop(LinkStack1 &s,double &e) { LinkStack1 p; e=s->data; p=s; s=s->next; delete p; } void DestoryStack(LinkStack &s) { LinkStack p; while(s) { p=s; s=s->next; delete p; } } void DestoryStack(LinkStack1 &s) { LinkStack1 p; while(s) { p=s; s=s->next; delete p; } } int StackEmpty(LinkStack s) { if(s==NULL) return ERROR; } int StackEmpty(LinkStack1 s) { if(s==NULL) return ERROR; }

截图：