基于栈结构的中缀表达式求值

实验三基于栈结构的中缀表达式求值班级：计科131、问题描述从键盘输入一中缀表达式字符串，读字符串，利用栈结构实现表达式求值。2、输入与输出输入：从键盘中缀表达式如：32＋5×（6－4）输出：计算结果423、需求分析1.定义两个栈结构，数栈用于存放表达式中的数，符号栈用于存放表达式中的符号，实现栈的运算2.在读数的时候考虑多位运算3.实现表达式求值4、开发工具与环境硬件设备：微型计算机系统软件环境：操作系统Windows，开发工具VC6.0等等5、概要设计1.结构定义typedefstruct/*运算符栈*/{char*base,*top;intstacksize;}SqStack;typedefstruct/*运算数栈*/{int*base,*top;intstacksize;}SqStack1;intpriority[7][7]={{'','','','','','',''},//+{'','','','','','',''},//-{'','','','','','',''},//*{'','','','','','',''},///{'','','','','','=',},//({'','','','','','',''},//){'','','','','','','='}//#};/*用于比较符号优先级的全局二维数组*/2．各函数模块voidInitStack(SqStack*s);操作结果：初始化运算符栈。voidInitStack1(SqStack*s);操作结果：初始化运算数栈。voidInitStack1(SqStack*s);操作结果：初始化运算符栈。charGetTop(SqStacks)操作结果：若栈不空，则返回运算符栈栈顶元素，否则返回ERROR。intGetTop1(SqStack1s)操作结果：若栈不空，则用，否则返回ERROR。voidPushS(SqStack&s,chare)操作结果：插入元素e为新的运算符的栈顶。voidPushS1(SqStack1&s,inte)操作结果：插入元素e为新的运算数栈顶。intpop(SqStack&s,char&e)操作结果：若运算符栈不空，则删除s的栈顶元素，用e返回其值，并返回OK,否则返回ERROR。intpop1(SqStack1&s,int&e)操作结果：若运算数栈不空，则删除s的栈顶元素，用e返回其值，并返回OK,否则返回ERROR。6、程序清单#includeiostreamusingnamespacestd;#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10#defineERROR0#defineOK1typedefstruct/*运算符栈*/{char*base,*top;intstacksize;}SqStack;typedefstruct/*运算数栈*/{int*base,*top;intstacksize;}SqStack1;intpriority[7][7]={{'','','','','','',''},//+0{'','','','','','',''},//-1{'','','','','','',''},//*2{'','','','','','',''},///3{'','','','','','=',},//(4{'','','','','','',''},//)5{'','','','','','','='}//#6};/*用于比较符号优先级的全局二维数组*/voidInitStack(SqStack&s)//初始化运算符栈{s.base=(char*)malloc(STACK_INIT_SIZE*sizeof(char));if(!s.base)exit(OVERFLOW);s.top=s.base;s.stacksize=STACK_INIT_SIZE;}voidInitStack1(SqStack1&s)//初始化运算数栈{s.base=(int*)malloc(STACK_INIT_SIZE*sizeof(int));if(!s.base)exit(OVERFLOW);s.top=s.base;s.stacksize=STACK_INIT_SIZE;}voidPushS(SqStack&s,chare)//插入元素e为新的运算符栈的栈顶{if(s.top-s.base=s.stacksize){s.base=(char*)realloc(s.base,(s.stacksize+STACKINCREMENT)*sizeof(char));if(!s.base)exit(OVERFLOW);s.top=s.base+s.stacksize;//指向栈顶s.stacksize+=STACKINCREMENT;}*s.top++=e;}voidPushS1(SqStack1&s,inte)//插入元素e为新的运算数的栈顶{if(s.top-s.base=s.stacksize){s.base=(int*)realloc(s.base,(s.stacksize+STACKINCREMENT)*sizeof(int));if(!s.base)exit(OVERFLOW);s.top=s.base+s.stacksize;//指向栈顶s.stacksize+=STACKINCREMENT;}*s.top++=e;}//PushcharGetTop(SqStacks)//若栈不空，则返回s的栈顶元素，否则返回ERROR{if(s.top==s.base)returnERROR;return*(s.top-1);}intGetTop1(SqStack1s)//若栈不空，则用e返回s的栈顶元素，否则返回ERROR{if(s.top==s.base)returnERROR;return*(s.top-1);}intpop(SqStack&s,char&e)//若栈不空，则删除s的栈顶元素，用e返回其值{if(s.top==s.base)returnERROR;e=*--s.top;returnOK;}intpop1(SqStack1&s,int&e)//若栈不空，则删除s的栈顶元素，用e返回其值{if(s.top==s.base)returnERROR;e=*--s.top;returnOK;}intnumber(chara)//将运算符的位置转化为数字以便于在二维数组中找到优先级{switch(a){case'+':return0;break;case'-':return1;break;case'*':return2;break;case'/':return3;break;case'(':return4;break;case')':return5;break;case'#':return6;break;default:returnERROR;}}charprecede(chara,charb){inti,j;i=number(a);j=number(b);returnpriority[i][j];}intOperate(inta,charc,intb)//计算表达式结果并返回其值{switch(c){case'+':returna+b;case'-':returna-b;case'*':returna*b;case'/':returna/b;default:returnERROR;}}intinput(SqStack&s,SqStack1&s1)//完成表达式的输入与计算{charc1,c2;chartemp;inte,a,b;c1=getchar();while(c1!='#'||GetTop(s)!='#'){if(c1='0'&&c1='9'){c2=getchar();if(c2!='#'&&c2='0'&&c2='9')//c2为数字{e=((int)c1-48)*10+(int)c2-48;PushS1(s1,e);}//内层ifelse//c1为运算数，c2为运算符else1{PushS1(s1,(int)c1-48);//将运算数入栈again:if(c2!='#'||GetTop(s)!='#'){switch(precede(GetTop(s),c2)){case''://栈顶元素优先权低PushS(s,c2);//c1=getchar();break;case'='://脱括号并接收下一个字符pop(s,c2);//c1=getchar();break;case''://退栈并将运算结果入栈pop(s,temp);pop1(s1,b);pop1(s1,a);PushS1(s1,Operate(a,temp,b));gotoagain;}//switch}//ifelsegotoexit;//计算完成晚会结果}//内层else}//ifelse{aga:if(c1!='#'||GetTop(s)!='#'){switch(precede(GetTop(s),c1)){case''://栈顶元素优先权低PushS(s,c1);//c1=getchar();break;case'='://脱括号并接收下一个字符pop(s,c1);//c1=getchar();break;case''://退栈并将运算结果入栈pop(s,temp);pop1(s1,b);pop1(s1,a);PushS1(s1,Operate(a,temp,b));gotoaga;}//switch}//ifelsegotoexit;//计算结束返回结果}c1=getchar();}//whileexit:returnGetTop1(s1);}voidmain(){SqStackoptr;//运算符栈SqStack1opnd;//运算数栈intresult;//结果InitStack(optr);//初始化运算符栈PushS(optr,'#');//‘#’为栈底元素，标志结束InitStack1(opnd);//初始化运算数栈cout请输入表达式,'#'表示结束endl;result=input(optr,opnd);//输入表达式计算结果。cout表达式的结果为resultendl;}7、程序结果