利用栈进行表达式求值

#includeStdafx.h#includestdio.h#includemalloc.h#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10typedefstruct{int*base;int*top;intstacksize;}SqStack;//初始化一个栈voidinitStack(SqStack&myStack){myStack.base=(int*)malloc(STACK_INIT_SIZE*sizeof(int));myStack.top=myStack.base;myStack.stacksize=STACK_INIT_SIZE;printf(系统为您分配了%d个Int大小的空间……\n,STACK_INIT_SIZE);}//进行出栈操作，返回的值放在e中voidpop(SqStack&myStack,int&e){if(myStack.top==myStack.base){e=NULL;}else{e=*--myStack.top;printf(%d进行了出栈操作……\n,e);}}//取出栈顶元素的值，但栈内的值不变chargetTop(SqStackmyStack){chare;if(myStack.top==myStack.base){e=NULL;}else{e=*(myStack.top-1);//top指针并未往下移动}returne;}//将新的元素e插入到栈顶voidpush(SqStack&myStack,inte){if((myStack.top-myStack.base)=myStack.stacksize){//判断是否栈满，若满，重新分配更大的栈myStack.base=(int*)realloc(myStack.base,(myStack.stacksize+STACKINCREMENT)*sizeof(int));myStack.top=myStack.base+myStack.stacksize;myStack.stacksize+=STACKINCREMENT;}*myStack.top++=e;printf(%d进行了入栈操作……\n,e);}//返回c1和c2操作符之间的等级关系，有'''''='charprecede(charc1,charc2){switch(c1){case'+':case'-':switch(c2){case'+':case'-':case')':case'#':return'';break;default:return'';}break;case'*':case'/':switch(c2){case'(':return'';break;default:return'';}break;case'(':switch(c2){case')':return'=';break;case'#':returnNULL;break;default:return'';}break;case')':switch(c2){case'(':returnNULL;break;default:return'';}break;case'#':switch(c2){case')':returnNULL;break;case'#':return'=';break;default:return'';}}returnNULL;}//对a和b之间进行数值计算intoperate(inta,chartheta,intb){intres;switch(theta){case'+':res=a+b;break;case'-':res=a-b;break;case'*':res=a*b;break;default:res=a/b;}returnres;}//判断是不是数字boolisNum(charc){return(c='9'&&c='0')?true:false;}//计算表达式intevaluateExpression(){charc;intt,a,b,theta;SqStackoprt,opnd;//栈oprt用来存放运算符，栈opnd用来存放操作数或运算结果initStack(oprt);//初始化oprtinitStack(opnd);//初始化opndpush(oprt,'#');//char类型的数组放到int中printf(\n请输入一个表达式，该表达式必须满足的条件是:\n);printf((1)、以\#\结束\n);printf((2)、每个数字必须是个位数\n);printf((3)、如果有除法运算，其值必须是整数\n);c=getchar();while(c!='#'||getTop(oprt)!='#'){if(isNum(c)){push(opnd,((int)c-48));c=getchar();}else{switch(precede((char)getTop(oprt),c)){case'':push(oprt,c);c=getchar();break;case'=':pop(oprt,t);c=getchar();break;case'':pop(oprt,theta);pop(opnd,b);pop(opnd,a);push(opnd,operate(a,theta,b));break;}}}returngetTop(opnd);}voidmain(){intresult=evaluateExpression();printf(最终结果是：%d\n,result);}