算术表达式求值问题课程设计报告.docx

《算术表达式求值问题课程设计报告.docx》由会员分享，可在线阅读，更多相关《算术表达式求值问题课程设计报告.docx（14页珍藏版）》请在三一办公上搜索。

1、合肥学院算术表达式求值演示一、问题分析和任务定义实验题目： 算术表达式求值：一个算术表达式是由操作数（ operand ）， 运算符（ operator ）和界限符（ delimiter ）组成的。假设操作数是正整数， 运算符只含加减乘除等四种运算符，界限符有左右括号和表达式起始，结束 符“#”，如：#（7+15）* （23-28/4 ）#。引入表达式起始、结束符是为了方 便。编程利用“算符优先法”求算术表达式的值。要求： （1） 从键盘读入一 个合法的算术表达式，输出正确的结果。 （2） 显示输入序列和栈的变化过 程。选作内容：操作数类型扩充到实数。问题分析： 在带括号的的算术表达式中，界限

2、符包括左右括号以及表达 式起始、结束符“ #”。假设运算符只有加、减、乘、除 4 种，则对一个简单 的算术表达式的运算规则如下：（ 1） 从左至右运算表达式。（ 2） 先乘、除，后加、减。（3）先括号内，后括号外。 要想能够实现这个问题，首先，你要从键盘中输入一个字符并判别该 字符是运算符还是运算数。 如果是运算数就直接进运算数栈。 如果是运算符， 则与运算符栈的栈顶元素进行优先级的比较 （ 可以单独写一个优先级比较函 数，将每个运算符与其他运算符之间的优先级一一比较出来，可以设置为 “”、“”，则将运算数栈依次出栈两次，将 该运算符和刚出栈的两个运算数进行计算 （ 单独写一个函数，将“ +”

3、、“ - ”、 “*”、“/ ”四种情况一一写出来 ） ，然后将计算的结果入运算数栈，将读入 的运算符入运算符栈；如果比较后为“ ”，但要注意如果从运算符栈出栈的元素为“ #”和“（”，则 运算数栈无需出栈，并且运算符栈也无需入栈。按照上面的步骤，一一读完 所有的字符。这样，运算数栈中最后剩下的元素就是该算术表达式的最终结 果。注意 ：整个算法结束的条件是运算符栈为空。 （即表达式的起始、结束符相遇 ） 任务定义： 为统一算法的描述，将运算符和界限符统称为算符。这样， 算符集为+，-，*，/，（，），#。根据上述 3 条运算规则，两个前后相继出 现的算符 a1、a2 间的优先关系可以归纳如下：

4、（1）若 a1、a2 同为“ *”、“ / ”或同为“ +”、“ - ”，则运算符 a1 的优先级大于 a2。（2）“*”、“ / ”的优先级大于“ +”、“- ”。（3）由于“先括号内，后括号外”，若 a1 为“ +”、“ -”、“ *”、 “/ ”，a2为“（”；或者， a1为“（”，而 a2为“+”、“- ”、 “*”、“ /”，则 a1的优先级小于 a2。4) 同理，若 a1 为“ +”、“ - ”、“ * ”、“ / ”， a2 为“)”；或 者，a1 为“)”，而 a2 为“ +”、“ - ”、“ * ”、“ / ”，则 a1 的优先级小于 a2。5) 若 a1,a2 同为“(”，

5、则 a1 的优先级小于 a2；若 a1,a2 同为“)”， 则 a1 的优先级大于 a2 。6) 表达式的起始、 结束符“ #”的优先级小于其他所有合法出现的算 符。(7)若 a1 为“(”， 优先级相同。a2为“)”或 a1，a2同为“ #”，则 a1，a2 的表 1 ：算符 a1和 a2间的关系a1 a2 +-/()#+-/(-# 测试用例：sum=0pushfu(OPTR, c); cinc;popfu(OPTR,& x); cinc;popfu(OPTR,&t) popshu(OPND,&b) popshu(OPND,&a) pushshu(OPND,opr eate(a,t,b)su

6、m=sum*10- ( c-0) pushshu(OPND,sum);13、进行运算函数： int opreate(int a,char fu,int b)； 主函数实现的流程图如下：gettop2(OPND)图 1 ：主函数的流程三、详细设计和编码1、初始化运算符类型的栈思想：申请一个运算符栈类型的指针变量后，将它的 top 置为-1，即使它为空，然后返回该指针。void initstack1(stack1 *s) s=(stack1 *)malloc(sizeof(stack1);s-top=-1;2、初始化运算数类型的栈思想：申请一个运算数栈类型的指针变量后，将它的 top 置为-1，即

7、使它为空，然后返回该指针。void initstack2 (stack2 *s) s=(stack2 *)malloc(sizeof(stack2);s-top=-1;3、入运算符栈思想：如果要入的栈不满，就使它的 top加 1，然后将要插入的算 符赋值给 top 指向的 data域中。void pushfu (stack1 *s,char c) if(s-top=maxlen-1) cout 栈已满，输入错误 !top)+; s-datas-top=c;4、入运算数栈思想：如果要入的栈不满，就使它的 top加 1，然后将要插入的算 符赋值给 top 指向的 data 域中。void push

8、shu (stack2 *L,int p) if(L-top=maxlen-1) cout 栈已满，输入错误 !top)+; L-dataL-top=p;5、出运算符栈思想：先将该栈的栈顶元素赋值给同类型的形参变量，然后使得 top 减 1。void popfu(stack1 *s,char *p) *p=s-datas-top;(s-top)-;6、出运算数栈思想：先将该栈的栈顶元素赋值给同类型的形参变量，然后使得 top 减 1。void popshu(stack2 *s,int *p) *p=s-datas-top;(s-top)-;7、得到运算符栈的栈顶元素char gettop1(s

9、tack1 *s) return s-datas-top;8、得到运算数栈的栈顶元素int gettop2(stack2 *s) return s-datas-top;9、输出运算符栈里的所有算符 void visitoptr(stack1 *c)int i; for(i=0;itop;i+) coutdatai; couttt;10、输出运算数栈里的所有算数void visitopnd(stack2 *c ) int i;for(i=0;itop;i+) coutdatai,;coutendl; 11、判断字符 c 是不是运算符：思想是如果该字符等于“ +” “ /”，“（”，“）”，“#”

10、中的一个就是运算符，并返回确认 1， 0。int judge (char c) if(c=+)|(c=-)|(c=*)|(c=/)|(c=()|(c=#)|(c=) return 1;else return 0;12、判断优先级：思想见上面任务定义部分。char youxianji(char ch1,char ch2) char ch;switch(ch1)/将 ch1和 ch2 相比较 case+:if(ch2=*)|(ch2=/)|(ch2=() ch=;break; case-:if(ch2=*)|(ch2=/)|(ch2=() ch=;break; case*:if(ch2=() ch

11、=;break;case/:if(ch2=() ch=;break;case(:if(ch2=) ch=;else ch=;break;case#:if(ch2=#) ch=;else ch=top=-1;return (s);将初始化运算数栈的函数更改为： stack2 *initstack2 () stack2 *s;s=(stack2 *)malloc(sizeof(stack2);s-top=-1;return (s);这时程序才能正常的读写内存。(4) 、在测试程序时，发现如果输入了一个不是个位数的数时，程序的运行结 果错误。经检查发现在读入字符时， 一个大于个位数的数是分开来从左向

12、右一个 一个的输入的， 所以在主函数中读入数时要定义一个开关变量， 来判别读入的数 下一个字符是否还是一个数，如果是就将该数乘以 10 并赋值给总量后继续读入 下个数；如果不是就将得到的总量直接放入运算数栈中并读入一个运算符。2、算法性能分析(1) .算法时间性能分析 对于算术符优先级比较算法，首先将每个待入栈的运算符判断，这样若有 n 个算术符，则要判断 n 次，而接下来又需对栈顶运算符比较，这样，又 可分为两种情况， a.栈顶元素优先级高于待入栈运算符， b.栈顶元素优先级 低于待入栈运算符，共需判断 2n 次，而在判断前以判断了 n 次，所以，这 一种情况的比较次数就为 2n2 次，像这

13、样的情况共有 5 种，综合时间复杂 度为 T(n)=O(5*2*n2 )=O(10*n2) 对于表达式格式判定算法，因比较复杂，外层为 3 种情况，而其中一种 又有 5 种情况，这样若有 n 个字符，则总的判断次数为： n*n*(3*n2+n+n3 ), 所以时间复杂度 T(n)=O(n5+3n4+n4)(2) .空间性能分析一个算术表达式输入时，存储在一维数组里，对于求表达式算法，一个 表达式最少占有空间 1(只有一个数子的情况) ，最多占有空间 2n-1(n-1 个 位置全部有符号)，平均一下，平均占空间是 3n/2，所以该算法空间复杂度 是:S(n)=(3n/2)*4 n-1,取 f(n

14、)=n*2 2n ,limS(n)/f(n)=3/8 。所以空间复杂度为： O(n*22n)。对于表达式求值出入栈算法，若该表达式共有 n 个字符，而共有运算符 栈和运算数栈，所以平均为 n2/4，这样，空间复杂度为： O(n*n2/4 )。五、测试结果与分析(1)、输入 #7+8#，结果显示如下所示：图 2 ：算式 #7+8#运行截屏 结果分析：经过亲自将结果运算式计算一遍，证明程序运算正确。 控制算术表达 式结束的条件就是“ gettop2(OPTR)= #”。(2)、输入： #9*(18+2)/(12-2)#,结果显示如下所示：图 3：算式 #9*(18+2)/(12-2)# 运行截屏

15、结果分析：该表达式输入了十位数，使得程序的功能得到充分实现。六、用户使用说明1. 打开“ Debug”文件夹，运行“算术表达式求值问题 .exe ”。2. 用户输入想要求值的算术表达式并以“ # ”结束。3. 程序会自动显示每步操作并同时显示两个栈的变化过程，最终输出正 确的结果。4. 用户选择“ Y”或者“ y”继续输入表达式求值；选择“ N”或者“ n” 时，按“ Enter ”键就会直接退出。七、参考文献1 王昆仑，数据结构与算法，北京：中国铁道出版社， 20072 谭浩强， c 程序设计，北京：清华大学出版社， 20053 郑莉、董渊、张瑞丰， C+语言程序设计，北京：清华大学出版社，

16、 20034 严蔚敏，数据结构：语言版，北京：清华大学出版社， 20025 胡学钢，数据结构与算法设计指导，北京：清华大学出版社， 19996 徐士良，常用算法程序集，北京：清华大学出版社， 19957 关治、陈景良，数值计算，北京：清华大学出版社， 1993八、附录： 源程序 #include #include#define maxlen 100 using namespace std;int n=0;/ 定义一个全局变量 n 并赋值为 0 typedef struct /创建运算符栈的类型 char datamaxlen;int top;stack1;typedef struct /创建运

17、算数栈的类型 int datamaxlen;int top;stack2;int judge (char c) /判断字符 c 是不是运算符 if(c=+)|(c=-)|(c=*)|(c=/)|(c=()|(c=#)|(c=) return 1;else return 0;stack1 *initstack1() / 初始化运算符类型的栈 stack1 *s; s=(stack1 *)malloc(sizeof(stack1);s-top=-1;return (s);stack2 *initstack2 ()/ 初始化运算数类型的栈 stack2 *s;s=(stack2 *)malloc(s

18、izeof(stack2); s-top=-1;return (s);void pushfu (stack1 *s,char c) /入运算符栈 if(s-top=maxlen-1) cout 栈已满，输入错误 !top)+; s-datas-top=c;void pushshu (stack2 *L,int p)/入运算数栈 if(L-top=maxlen-1) cout 栈已满，输入错误 !top)+;L-dataL-top=p;void popfu(stack1 *s,char *p) / 出运算符栈 *p=s-datas-top;(s-top)-;void popshu(stack2

19、*s,int *p) / 出运算数栈 *p=s-datas-top;(s-top)-;char youxianji(char ch1,char ch2)/判断优先级 char ch;switch(ch1)/将 ch1和 ch2 相比较 case+:if(ch2=*)|(ch2=/)|(ch2=() ch=;break; case-:if(ch2=*)|(ch2=/)|(ch2=() ch=;break; case*:if(ch2=() ch=;break;case/:if(ch2=() ch=;break;case(:if(ch2=) ch=;else ch=;break; case#:if(

20、ch2=#) ch=;else ch=datas-top;int gettop2(stack2 *s) /得到运算数栈的栈顶元素 return s-datas-top;int opreate(int a,char fu,int b) /进行运算函数 int s;switch(fu) case+:s=a+b;break;case-:s=a-b;break;case*:s=a*b;break; case/:s=a/b;break;return s;void visitoptr(stack1 *c)/ 输出运算符栈里的所有算符 int i; for(i=0;itop;i+) coutdatai; c

21、outtt;void visitopnd(stack2 *c)/ 输出运算数栈里的所有算数 int i;for(i=0;itop;i+) coutdatai,;coutendl;void printstep()/ 输出步骤编号n+;coutntt;void main()char c,t,x,jixu;int i=0,sum=0;int k=1,j=1;/ 设置了开关变量int a,b;stack1 *OPTR;/定义运算符栈 OPTR stack2 *OPND;/ 定义运算数栈 OPND OPTR=initstack1();/初始化运算符栈 pushfu(OPTR,#);/#号压入栈 OPTR

22、OPND=initstack2();/ 初始化运算数栈for(;)cout 请输入算术表达式并以 #号结束(形如 3*(4+5)#):endl; coutc;cout*表达式求值演示 *endl;cout步骤tt;cout操作 tt;cout运算符栈 t;cout 运算数栈 endl;printstep();/第一步是将 #号入栈 OPTRcout# 号入运算符栈 tt;visitoptr(OPTR);coutttc;pushshu(OPND,sum);/将得到的数入运算数栈 printstep();/输出步骤，操作，以及运算符栈、运算数栈的变化 cout输入sumttt;visitoptr(

23、OPTR);visitopnd(OPND);j=1;elseif(k)switch(youxianji(gettop1(OPTR),c)/ 如果得到的数据是运算符，就将 它和运算符栈的栈顶元素比较优先级case: pushfu(OPTR,c);/如果 c 的优先级小于栈顶运算符， 就将 c 入运算符栈并继续输入printstep();coutc 入运算符栈 c;break;case=: popfu(OPTR,&x);/ 如果 c 的优先级等于栈顶运算符，就 将运算符栈栈顶运算符出栈并继续输入printstep();coutx 出栈运算符栈 c;break;case: popfu(OPTR,&t

24、); / 如果 c 的优先级等于栈顶运算符， 先输出运算符栈顶元素，然后输出运算数栈的栈顶和次栈顶元素并计算 printstep();coutt 出运算符栈 tt;visitoptr(OPTR);visitopnd(OPND);popshu(OPND,&b);/ 注意这里是谁先出栈printstep();coutb 出运算数栈 tt;visitoptr(OPTR);visitopnd(OPND);popshu(OPND,&a);printstep();couta出运算数栈 tt;visitoptr(OPTR);visitopnd(OPND);pushshu(OPND,opreate(a,t,b);printstep();couta与b相t 后入运算数栈 t;visitoptr(OPTR);visitopnd(OPND);break;cout 运算结果是： gettop2(OPND)endl;coutjixu;if(jixu=n) exit(0);