《数据结构实验——中缀表达式向后缀表达式的转化(包括四则运算和幂运算)——详细注释》由会员分享，可在线阅读，更多相关《数据结构实验——中缀表达式向后缀表达式的转化(包括四则运算和幂运算)——详细注释（11页珍藏版）》请在金锄头文库上搜索。
1、数据结构实验中缀表达式向后缀表达式的转化(包括四则运算和幂运算)详细注释#include#include/*输入输出说明：输入，输入一中缀表达式并紧接符号 # 以结束输入，输入样例如下，a+b*c+(d*e+f)*g#c*a+b*d-(e+f*g)*h#a*(b+c/(d+e+f)+g)-h#输入注意，括号一律用圆括号输出，输出相应后缀表达式，输出样例如下，abc*+de*f+g*+ca*bd*+efg*+h*-abcde+f+/+g+*h-#带幂运算的优先级顺序(左低右高) + , * , ( + , , ( 注意，加减具有同一优先级,乘除具有同一优先级,且幂运算 与乘法运算 * 的优先级顺
2、序不具有可比性!#样例输入：3*65*2#3*23223+2*5-5#6+3*23*223*4+5#样例输出：3652*323223*?5*+5-63232234*+5+注意：第二组数据输出中的 ? 本该是 2 ，经过长时间测试及数据对比，至今仍未找到确切原因，故尚且属于未知错误，作特殊情况处理! */struct hichar ch;hi *next;hi *plus_minus(hi *tempstack)while(tempstack!=NULL)if(tempstack-ch=()/如果遇到左括号就返回“空”，return NULL;/因为说明要输入的元素本身就包含在一组括号中else
3、 if(tempstack-ch=+|tempstack-ch=-)return tempstack;tempstack=tempstack-next;return NULL;/没有找到优先级更高的则返回“空”hi *mul_div(hi *tempstack)while(tempstack!=NULL)if(tempstack-ch=(|tempstack-ch=)return NULL;else if(tempstack-ch=*|tempstack-ch=/)return tempstack;tempstack=tempstack-next;return NULL;hi *power(h
4、i *tempstack,hi *temptail)while(tempstack!=NULL)if(tempstack-ch=()return NULL;else if(tempstack-ch=)/如果有幂运算就全部弹出return temptail;/所以返回尾部地址tempstack=tempstack-next;return NULL;hi *sign(hi *tempstack)while(tempstack!=NULL)if(tempstack-ch=()return tempstack;tempstack=tempstack-next;return NULL;int main(
5、)int i,j;hi *stack,*temp,*freenode,*tail,*index,*pointer;temp=(hi*)malloc(sizeof(hi);stack=(hi*)malloc(sizeof(hi);/这里和temp区别开申请内存后面比较好处理tail=stack;tail-next=NULL;/提前封栈while(true)scanf(%c,&temp-ch);if(temp-ch=#)/输入停止while(stack!=NULL)if(stack-ch=(|stack-ch=)printf(nFool, error!);break;printf(%c,stack
6、-ch);stack=stack-next;puts();break;/处理操作符if(temp-ch=|temp-ch=+|temp-ch=-|temp-ch=*|temp-ch=/|temp-ch=(|temp-ch=)/处理幂运算if(temp-ch=)/如果是幂运算符就直接压栈temp-next=stack;stack=temp;temp=(hi*)malloc(sizeof(hi);/处理加减else if(temp-ch=+|temp-ch=-)pointer=plus_minus(stack);/加减时先考虑优先级低的if(pointer=NULL)pointer=power(s
7、tack,tail);if(pointer=NULL)pointer=mul_div(stack);/再考虑优先级高的if(pointer=NULL)temp-next=stack;stack=temp;temp=(hi*)malloc(sizeof(hi);/tail-next=NULL;/试试可不可以再开始的时候就封栈else if(pointer!=NULL)while(stack!=pointer)printf(%c,stack-ch);freenode=stack;stack=stack-next;free(freenode);printf(%c,stack-ch);stack-ch
8、=temp-ch;/处理乘除else if(temp-ch=*|temp-ch=/)pointer=mul_div(stack);if(pointer=NULL)temp-next=stack;stack=temp;temp=(hi*)malloc(sizeof(hi);/tail-next=NULL;else if(pointer!=NULL)while(stack!=pointer)printf(%c,stack-ch);freenode=stack;stack=stack-next;free(freenode);printf(%c,stack-ch);stack-ch=temp-ch;/
9、处理括号else if(temp-ch=(|temp-ch=)if(temp-ch=()temp-next=stack;stack=temp;temp=(hi*)malloc(sizeof(hi);/tail-next=NULL;else if(temp-ch)pointer=sign(stack);if(pointer=NULL)printf(nFool, error!n);break;else if(pointer!=NULL)while(stack!=pointer)/注意圆括号的输出printf(%c,stack-ch);freenode=stack;stack=stack-next;free(freenode);freenode=stack;stack=stack-next;free(freenode);/处理操作数elsechar markch=temp-ch;printf(%cn,markch);printf(%c,temp-ch);/如果不是操作符就默认为操作数输出system(pause);return 0;
