用栈计算数学表达式的值

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

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

3、plateclass stackpublic:stack(int sz=100);stack()deleteelement;bool push(T x);bool pop(T &x);bool getTop(T &x);bool IsEmpty()return top=-1?true:false;bool Full()return top=maxsize-1?true:false;int getsize()return top+1;private:T *element;int top;int maxsize;templatestack:stack(int sz)top=-1;maxsize=s

4、z;element=new Tmaxsize;templatebool stack:push(T x)if(Full()return false;else element+top=x;return true;templatebool stack:pop(T &x)if(IsEmpty()return false;else x=elementtop-;return true;templatebool stack:getTop(T &x)if(IsEmpty()return false;elsex=elementtop;return true; 2、 主程序的实现#includeStack.h#i

5、ncludestring.h#includeusing namespace std;bool IsOperator(char ch)if(ch=+|ch=-|ch=*|ch=/)return true;else return false;int judge(char ch)if(ch=+|ch=-)return 1;else if(ch=*|ch=/)return 2; else if(ch=(|ch=#)return 0;int cal(int n1,int n2,char ch)if(ch=+)return n1+n2;else if(ch=-)return n1-n2; else if(

6、ch=*)return n1*n2; else if(ch=/)return n1/n2;char *postfix(char *s1)int i=0,j=0;char *s2=new char2*strlen(s1),ch=s10,c;stackcs;cs.push(#);while(ch!=0)if(IsOperator(ch)if(s2j-1!= &!IsOperator(s2j-1)s2j+= ;cs.getTop(c);if(judge(ch)judge(c)cs.push(ch);elsecs.pop(c);s2j+=c;i-;if(ch=()cs.push(ch);if(ch=)

7、s2j+= ;cs.pop(c);while(c!=()s2j+=c;cs.pop(c);if(ch=0&ch=9)s2j+=ch;i+;ch=s1i;if(!IsOperator(s2j-1)s2j+= ;cs.pop(c);while(c!=#)s2j+=c;cs.pop(c);s2j=0;return s2;int cal_post(char *s)stackints;int i=0,t=0;char ch=s0;while(ch!=0)if(ch=0)t=t*10+ch-0;if(ch= )ints.push(t);t=0;if(IsOperator(ch)int n1,n2;ints

8、.pop(n2);ints.pop(n1);ints.push(cal(n1,n2,ch);i+;ch=si;ints.pop(t);return t;void main()char *s1=new char 100,*s2,x;bool a=true,b;while(a)b=true;couts1;s2=postfix(s1);couts1=cal_post(s2)endl;coutx;if(x=n|x=N)a=false;b=false;else if(x=y|x=Y)b=false; elsecout输入错误！请重新输入：;b=true;delete s2;delete s1;五、 调试分析1、 设计与调试过程中遇到的问题及分析、体会遇到的最大的问题就是：动态申请的空间不知道应该什么时候释放，开始时一直出现这种问题，后来请教同学，又问了老师，才完全把这一问题解决。还有就是一些细节问题，将算式转化为后缀式时，分的那几种情况，是并列关系，开始时，写了三个if 一个else，但是应该是四种并列。在将算式转化为后缀式后，s2最后没有