用栈计算数学表达式的值.doc

《用栈计算数学表达式的值.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验4用栈计算表达式的值一、问题描述实现栈，并基于栈求表达式的值。二、需求分析1、简述程序的基本功能将输入的一个表达式转化为后缀式，并计算该算式的值。2、输入的形式和输入值的范围输入的必须是一个整型算式，可以包含加减乘除以及小括号。运算完成后，提示输入Y/N，输入为字符型，用以判断是否继续运算。3、输出的形式每一次运算后，输出运算结果为整型。4、测试数据要求要求输入的必须为运算式，即只能有整型数字加减乘除以及小括号。三、概要设计1、抽象数据类型有一个类classstack，它含有三个数据成员：*element、top、maxsize；分别表示栈中元素、栈顶位置、栈的

2、容量。还有几个成员函数用来进行进栈、出栈、取出栈顶元素、判断栈是否为空等操作。2、主程序流程及模块调用关系a)定义char型指针变量s1，并为之申请了100个数据的空间；b)用while循环语句开始运行程序；c)键盘输入s1，即数学表达式；d)程序运算并输出结果，然后提示是否继续运算，请求输入字符Y/N；e)输入y或Y时，程序继续进行while循环，进行运算；输入n或N时，程序结束；若输入其他字符，提示输入错误，要求重新输入。四、详细设计（要求主要变量和语句加注释）1、抽象数据类型的实现：包括类型定义和各个操作的实现。#includeusingn

3、amespacestd;templateclassstack{public:stack(intsz=100);~stack(){delete[]element;};boolpush(Tx);boolpop(T&x);boolgetTop(T&x);boolIsEmpty(){returntop==-1?true:false;};boolFull(){returntop==maxsize-1?true:false;};intgetsize(){returntop+1;};private:T*element;inttop;intmaxsize;};tem

4、platestack::stack(intsz){top=-1;maxsize=sz;element=newT[maxsize];}templateboolstack::push(Tx){if(Full())returnfalse;elseelement[++top]=x;returntrue;}templateboolstack::pop(T&x){if(IsEmpty())returnfalse;elsex=element[top--];returntrue;}templatebo

5、olstack::getTop(T&x){if(IsEmpty())returnfalse;elsex=element[top];returntrue;}1、主程序的实现#include"Stack.h"#include"string.h"#includeusingnamespacestd;boolIsOperator(charch){if(ch=='+'

6、

7、ch=='-'

8、

9、ch=='*'

10、

11、ch=='/')returntrue;elsereturnfalse;}intjudge(charch){if(ch=='+'

12、

13、ch=='-')r

14、eturn1;elseif(ch=='*'

15、

16、ch=='/')return2;elseif(ch=='('

17、

18、ch=='#')return0;}intcal(intn1,intn2,charch){if(ch=='+')returnn1+n2;elseif(ch=='-')returnn1-n2;elseif(ch=='*')returnn1*n2;elseif(ch=='/')returnn1/n2;}char*postfix(char*s1){inti=0,j=0;char*s2=newchar[2*strlen(s1)],ch=s1[0],c;stack

19、ar>cs;cs.push('#');while(ch!=''){if(IsOperator(ch)){if(s2[j-1]!=''&&!IsOperator(s2[j-1]))s2[j++]='';cs.getTop(c);if(judge(ch)>judge(c)){cs.push(ch);}else{cs.pop(c);s2[j++]=c;i--;}}if(ch=='('){cs.push(ch);}if(ch==')'){s2[j++]='';cs.pop(c);while(c!='('){s2[j++]=c;cs.pop(c);}}if(ch>='