数据结构C语言版-栈实现表达式求值

/*数据结构C语言版栈实现表达式求值P52-54编译环境：Dev-C++4.9.9.2日期：2011年2月10日*/typedefintSElemType;//栈的元素类型#defineSTACK_INIT_SIZE10//存储空间初始分配量#defineSTACKINCREMENT2//存储空间分配增量//栈的顺序存储表示P46typedefstructSqStack{SElemType*base;//在栈构造之前和销毁之后，base的值为NULLSElemType*top;//栈顶指针intstacksize;//当前已分配的存储空间，以元素为单位}SqStack;//顺序栈//构造一个空栈S。intInitStack(SqStack*S){//为栈底分配一个指定大小的存储空间(*S).base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));if(!(*S).base)exit(0);//存储分配失败(*S).top=(*S).base;//栈底与栈顶相同表示一个空栈(*S).stacksize=STACK_INIT_SIZE;return1;}//若栈不空，则用e返回S的栈顶元素，并返回1；否则返回0。intGetTop(SqStackS,SElemType*e){if(S.top>S.base){*e=*(S.top-1);//栈顶指针的下一个位置为栈顶元素return1;}elsereturn0;}//插入元素e为新的栈顶元素。intPush(SqStack*S,SElemTypee){if((*S).top-(*S).base>=(*S).stacksize)//栈满，追加存储空间{(*S).base=(SElemType*)realloc((*S).base,((*S).stacksize+STACKINCREMENT)*sizeof(SElemType));if(!(*S).base)exit(0);//存储分配失败(*S).top=(*S).base+(*S).stacksize;(*S).stacksize+=STACKINCREMENT;}*((*S).top)++=e;//这个等式的++*优先级相同，但是它们的运算方式，是自右向左return1;}//若栈不空，则删除S的栈顶元素，用e返回其值，并返回1；否则返回0。intPop(SqStack*S,SElemType*e){if((*S).top==(*S).base)return0;*e=*--(*S).top;//这个等式的++*优先级相同，但是它们的运算方式，是自右向左return1;}//根据教科书表3.1，判断两符号的优先关系SElemTypePrecede(SElemTypet1,SElemTypet2){SElemTypef;switch(t2){case'+':case'-':if(t1=='('||t1=='#')f='<';elsef='>';break;case'*':case'/':if(t1=='*'||t1=='/'||t1==')')f='>';elsef='<';break;case'(':if(t1==')'){printf("ERROR1\n");exit(0);}elsef='<';break;case')':switch(t1){case'(':f='=';break;case'#':printf("ERROR2\n");exit(0);default:f='>';}break;case'#':switch(t1){case'#':f='=';break;case'(':printf("ERROR3\n");exit(0);default:f='>';}}returnf;}//判断c是否为运算符intIn(SElemTypec){switch(c){case'+':case'-':case'*':case'/':case'(':case')':case'#':return1;default:return0;}}SElemTypeOperate(SElemTypea,SElemTypetheta,SElemTypeb){SElemTypec;a=a-48;//ASCII值转化为对应的十进制值b=b-48;//ASCII值转化为对应的十进制值switch(theta){case'+':c=a+b+48;break;case'-':c=a-b+48;break;case'*':c=a*b+48;break;case'/':c=a/b+48;}returnc;}//算法3.4P54//算术表达式求值的算符优先算法。设OPTR和OPND分别为运算符栈和运算数栈SElemTypeEvaluateExpression(){SqStackOPTR,OPND;SElemTypea,b,c,x,theta;InitStack(&OPTR);Push(&OPTR,'#');InitStack(&OPND);c=getchar();GetTop(OPTR,&x);while(c!='#'||x!='#'){if(In(c))//是7种运算符之一switch(Precede(x,c)){case'<':Push(&OPTR,c);//栈顶元素优先权低c=getchar();break;case'=':Pop(&OPTR,&x);//脱括号并接收下一字符c=getchar();break;case'>':Pop(&OPTR,&theta);//退栈并将运算结果入栈Pop(&OPND,&b);Pop(&OPND,&a);Push(&OPND,Operate(a,theta,b));break;}elseif(c>='0'&&c<='9')//c是操作数{Push(&OPND,c);c=getchar();}else//c是非法字符{printf("非法字符\n");exit(0);}GetTop(OPTR,&x);}GetTop(OPND,&x);returnx;}intmain(){printf("请输入算术表达式（中间值及最终结果要在0～9之间），""并以#结束\n");printf("例如：3*(7-5)#\n");printf("%c\n",EvaluateExpression());system("pause");return0;}/*输出效果：请输入算术表达式（中间值及最终结果要在0～9之间），并以#结束例如：3*(7-5)#3*(7-5)#6请按任意键继续...请输入算术表达式（中间值及最终结果要在0～9之间），并以#结束例如：3*(7-5)#4+2*3-10/5#8请按任意键继续...*/