简单表达式的处理与实现.doc

_/*简单个位数算术表达式转换成后缀表达式程序， 并计算出结果。*/#include#define StackSize 100#define QueueSize 100/*队列的相关操作*/struct Queue char data100; int front,rear; POstQ;/*定义队列，存放后缀表达式*/void InitQueue(struct Queue *Q)/*初始化队列*/ Q-front=0; Q-rear=0; int QueueEmpty(struct Queue *Q)/*队列判空*/ if (Q-rear=Q-front) return 1; else return 0; void EnQueue(struct Queue *Q, char x)/*入队*/ if(Q-rear+1)%QueueSize=Q-front) printf(队溢出！); else Q-dataQ-rear=x; Q-rear=(Q-rear+1)%QueueSize; /*字符栈的相关操作*/struct Stack char data100; int top; Os;/*定义栈，存放运算符*/void InitStack(struct Stack *s)/*初始化栈*/ s-top=0; void Push(struct Stack *s, char x)/*入栈（进栈）*/ if(s-top=StackSize) printf(stack overflow); else s-datas-top=x; s-top=s-top+1; char Pop(struct Stack *s)/*退栈（出栈）*/ if(s-top=0) printf(栈溢出！); else s-top=s-top-1; return (s-datas-top); char GetTop(struct Stack *s)/*取栈顶元素*/ if(s-top=0) printf(栈空！); else printf(st=%2c,s-datas-top-1);printf(n); return (s-datas-top-1); /*运算对象栈的相关操作*/struct dStack int data100; int top; Vs;/*定义栈，存放运算对象。当运算对象是一位数时可以是字符， 也可以利用上面原有的字符栈，但超过一位数时只能另外设立数字 栈，及相关的栈处理程序。*/void InitdStack(struct dStack *s)/*初始化栈*/ s-top=0; void Pushd(struct dStack *s, int x)/*入栈（进栈）*/ if(s-top=StackSize) printf(stack overflow); else s-datas-top=x; s-top=s-top+1; int Popd(struct dStack *s)/*退栈（出栈）*/ if(s-top=0) printf(栈溢出！); else s-top=s-top-1; return (s-datas-top); int Priority(char p)/*求运算符优先级函数*/ printf(p=%2c,p);printf(n); switch(p) case(: case#:return(0); case-: case+:return(1); case*: case/:return(2); /*运算对象、运算符，入队、进栈的相关操作*/void CTPOstExp(struct Queue *Q) int i,j; struct Stack *s; char c,t; s=&Os; InitStack(s); /*初始化栈*/ Push(s,#); /*压入栈底元素#*/ printf(请输入表达式，并以“#”结束：);printf(n); do /*扫描中缀表达式*/ c=getchar( ); /*此语句实际连“回车符”共输入两个字符*/ switch(c) case :break; /*去除空格符*/ case0: case1: case2: case3: case4: case5: case6: case7: case8: case9:EnQueue(Q,c);break; case(:Push(s,c);break; case): case#:do t=Pop(s); if(t!=( & t!=#) EnQueue(Q,t); while(t!=( & s-top!=0); break; case+: case-: case*: case/: i=Priority(c);j=Priority(GetTop(s); printf(i=%2d,j=%2d,i,j);printf(n); while(i10)/*此语句是回避“回车符”*/ printf(运算符栈：); for(i=0;itop-1;i+) printf(%2c,s-datai);printf(n); printf(后缀表达式队：); for(i=0;irear-1;i+) printf(%2c,Q-datai);printf(n); while(c!=#);/*以#号结束表达式扫描*/ /*后缀表达式队计算结果操作过程函数*/int CPOstExp(struct Queue *Q) int i,j,x,y; struct dStack *s; char ch; s=&Vs; InitdStack(s); /*初始化栈*/ for(i=0;irear-1;i+) ch=Q-datai; /*从后缀表达式取字符*/ if(ch0 & ch=9)/*判别运算对象或运算符*/j=ch-0;Pushd(s,j);/*此处ch-0是把ASCII码转换成数字，也可直接用ch-0作为实参调 用，但为清晰仍转为整型数j。*/ else /*是运算符则取运算对象运算*/ y=Popd(s); x=Popd(s); /*取运算对象分别存入x、y*/ switch(ch) case+:Pushd(s,x+y);break; case-:Pushd(s,x-y);break; case*:Pushd(s,x*y);break; case/:Pushd(s,x/y);break; printf(后缀表达式队：); for(j=i;jrear-1;j+) printf(%2c,Q-dataj);printf(n); printf(运算对象栈：); for(j=0;jtop-1;j+) printf(%2d,s-dataj);printf(n); main( ) struct Queue