- #include<stdio.h>
- #include<malloc.h>
- #include<string.h>
- #include<stdlib.h>
- typedef struct LNode//链栈
- {
- char op;
- struct LNode *next;
- } LNode,*LinkList;
- LinkList InitStack()
- {
- LinkList pHead;
- pHead=(LNode*)malloc(sizeof(LNode));
- if(!pHead)
- return 0;
- pHead->next=NULL;
- return pHead;
- }
- int push(LinkList pHead,char e)
- {
- LinkList pnew,p=pHead->next;
- pnew=(LNode *)malloc(sizeof(LNode));
- pnew->op=e;
- pnew->next=pHead->next;
- pHead->next=pnew;
- while(p!=NULL)
- {
- p=p->next;
- }
- return 0;
- }
- int isEmpty(LinkList pHead)
- {
- if(pHead->next==NULL)
- return -1;
- else
- return 1;
- }
- int pop(LinkList pHead,char *e)//出栈
- {
- LinkList p;
- p=pHead->next;
- while(p!=NULL)
- {
- *e=p->op;
- pHead->next=p->next;
- }
- if(p==NULL)
- {
- printf("空栈\\n");
- }
- return 0;
- }
- char Gettop(LinkList pHead)//取栈顶
- {
- LinkList p;
- p=pHead->next;
- return p->op;
- }
- int Deletetop(LinkList pHead)//删除栈顶
- {
- LinkList q;
- q=pHead->next;
- pHead->next=q->next;
- free(q);
- return 0;
- }
- int GetLevel(char op)
- {
- if(op=='+'||op=='-')
- return 1;
- if(op=='*'||op=='/')
- return 2;
- return 0;
- }
- int GetRpn(LinkList pHead,char *str,char *rpn)
- {
- int i,cnt=0,length;
- int flag=0;//定义一个旗帜 标志一个数的结束
- length=strlen(str);
- if(str[length-1]=='=')
- {
- length--;
- }
- if(str[0]=='-')
- {
- rpn[cnt++]='0';
- rpn[cnt++]='#';
- }
- char e;
- for(i=0; i<length; i++)
- {
- if(str[i]>='0'&&str[i]<='9')
- {
- rpn[cnt++]=str[i];
- flag=1;
- continue;//直接返回到for循环 i+1后再来
- }//用来输入十位以上的数
- if(flag==1)
- {
- rpn[cnt++]='#';
- flag=0;
- }
- if(str[i]=='('&&str[i+1]=='-')//(-1)这种情况
- {
- rpn[cnt++]='0';
- rpn[cnt++]='#';
- }
- if(str[i]=='(')//左括号直接入栈
- {
- push(pHead,str[i]);
- }
- else if(str[i]==')')
- {
- while(Gettop(pHead)!='(')//右括号是 一直输出到左括号为止
- {
- rpn[cnt++]=Gettop(pHead);
- Deletetop(pHead);
- }
- Deletetop(pHead);;//将左括号出栈
- }
- else if(isEmpty(pHead)!=-1&&GetLevel(str[i])<=GetLevel(Gettop(pHead)))//处理加减乘除
- {
- ///当不是空栈时 比较优先级 同级时将栈顶的取出
- while(isEmpty(pHead)!=-1&&GetLevel(str[i])<=GetLevel(Gettop(pHead)))
- {
- rpn[cnt++]=Gettop(pHead);//
- Deletetop(pHead);
- }
- push(pHead,str[i]);//最小级输入栈中
- }
- else
- {
- push(pHead,str[i]);// - * 这种情况和直接入栈时
- }
- }
- if(flag)
- {
- rpn[cnt++]='#';///当最后一个数输完 continue后刚好跳出循环 就会出现这种情况
- }
- while(isEmpty(pHead)!=-1)
- {
- rpn[cnt++]=Gettop(pHead);
- Deletetop(pHead);
- }
- rpn[cnt++]='\\0';
- return 0;
- }
- int main()
- {
- LinkList pHead=InitStack();
- while(1)
- {
- char str[100],rpn[100];
- gets(str);
- GetRpn(pHead,str,rpn);
- printf("%s \\n",rpn);
- }
- return 0;
- }
- //该片段来自于http://www.codesnippet.cn/detail/2605201512668.html
来源: http://www.codesnippet.cn/detail/2605201512668.html