表达式的计算

班级：计科111班学号：2011081113姓名：罗明芳题目：计算表达式的值一:问题描述问题描述：计算表达式的值，对于给定的一个表达式，表达式中可以包括整数或小数、算术运行符(“+”、“-”、“*”、“/”)和括号，编写程序计算表达式的值。2•基本要求：从键盘输入一个正确的中缀表达式，将中缀表达式转换为对应的后缀表达式，计算后缀表达式的值。二:需要分析软件的基本功能本程序能计算出含+、-、*、/、(、)等运算符的简单运算。输入的形式和输入值的范围根据题目要求与提示，在输入一个中缀表达式，输入数的范围为int或float型，此时，程序将计算出表达式的结果。当按照程序输入表达式；程序将现将中缀表达式转化为后缀表达式并计算出结果。测试数据输入一个中缀表达式，例如输入3*(4+2)/2-5#,那么输出结果是4；如果输入表达式没有结束标示符#，如3*(4+2)/2-5，那将不会输出任何结果，或出现错误结果。三:概要设计首先设计一个栈模板定义一个运算对象栈Intstack<float>n,一个运算符栈Intstackvchar>m。ADTInitStackData栈中元素具有相同类型及后进先出的特性，相邻元素具有前驱和后继关系基本操作：InitStack()前置条件：栈不存在输入：无功能：栈的初始化输出：无后置结果：构造一个空栈DestroyStack()前置条件：栈已存在输入：无功能：销毁栈输出：无后置条件：释放栈所占用的空间GetTop()前置条件：栈S已存在输入：无功能：取栈顶元素，读取当前的栈顶元素输出：若栈不空，返回当前的栈顶元素值后置条件：栈不变Push(x)前置条件：栈已存在输入：元素值X功能：入栈操作，在栈顶插入一个元素值输出：如果插入不成功，则抛出异常后置条件：如果插入成功，则栈顶增加了一个元素Pop()前置条件：栈已存在输入：无功能：出栈操作，删除栈顶元素输出：如果删除成功，返回被删元素值操作结果：删除S的栈顶元素。Empty()前置条件：栈已存在输入：无功能：判空操作，判断栈是否为空输出：如果栈为空，返回1,否则返回0后置条件：栈不变endADT对于输入的表达式进行判断如果输入错误，就提示出来，并返回1如果没有错误，就返回0intjudge(chara[])如果返回0,就继续进行以下运算，否则返回主界面中缀表达式变后缀表达式voidorder(chara[])伪代码如下：将运算符栈s初始化为空栈。从左到右依次扫描表达式的每一个字符，执行下列操作。若当前字符是运算对象，则输出该字符，处理下一个字符若当前字符是运算符且优先级比栈s的栈顶运算符的优先级高，则将字符入栈s，处理下一个字符。若当前字符是运算符且优先级比栈s的栈顶运算符的优先级低，则将栈s的栈顶元素弹出并输出。若当前字符是运算符且优先级与栈s的栈顶运算符的优先级相等，则将栈s的栈顶元素弹出,处理下一字符。算出表达式的结果voidFunction(chara[])伪代码如下：将对象栈n初始化为空，将字符站m也初始化为空。从左到右扫描表达式的的每一个字符执行下列操作，指导遇到结束语‘#'2.1若当前字符是运算对象，则入栈n。2.2若当前字符是运算符且优先级比栈m的栈顶运算符的优先级高，则入栈m，处理下一个字符。2.3若当前字符是运算符且优先级比栈m的栈顶运算符的优先级低，则从栈n出栈两个运算对象，从栈m中出栈一个运算符进行运算，并将运算结果入栈n，继续处理下一个字符。2.4若当前字符是运算符且优先级与栈m的栈顶运算符的优先级相同，则将栈m的栈顶运算符出栈，处理下一个字符。输出栈n的栈顶元素，既表达式的运算结果。四•主程序流程及模块调用关系结束四：详细设计模板templatevtypenameT>structnode{Tdata;nodevT>*next;}；templatevtypenameT>classIntstack{public:friendostream&operatorvv(ostream&,IntstackvT〉&);〃运算符重载Intstack();voidpush(T);Tpop();intempty();voidget(T&,T&);TGettop();~Intstack();private:node<T>*top;};#endiftemplatevtypenameT>ostream&operatorvv(ostream&os,IntstackvT>&in)〃输出重载{while(in.top){osvvin.top->datavv'\t';in.top=in.top->next;}osvvendl;returnos;}templatevtypenameT>IntstackvT>::Intstack()〃构造函数{top=NULL;}templatevtypenameT>voidIntstackvT>::push(Tp)//入栈操作{nodevT>*s;s=newnodevT>;s->data=p;s->next=top;top=s;}templatevtypenameT>//出栈操作TIntstackvT>::pop(){nodevT>*p;Tx;p=top;x=top->data;top=top->next;deletep;returnx;}templatevtypenameT>intIntstackvT>::empty()〃判空操作{returntop==NULL?1:0;}templatevtypenameT>TIntstackvT>::Gettop(){returntop->data;〃取栈顶兀素}templatevtypenameT> 〃取栈兀素voidIntstackvT>::get(T&numl,T&num2){num1=pop();num2=pop();}templatevtypenameT>Intstack<T>::~Intstack()〃析构函数{nodevT>*p;while(top){p=top;top=top->next;deletep;}}优先级判断intprior(charp){intj=0;switch(p){case'(':case')':j=9；break;case'*':case'/':j=8;break;case'+':case'-':j=7;break;case'#':j=6;break;}returnj;}判断输入的表达式是否正确intjudge(chara[]){inti=0;intm=0;intn=0;intp=0;intr=1;while(a[i]!='#'){inty=i+l;intx=i-1;if(a[i]=='(')m++;elseif(a[i]==')')n++;elseif(a[i]>='0'&&a[i]v=9){if(a[x]==')'){-cout<<"错误"vvr<<':'<<''<<a[i]<<"没有左运算符!"<<endl;p++;r++;}if(a[y]=='('){_coutvv"错误"vvrvv':'<<''vva[i]vv"没有右运算符!"vvendl;p++;r++;}}elseif(a[i]='.'){}elseif(a[i]=='+'lla[i]=='-'lla[i]=='*'lla[i]=='/'){if(a[i]=='/'){if(a[y]=='0'){cout<< "错误"vvrvv':'vv''<<a[i]<<"后被除数不能是零！"vvendl;P++；r++;}}if(a[x]=='('lla[x]=='+'lla[x]=='-'lla[x]=='*'lla[x]=='/'){-cout<<"错误"<<r<<':'<<&□]<<"没有左运算对象!"<<endl;P++;r++;}if(a[y]==')'lla[y]=='+'lla[y]=='-'lla[y]=='*'lla[y]=='/'){_cout<<"错误"<<r<<':'<<''<<a[i]<<"没有右运算对象!"<<endl;P++;r++;}}else{if(i!=0){cout<<"错误"<<[<<':'<<"输入字符'"<<a[i]<<"'不正确!"vvendl;P++;r++;}}i++;}if(m!=n){coutvv"错误"vvrvv':'vv"左右括号不相等"vvendl;return1;if(p!=O)return1;elsereturn0;}中缀表达式变后缀表达式voidorder(chara[]){inti=0;floats=0;Intstackvchar>m;while(a[i]){if(a[i]>='0'&&a[i]v=9)//十位数以上的数据处理{s=s*10.0+(float(a[i])-48);i++;}else{if(a[i]=='.')//处理小数{floatj=1;i++;while(a[i]>='0'&&a[i]v=9){j=j*1O；intt=(float)a[i]-48;s=s+t/j;i++;}}if(s!=0)//数据输出{cout<<svv'';s=0;}if(m.empty()=l)〃字符栈空时{m.push(a[i]);i++；}else{if(prior(a[i])>prior(m.Gettop()))//当前优先级大于栈优先级{if(a[i]!=')'){m.push(a[i]);i++；}else{while(m.Gettop()!='('){cout<<m.pop()vv'';}m.pop();i++；}}elseif(prior(a[i])<prior(m.Gettop()))//当前优先级小于栈优先级{if(a[i]!='#')〃处理特殊情况#{if(m.Gettop()=='(')//处理特殊情况({m.push(a[i]);i++;}else{cout<<m.pop()vv'';else{while(m.empty()!=l){cout<<m.pop()<<'';}i++；}}else〃当前优先级等于栈优先级{cout<<m.pop()<<'';m.push(a[i]);i++；}}}}cout<<endl;}计算表达式结果voidFunction(chara[]){floats=0;inti=0;floatnum1=0;floatnum2=0;Intstackvchar>m;Intstackvfloat>n;inttmp=0;while(a[i]){if(a[i]>='0'&&a[i]v=9)//十位数整数以上的数据处理{s=s*10.0+(float(a[i])-48);i++;}else{if(a[i]=='.')//处理小数{floatj=1;i++;while(a[i]>='0'&&a[i]v=9){j=j*10；intt=(float)a[i]-48;s=s+t/j;i++；}}if(s!=O){n.push(s);//数据入栈s=0;}if(m.empty()=1)〃字符栈空时{m.push(a[i]);i++;}else{〃当前优先级大于栈优先级时if(prior(a[i])>prior(m.Gettop())){if(a[i]!=')') 〃处理后括号的情况{m.push(a[i]);i++;}else{while(m.Gettop()!='('){n.get(num1,num2);charc=m.pop();switch(c){case'*':n.push(num1*num2);break;case'/':n.push(num2/num1);break;case'+':n.push(num2+numl);break;case'-':n.push(num2-num1);break;}}m.pop();i++;}}〃当前栈优先级小于栈优先级时elseif(prior(a[i])vprior(m.Gettop())){if(a[i]!='#') 〃处理'#'的情况{if(m.Gettop()!='(')〃处理的'('情况{n.get(num1,num2);charc=m.pop();switch(c){case'*':n.push(num1*num2);break;case'/':n.push(num2/num1);break;case'+':n.push(num2+num1);break;case'-':n.push(num2-num1);break;}m.push(a[i]);i++;}else{m.push(a[i]);i++；}else{while(m.empty()!=l){n.get(num1,num2);charc=m.pop();switch(c){case'*':n.push(num1*num2);break;case'/':n.push(num2/num1);break;case'+':n.push(num2+num1);break;case'-':n.push(num2-num1);break;}}i++;}}〃当前优先级等于栈的优先级else{n.get(num1,num2);charc=m.pop();switch(c){case'*':n.push(num1*num2);break;case'/':n.push(num2/num1);break;case'+':n.push(num2+numl);break;case'-':n.push(num2-num1);break;}m.push(a[i]);i++;}}}}coutvvn.Gettop()vvendl;}主函数，实现函数的调用intmain(){cout<<setw(50)<<"欢迎使用本小型计算系统"vvendl;coutvvendl;while(l){coutvv"请选择操作：1.表达式计算 2.退出该系统"vvendl;charx;cin>>x;cin.ignore();switch(x){caseT:{coutvv"请请输入中缀表达式，以'#'号结束:"vvendl;chara[size];cin.getline(a,size,'\n');coutvvendl;if(judge(a)!=1){cout<<"变为后缀表达式为:"vvendl;order(a);coutvvendl;coutvv"表达式运算结果为:"vvendl;Function(a);coutvvendl;}elsecoutvvendl;}break;case2:return0;break;}}return0;}五：编码与调试分析编码过程中，遇到很多小问题。比如不能判断有些表达式是否正确，后来经过严谨的思考，终于能判断各种情况了。但后来又出现了一个问题,就是输入空格后就无法正常进行了，后来经过分析和查阅资料，明白了字符数组中，如果有空格就不能用cin>>来进行输入，经过了用cin.getline()这个函数解决了我的问题。经过了三个星期的努力，现在还没有发现问题，不过我会继续改进我的程序。六:使用说明运行的软件：本程序的运行环境为VC6.0。进入演示程序后即显示提示信息:简要说明程序运行操作步骤主菜单为1输入表达式2退出该运算若输入1.则继续输入一中缀表达式，程序将计算出结果；请输入一个中缀表达式：输入一中缀表达式进行判断，如果不正确，返回主菜单否则将转化为相应的后缀表达式，程序此后将显示转换后的后缀表达式，并输出运算结果。若输入2.退出系统，结束所有的运行七：测试结果判断整型:判断十位数以上的数:欢迎使用本小型计算系纟»青选择操作：「表达式计算 囂退岀该系统1请请输入中缀表达式，以^号结束:1+25*4#变为后缀表达式为=1254*+表达式运算结果为:101判断小数运算:欢迎使用本小型计算系统请选择操作：「表达式计算 器退岀该系统1.2+2.5*4#请请输入中缀表达式，以,护号结東：变为后缀表达式为：22.54*+表达式运算结果