数据结构实验三-栈的应用(算术表达式求值)

实验四栈的应用——算术表达式求值一、实验目的1.掌握栈和队列的两种存储结构；2.掌握栈和队列的实现；3.掌握栈和队列的应用。二、实验相关知识1.复习C语言文件读写的相关知识2.复习课本中第3章关于栈和队列的相关知识点；三、实验内容与要求1.编程实现对算术表达式的求值。【设计要求】输入包含+-*/四种运算，以及包含()括号的合法算术表达式，并计算其值，表达式以#开始，并以#结束。【测试用例】#(3)##3+4##3+4*2##(3+4)*2##(2*(3+4)-2)+(3-1)##(11+12)*16#【栈应用分析】以测试用例：#16*(11+12)#为例，分析栈操作的过程，详细见“算术表达式计算的栈操作过程.ppt”文件。四、程序代码及运行结果【程序代码】#includeiostreamusingnamespacestd;#defineTRUE1#defineFALSE0#defineStack_Size50/*int栈*/typedefstruct{intelem[Stack_Size];/*用来存放栈中元素的一维数组*/inttop;/*用来存放栈顶元素的下标，top为-1表示空栈*/}IntStack;/*char栈*/typedefstruct{charelem[Stack_Size];/*用来存放栈中元素的一维数组*/inttop;/*用来存放栈顶元素的下标，top为-1表示空栈*/}CharStack;/*初始化int栈*/voidInitStack(IntStack*&S){S=(IntStack*)malloc(sizeof(IntStack));S-top=-1;}/*初始化char栈*/voidInitStack(CharStack*&S){S=(CharStack*)malloc(sizeof(CharStack));S-top=-1;}/*判栈空*/intIsEmpty(IntStack*S)/*判断栈S为空栈时返回值为真，反之为假*/{return(S-top==-1?TRUE:FALSE);}/*判栈空*/intIsEmpty(CharStack*S)/*判断栈S为空栈时返回值为真，反之为假*/{return(S-top==-1?TRUE:FALSE);}/*判栈满*/intIsFull(IntStack*S)/*判断栈S为满栈时返回值为真，反之为假*/{return(S-top==Stack_Size-1?TRUE:FALSE);}/*判栈满*/intIsFull(CharStack*S)/*判断栈S为满栈时返回值为真，反之为假*/{return(S-top==Stack_Size-1?TRUE:FALSE);}/*进栈*/intPush(CharStack*&S,charx){if(S-top==Stack_Size-1)return(FALSE);/*栈已满*/S-top++;S-elem[S-top]=x;return(TRUE);}/*进栈*/intPush(IntStack*&S,intx){if(S-top==Stack_Size-1)return(FALSE);/*栈已满*/S-top++;S-elem[S-top]=x;return(TRUE);}/*出栈*/intPop(IntStack*&S,int&x){/*将栈S的栈顶元素弹出，放到x所指的存储空间中*/if(S-top==-1)/*栈为空*/return(FALSE);else{x=S-elem[S-top];S-top--;/*修改栈顶指针*/return(TRUE);}}/*出栈*/intPop(CharStack*S,char&x){/*将栈S的栈顶元素弹出，放到x所指的存储空间中*/if(S-top==-1)/*栈为空*/return(FALSE);else{x=S-elem[S-top];S-top--;/*修改栈顶指针*/return(TRUE);}}/*取栈顶元素。*/intGetTop(IntStack*S,int&x){/*将栈S的栈顶元素弹出，放到x所指的存储空间中，但栈顶指针保持不变*/if(S-top==-1)/*栈为空*/return(FALSE);else{x=S-elem[S-top];return(TRUE);}}/*取栈顶元素。*/intGetTop(CharStack*S,char&x){/*将栈S的栈顶元素弹出，放到x所指的存储空间中，但栈顶指针保持不变*/if(S-top==-1)/*栈为空*/return(FALSE);else{x=S-elem[S-top];return(TRUE);}}voidtrans(char*exp,charpostexp[]){chare;CharStack*Optr;InitStack(Optr);inti=0;while(*exp!='\0'){switch(*exp){case'(':Push(Optr,'(');exp++;break;case')':Pop(Optr,e);while(e!='('){postexp[i++]=e;Pop(Optr,e);}exp++;break;case'+':case'-':while(!IsEmpty(Optr)){GetTop(Optr,e);if(e!='('){postexp[i++]=e;Pop(Optr,e);}elsebreak;}Push(Optr,*exp);exp++;break;case'*':case'/':while(!IsEmpty(Optr)){GetTop(Optr,e);if(e=='*'||e=='/'){postexp[i++]=e;Pop(Optr,e);}elsebreak;}Push(Optr,*exp);exp++;break;default:while(*exp='0'&&*exp='9'){postexp[i++]=*exp;exp++;}postexp[i++]='#';}}while(!IsEmpty(Optr)){Pop(Optr,e);postexp[i++]=e;}postexp[i]='\0';/*DestroyStack(Optr);*/}doublecompvalue(char*postexp){intd=0,a=0,b=0,c=0,e=0;IntStack*Opnd;//定义操作数栈InitStack(Opnd);//初始化操作数栈while(*postexp!='\0')//postexp字符串未扫描完时循环{switch(*postexp){case'+'://判定为'+'号Pop(Opnd,a);//出栈元素aPop(Opnd,b);//出栈元素bc=b+a;//计算cPush(Opnd,c);//将计算结果c进栈break;case'-'://判定为'-'号Pop(Opnd,a);//出栈元素aPop(Opnd,b);//出栈元素bc=b-a;//计算cPush(Opnd,c);//将计算结果c进栈break;case'*'://判定为'*'号Pop(Opnd,a);//出栈元素aPop(Opnd,b);//出栈元素bc=b*a;//计算cPush(Opnd,c);//将计算结果c进栈break;case'/'://判定为'/'号Pop(Opnd,a);//出栈元素aPop(Opnd,b);//出栈元素bif(a!=0){c=b/a;//计算cPush(Opnd,c);//将计算结果c进栈break;}else{printf(\n\t除零错误!\n);exit(0);//异常退出}break;default://处理数字字符d=0;//转换成对应的数值存放到d中while(*postexp='0'&&*postexp='9'){d=10*d+*postexp-'0';postexp++;}Push(Opnd,d);//将数值d进栈break;}postexp++;//继续处理其他字符}GetTop(Opnd,e);//取栈顶元素ereturne;//返回e}intmain(intheng,char*heng1[]){charexp[Stack_Size];inti=0;gets_s(exp);charpostexp[Stack_Size];trans(exp,postexp);printf(中缀表达式:%s\n,exp);printf(后缀表达式:%s\n,postexp);printf(表达式的值:%g\n,compvalue(postexp));return0;}【运行结果】【算法描述】（1）将算术表达式转换成后缀表达式exp=postexp扫描exp的所有字符：数字字符直接放在postexp中运算符通过一个栈来处理优先级情况1（没有括号）先进栈的先退栈即先执行：只有大于栈顶优先级才能直接进栈exp扫描完毕，所有运算符退栈情况2（带有括号）开始时，任何运算符都进栈(：一个子表达式开始，进栈栈顶为(：任何运算符进栈)：退栈到（只有大于栈顶的优先级，才进栈；否则退栈（2）后缀表达式求值postexp=值扫描postexp的所有字符：数字字符：转换为数值并进栈运算符：退栈两个操作数，计算，将结果进栈五、实验心得体会通过这次试验，我对栈有了新的理解和认识。