数据结构课程设计带括号的算术表达式求值

、实验的目的和要求1.采用算符优先数算法,能正确求值表达式;2.熟练掌握栈的应用;3•熟练掌握计算机系统的基本操作方法，了解如何编辑、编译、链接和运行一个C++程序;4.上机调试程序,掌握查错、排错使程序能正确运行。三、实验的环境:指硬件和软件环境1.硬件环境:Intel奔腾双核T2390双核处理器(1.86GHz主频/1MB二级缓存/533MHz前端总线)，RAM:2G.2.软件环境:操作系统：windowsvista编译软件：MicrosoftViualC++6.03.软件环境介绍:VisualC++是一个功能强大的可视化软件开发工具。自1993年Microsoft公司推出VisualC++1.0后，随着其新版本的不断问世，VisualC++已成为专业程序员进行软件开发的首选工具。虽然微软公司推出了VisualC++.NET(VisualC++7.0)，但它的应用的很大的局限性，只适用于Windows2000,WindowsXP和WindowsNT4.0。所以实际中，更多的是以VisualC++6.0为平台。VisualC++6.0不仅是一个C++编译器，而且是一个基于Windows操作系统的可视化集成开发环境(integrateddevelopmentenvironment,IDE)。VisualC++6.0由许多组件组成，包括编辑器、调试器以及程序向导AppWizard、类向导ClassWizard等开发工具。这些组件通过一个名为DeveloperStudio的组件集成为和谐的开发环境。四、算法描述:1.头文件:Stack.hCalculator.hMethod:Stackmethod:Push();//进栈操作Pop();//出栈操作GetHead();//返回栈中的最顶层元素MakeEmpty();//清空栈操作Calculatormethod:Calculator();//计算主体celarstream();//清空输入流Prior();//返回运算符的优先级done();//做一次二元运算output();//打印结果并输出EnEmpty();//调用MakeEmpty(),并清空栈2.cpp文件Calculator.cppMethod:intmain();//主程序3.程序流程图优先级比较算法Data算法存放操作字符存放数据调用Calculator。4.功能描述(1)所有函数都是在calculator。函数为主体，调用其他函数开始的。Calculator函数让输入的中缀表达式按字符读取。(2)如果读取为操作数，则将字符返回输入流(cin.putback)，读操作数并进data栈，然后读入下一字符送入ch。(3)如果读取为操作符，则判断操作符类型，确定优先级。不同的优先数的操作符进行不同的运算。⑷用output函数进行结果等的输出。⑸Enempty为清空两个栈。(6)主函数调用时，创建calculator实例，调用calculator函数进行计算，然后调用output函数进行输出，最后调用enempty清空栈。结束注：程序有两个栈，分别为data和sign。分别存放操作数和操作符；此程序要求输入的是中缀表达式，即直接对中缀表达式求值,不用转化为后缀在求值。五、源程序清单:Stack.h#includeiostream.h#includestring.h#includestdio.h#includestdlib.h#includeassert.h#defineERROR-1#defineBLANK0#defineDATA1#defineKUOHAO15#defineKUOHAO22#defineADD_OR_SUB3#defineMUT_OR_DIV4constintsize=500;templateclassElemclassStack;templateclassElemclassStackNode//堆栈的结点类{friendclassStackElem;Elemelem;StackNodeElem*link;StackNode(Eleme=0,StackNodeElem*l=NULL):elem(e),link(l){//coutelemis:eendl;}};templateclassElemclassStack;templateclassElemclassStack{intnumber;StackNodeElem*head;public:Stack():number(0),head(NULL){}~Stack(){StackNodeElem*tmp=head;while(head!=NULL){head=head-link;deletetmp;tmp=head;}}voidPush(constElem&e){number++;head=newStackNodeElem(e,head);}voidMakeEmpty(){StackNodeElem*tmp=head;while(head!=NULL){head=head-link;deletetmp;tmp=head;}number=0;}voidPop()assert(number!=0);number--;StackNodeElem*tmp=head;head=head-link;deletetmp;}ElemGetHead(){returnhead-elem;}intGetNumber()const{returnnumber;}//返回堆栈中元素的数目};Calculator.hclassCalculator{private:Stackdoubledata;//数据栈Stackcharsign;//运算符栈intflag;//标志位表示前一个输入的是数还是一个运算符public:Calculator(){flag=BLANK;}~Calculator(){}intPrior(charch)const//返回运算符的优先级{switch(ch){case')':return1;case'+':case'-':return2;case'*':case'/':return3;case'(':return5;default:return-1;}}voidclearstream()//清空输入流{charch;while(cinch,ch!=';');}voiddone(charch)//做一次二元运算{doublea,b;a=data.GetHead();data.Pop();b=data.GetHead();data.Pop();switch(ch){case'+':b+=a;break;case'-':b-=a;break;case'*':b*=a;break;case'/':if(a==0){cout除数为零!返回系统默认值如下endl;}b/=a;break;default:break;}data.Push(b);}voidCalculate(){charch;doubled;while(cinch,ch!='='){if(ch='0'&&ch='9'||ch=='.'){if(flag==DATA){cout\nErrorinput!小数点只能有一位!endl;flag=ERROR;clearstream();return;}cin.putback(ch);cind;data.Push(d);flag=DATA;}else//如果输入的是字符，则作出判断{intprio=Prior(ch);chartempch,chprior;switch(prio){case-1:cout\nErrorinput!不允许的字符endl;flag=ERROR;clearstream();return;case1://如果是一个后括号，tempch=sign.GetHead();//是合法的运算，取一个运算符flag=KUOHAO2;while(tempch!='(')//做完这一重括号内的所有运算{sign.Pop();done(tempch);if(sign.GetNumber()!=0){tempch=sign.GetHead();}}sign.Pop();break;case2://如果读入的是一个+或者-号，//如果+前面没有数据，或者+是被写在括号里的，则向//它的前面压入一个0到dataif(flag==BLANK||data.GetNumber()==0||flag==KUOHAO1){data.Push(0);//push0tostack//sign.Push(ch);//push+/-tostack}//如果它前面是一个后括号，因后括号里的内容已经做过//运算，故只当一个一般的来做if(flag==KUOHAO2||flag==DATA){while(sign.GetNumber()&&sign.GetHead()!='('&&Prior(sign.GetHead())=Prior(ch))done(sign.GetHead());sign.Pop();}flag=ADD_OR_SUB;sign.Push(ch);break;case3://如果当前输入是一个*或者/号//如果前一个输入是一个*或者/号//如果它前面不只一个数字，则做它前面的运算if(data.GetNumber()!=1){chprior=Prior(sign.GetHead());if(chprior=Prior(ch)&&sign.GetHead()!='('){chprior=sign.GetHead();sign.Pop();done(chprior);}}sign.Push(ch);flag=MUT_OR_DIV;break;case5://如果当前的是一个前括号//如果它前面输入的是一个数据，则提示出错if(flag==DATA){cout\n输入错误!数据后不能直接跟括号flag=ERROR;clearstream();return;}sign.Push(ch);flag=KUOHAO1;break;default:cout\n输入错误!非法字符!chendl;flag=ERROR;clearstream();break;}}}if(sign.GetNumber()&&sign.GetHead()=='('){cout\n括号不配对!endl;//前括号没有找到后括号flag=ERROR;return;}if(flag==MUT_OR_DIV||flag==ADD_OR_SUB){cout\n表达式没有写完!endl;flag=ERROR;return;}while(sign.GetNumber()){if(sign.GetHead()=='('){cout\n括号不配对！endl;flag=ERROR;return;}!endl;done(sign.GetHead());sign.Pop();}}voidOutPut(){cout\nTheansweris:data.GetHead()endl;data.Pop();}voidEnEmpty(){data.MakeEmpty();sign.MakeEmpty();flag=BLANK;}};Calculator.cpp#includeStackNode.h#includeCalculator.hintmain(){chariscontinue='Y';Calculatorcal;while(iscontinue=='Y')endl;cout请输入你要计算的中缀表达式,以等号结束cal.Calculate();cal.OutPut();cal.EnEmpty();cout是否继续(Y/N)?;