数据结构实验-栈和队列

实验3：栈和队列一、实验目的深入了解栈和队列的特性，学会在实际问题下灵活运用它们。二、问题描述表达式求值运算是实现程序设计语言的基本问题之一，也是栈应用的一个典型例子。设计并演示用算符优先级对算术表达式的求解过程。三、实验要求1、算法优先级别如下：'+','-','*','/','(',')','#''+''','','','','','','','-''','','','','','','','*''','','','','','','','/''','','','','','','','(''','','','','','=','',')''','','','','','','','#''','','','','','','='2、以字符序列的形式从终端输入语法正确、不含变量的算术表达式，利用给出的算符优先级关系，实现对算术四则混合运算的求解过程。四、实验环境PC微机DOS操作系统或Windows操作系统TurboC程序集成环境或VisualC++程序集成环境五、实验步骤1、根据给出的算符优先级，设置运算符栈和运算数栈；2、在读入表达式的同时，完成运算符和运算数的识别处理，并将运算数的字符序列形式转换成整数形式，并进行相应的运算；3、调试程序，检查输出结果；4、实验小结。六、测试数据1.输入数据：1+（20+4）/（4-1）正确结果：92.输入数据：2*9-6-（20+4）/（4-1）正确结果：4七、实验报告要求实验报告应包括以下几个部分：1、问题描述；2、算法的设计描述；3、测试结果的分析与讨论。4、设计与实现过程中的体会，进一步的改进设想。实现算法的程序清单，应有足够的注释。实验代码如下：#includeiostream#includecmath#includecstdlibusingnamespacestd;#defineMAX1000structsave1{floatn[MAX];inttop;}stack1;structsave2{charn[MAX];inttop;}stack2;//stack1存储数字，stack2存储运算符号.boolstackempty(save1s)//判断是否为空{if(s.top==-1)return1;elsereturn0;}boolstackempty2(save2s)//判断是否为空{if(s.top==-1)return1;elsereturn0;}voidpush(save1&s,floate)//将e入栈{if(s.top==MAX-1){cout栈已满endl;return;}s.top++;s.n[s.top]=e;}voidpush2(save2&s,chare)//将e入栈{if(s.top==MAX-1){cout栈已满endl;return;}s.top++;s.n[s.top]=e;}voidpop(save1&s,float&e)//将栈顶元素出栈，存到e中{if(s.top==-1){cout栈为空endl;}else{e=s.n[s.top];s.top--;}}voidpop2(save2&s,char&e)//将栈顶元素出栈，存到e中{if(s.top==-1){cout栈为空endl;}else{e=s.n[s.top];s.top--;}}intin(chare)//e在栈内的优先级别{if(e=='-'||e=='+')return2;if(e=='*'||e=='/')return4;if(e=='^')return5;if(e=='(')return0;if(e==')')return7;return-1;}intout(chare)//e在栈外的优先级别{if(e=='-'||e=='+')return1;if(e=='*'||e=='/')return3;if(e=='^')return6;if(e=='(')return7;if(e==')')return0;return-1;}voidcount(floata,charope,floatb)//进行计算并将计算结果入栈{floatsum;if(ope=='+')sum=a+b;if(ope=='-')sum=a-b;if(ope=='*')sum=a*b;if(ope=='/')sum=a/b;if(ope=='^')sum=pow(a,b);push(stack1,sum);}intmain(){inti=0,len,j,nofpoint,g=0;//len表示输入式子的长度。g表示读入的字符是否是字母变量、数字以及运算符。floata,b;//a、b用来存储操作数栈中弹出的操作数，便于代入函数中进行计算。charline[MAX],operate,temp[20];cout请输入表达式:endl;cinline;len=strlen(line);stack1.top=-1;//将栈置为空stack2.top=-1;//将栈置为空while(1){g=0;if(isdigit(line[i]))//若读入的字符为数字，则继续判断下一个字符，直到下一个字符不是数字或者不是小数点，即可保证该操作数是完整的小数，然后将该数入操作数栈。{j=0;g=1;nofpoint=0;//记录所存的数中小数点的个数while(isdigit(line[i])||line[i]=='.'){if(line[i]=='.')nofpoint++;temp[j++]=line[i];i++;if(i=len)break;}if(nofpoint1||(ilen&&(line[i]!='-'&&line[i]!='+'&&line[i]!='*'&&line[i]!='/'&&line[i]!='^'&&line[i]!=')'))){cout表达式有错endl;return0;}//所存数中含有不止一个小数点，或者数字后面跟的不是“+、-、*、/、^、)”，则为错误temp[j]='\0';b=atof(temp);push(stack1,b);if(i=len)break;}else{if(line[i]=='-'||line[i]=='+'||line[i]=='*'||line[i]=='/'||line[i]=='^'||line[i]=='('||line[i]==')')//若读入的字符为运算符的情况{g=1;if(line[i]=='('&&i==len){cout表达式有错endl;return0;}//“(”放表达式最后面，错误if(line[i]=='-'||line[i]=='+'||line[i]=='*'||line[i]=='/'||line[i]=='^'){if(i==len){cout表达式有错endl;return0;}//“+、-、*、/、^”放在表达式最后面，错误if((!isdigit(line[i+1]))&&(!isalpha(line[i+1]))&&line[i+1]!='(')//“+、-、*、/、^”后面跟的不是数字或者变量，错误{cout表达式有错endl;return0;}}if(line[i]=='-'&&(i==0||line[i-1]=='('))//运算符是负号{push(stack1,0);push2(stack2,line[i]);i++;}else{//读入的运算符与运算符栈的栈顶元素相比，并进行相应的操作if(in(stack2.n[stack2.top])out(line[i])||stackempty2(stack2)){push2(stack2,line[i]);i++;}elseif(in(stack2.n[stack2.top])==out(line[i])){i++;stack2.top--;}elseif(in(stack2.n[stack2.top])out(line[i])){pop(stack1,a);pop(stack1,b);pop2(stack2,operate);count(b,operate,a);}if(i=len)break;}}else{if(isalpha(line[i]))//读入的字符是字母变量的情况{g=1;cout请输入变量;while(isalpha(line[i])){coutline[i];i++;}cout的值endl;cinb;push(stack1,b);if(i=len)break;if(line[i]!='-'&&line[i]!='+'&&line[i]!='*'&&line[i]!='/'&&line[i]!='^'&&line[i]!=')')//变量后面跟的不是“+、-、*、/、^、)”，则为错误{cout表达式有错endl;return0;}}}}if(g==0){cout表达式有错endl;return0;}//g=0表示该字符是不符合要求的字符}while(stack2.top!=-1)//读入结束后，继续进行操作，直到运算符栈为空{pop(stack1,a);pop(stack1,b);pop2(stack2,operate);if(operate=='('||operate==')')//括号多余的情况{cout表达式有错endl;return0;}count(b,operate,a);}coutstack1.n[stack1.top]endl;return0;}整型数运行结果如下：浮点数运行结果如下：八、思考题1、如何实现前缀算术表达式、后缀表达式的求解？答：用栈来实现表达式的中缀表示法变后缀要用一个字符型数组OPTR作为栈，存放括号和运算符。设字符“#”为表达式的终止符，方法如下：先将一个左括号“（”压入栈OPTR，作为栈底元素，输入时以“#”作为输入的结束标志。依次读入表达式中的字符，对于每一个字符有三种情况：第一种情况是——数字；处理方式：将字符直接赋值到后缀表达式串中。第二种情况是——非数字非运算符；处理方式：结束。第三种情况是——运算符；处理情况按运算符与栈顶运算符的三种优先关系；①大于栈顶优先级：将字符直接赋值到后缀表达式串中。②等于栈顶优先级：将栈顶元素退栈，处理表达式中下一个字符。③小于栈顶优先级：将栈顶元素退栈，并将推出栈的元素输出到后缀表示式串中inttransExpression(char*str1,char*str2){/*将中缀表达式串str1，转换为后缀表达式str2*/IniStack(OPTR);Push(OPTR,′#′)；i=0;k=0;while(str1[i]!=′#′||GetTop(OPTR)!=′#′){if(str1[i]=′0′&&c=′9′)str2[k++]=str1[i++]；/*数复制到str2中*/else{ifjudge(str1[i])returnERROR;/*判断是否操作符，若不是结束*/switch(Precede(GetTop(OPTR),str[i])/*比较操作符优先级高低*/{case′′：/*栈顶优先级时str1[i]低直接复制到str2[k]中*/str2[k++]=str1[i++]；break；case′=′：/*优先级相等脱括号并处理下一个字符*/Pop(OPTR,x)；i++；break；case′′：/*栈顶优先级高，将栈顶复制到str2中*/Pop(OPTR,theta)；str2[k++]=theta;break；}}}returnOK；/*正确返回*/}