后缀表达式-逆波兰式-栈-C语言-C++-数据结构-链表-课程设计

#includestdio.h#includectype.h#includeassert.h#includestdlib.h#includeconio.hvoidpostfix(char*infix);#defineSIZE100typedefstruct{chardata[SIZE];inttop;}Stack;typedefstruct{intcount,front,rear;chardata[SIZE];}Queue;/***********Õ»µÄ¹¦ÄÜʵÏÖ*********************//*³õʼ»¯Õ»*/voidinit_stack(Stack*s){s-top=0;}/*²âÊÔÕ»ÊÇ·ñΪ¿Õ*/intempty_stack(Stack*s){return(s-top==0);}/*²âÊÔÕ»ÊÇ·ñÒÑÂú*/intfull_stack(Stack*s){return(s-top==SIZE);}/*ѹջ*/voidpush(Stack*s,charx){if(full_stack(s)){printf(Õ»Òç³ö\n);}else{s-data[s-top]=x;++(s-top);}}/*³öÕ»*/charpop(Stack*s){if(empty_stack(s)){printf(Õ»ÊÇ¿ÕµÄ\n);}else{--(s-top);returns-data[s-top];}return0;}/***************¶ÓÁеŦÄÜʵÏÖ**********************//*³õʼ»¯¶ÓÁÐ*/voidinitq(Queue*q){q-count=0;q-front=0;q-rear=-1;}/*²âÊÔ¶ÓÁÐÊÇ·ñΪ¿Õ*/intemptyq(Queue*q){return(q-count==0);}/*²âÊÔ¶ÓÁÐÊÇ·ñÒÑÂú*/intfullq(Queue*q){return(q-count==SIZE);}/*Ïò¶ÓÁвåÈëÒ»¸öÔªËØ*/voidinsertq(chary,Queue*q){if(fullq(q)){printf(¶ÓÁÐÒç³ö\n);}else{q-rear=(q-rear+1)%SIZE;q-data[q-rear]=y;q-count++;}}/*ÒƳýÒ»¸öÔªËز¢½²ËüµÄÖµ·µ»Ø*/charremoveq(Queue*q){chary;if(emptyq(q)){printf(¶ÓÁÐÊÇ¿ÕµÄ\n);}else{y=q-data[q-front];q-front=(q-front+1)%SIZE;--(q-count);returny;}return0;}/***********Ö÷º¯Êý****************/intmain(void){charinfx[]=A+B*(C/D-E)*F-G;/*Êä³öʾÀý*/charinput[SIZE];printf(Àý×Ó\nÊäÈë:\n%s\nÊä³ö:\n,infx);postfix(infx);while(1){printf(\nÈÎÒâ¼ü¿ªÊ¼ÊäÈ룬°´EscÍ˳ö...\n);if(getch()==27)return0;printf(\nÇëÊäÈëÖÐ׺±í´ïʽ:);/*ÌáʾÊäÈë*/scanf(%s,input);postfix(input);}getch();/*°´ÈÎÒâ¼ü¼ÌÐø*/return0;}intis_number(charch){if(ch='A'&&ch='Z'||ch='a'&&ch='z'||ch='0'&&ch='9')return1;return0;}/*תºó׺±í´ïʽº¯Êý*/voidpostfix(char*infix){Queueq;Stacks;inti=0;charch,temp;intpriority[256];/*Ϊÿ¸öasciiÂëÔ¤¶¨ÒåÓÅÏȼ¶*/initq(&q);/*³õʼ»¯Õ»ºÍ¶ÓÁÐ*/init_stack(&s);push(&s,'\0');priority['*']=3;priority['/']=3;/*³õʼ»¯ÓÅÏȼ¶*/priority['+']=2;priority['-']=2;priority['(']=1;priority[')']=1;priority['$']=0;do{ch=infix[i++];if(is_number(ch))/*Èç¹ûÊÇ´óд×Öĸ*/{insertq(ch,&q);/*²åÈë¶ÓÁÐ*/}elseif(ch==')')/*Èç¹ûÊÇÓÒÀ¨ºÅ*/{temp=pop(&s);/*µ¯³ö×óÀ¨ºÅÇ°µÄËùÓÐÔËËã·û*/while(temp!='('){insertq(temp,&q);/*°Ñµ¯³öµÄÔËËã·û²åÈë¶ÓÁÐ*/temp=pop(&s);}}elseif(ch=='\0')/*Èç¹ûÊǽáÊø·û*/{while(!empty_stack(&s)){temp=pop(&s);insertq(temp,&q);/*°ÑÕ»ÄÚÊ£ÓàµÄÔËËã·û²åÈë¶ÓÁÐ*/}}elseif(ch=='(')/*Èç¹ûÊÇ×óÀ¨ºÅ*/{push(&s,ch);}elseif(ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch=='$')/*Èç¹ûÊÇÔËËã·û*/{temp=pop(&s);while(priority[(int)temp]=priority[(int)ch])/*±È½ÏÓÅÏȼ¶*/{insertq(temp,&q);temp=pop(&s);}push(&s,temp);push(&s,ch);}else/*ÆäËû×Ö·û±¨´í*/{printf(·Ç·¨×Ö·û%ch\n,ch);exit(-1);}}while(ch!='\0');for(i=0;!emptyq(&q);i++)/*°´Ë³Ðò´òÓ¡¶ÓÁÐÀïµÄ×Ö·û*/printf(%c,removeq(&q));printf(\n);}