为了简化问题，不妨假设所有数据都是int 型，运算符都是二元操作符（,）,+,-,*,/函数原型int Calc(char *str);例如main(){ int value; value=Calc（"8+5*4-6/2"）； printf("\\n%d",value); getch();}
以前做的，-------------------#include<iostream.h>#include<stdlib.h>#include<conio.h>typedef struct{ int data[100]; int top;}A;int g(char ch){ char *s="0123456789+-*/"; while(*s!=\'+\'){ if(ch==*s) return 1;//数字 s++; } while(*s!=\'*\'){ if(ch==*s) return 2;//\'+\',\'-\' s++; } while(*s!=\'\\0\'){ if(ch==*s) return 3;//\'*\',\'/\' s++; } return 0;}void G(A *p,A *q,char *s){ p->top=q->top=-1; while(*s!=\'\\0\'){ if(g(*s)==1) q->data[++q->top]=*s; else if(*s==\'(\') p->data[++p->top]=*s;
else if(*s==\')\'){ while(p->data[p->top]!=\'(\') q->data[++q->top]=p->data[p->top--]; p->top--; } else if(*s==\'+\'||*s==\'-\'){ while(g(p->data[p->top])==2||g(p->data[p->top])==3) q->data[++q->top]=p->data[p->top--]; p->data[++p->top]=*s; } else if(*s==\'*\'||*s==\'/\'){ while(g(p->data[p->top])==3) q->data[++q->top]=p->data[p->top--]; p->data[++p->top]=*s; } s++; } while(p->top!=-1) q->data[++q->top]=p->data[p->top--];}void F(int *z,int x,int y,char c){ switch(c){ case \'+\': *z=x+y; break; case \'-\': *z=x-y; break; case \'*\': *z=x*y; break; case \'/\': *z=x/y; break; }}int f(A *q){ A *p=(A *)malloc(sizeof(A)); p->top=-1; for(int i=0;i<=q->top;i++){ if(g(q->data)==1) p->data[++p->top]=q->data-48; else if(g(q->data)==2||g(q->data)==3) { F(&p->data[p->top-1],p->data[p->top-1],p->data[p->top],q->data); p->top--; } } return p->data[p->top];}void main(){ char s[]="1+2*(7-6+0+3)/4-1";//原算术表达式 cout<<"原算术表达式是："<<endl<<s<<endl; A *p=(A *)malloc(sizeof(A)),*q=(A *)malloc(sizeof(A)); G(p,q,s); cout<<"其逆波兰表达式是："<<endl; for(int i=0;i<=q->top;i++) cout<<(char)q->data; cout<<endl<<s<<"="<<f(q)<<endl; getch();}
提问者对答案的评价：
//c++版的#include <iostream>using namespace std;typedef enum prio{add=0,sub,mul,divi,bra_f,bra_r,nus}prio; //+,-,*,/,(,),#typedef struct Stack{ //栈的数据节点 union{ int opnd;//运算数 prio optr; //运算符 };//union struct Stack* next;}Stack,*Stackp;//Stacktypedef struct LStack{ //栈的总结点 Stackp base; Stackp top;}LStack;//LStackchar priority[7][7]={\'>\',\'>\',\'<\',\'<\',\'<\',\'>\',\'>\',\'>\',\'>\',\'<\',\'<\',\'<\',\'>\',\'>\',\'>\',\'>\',\'>\',\'>\',\'<\',\'>\',\'>\',\'>\',\'>\',\'>\',\'>\',\'<\',\'>\',\'>\',\'<\',\'<\',\'<\',\'<\',\'<\',\'=\',\' \',\'>\',\'>\',\'>\',\'>\',\' \',\'>\',\'>\',\'<\',\'<\',\'<\',\'<\',\'<\',\' \',\'=\'};bool InitStack(LStack &S){ //构造一个空栈S //成功返回true,否则返回false S.base=(S.top=NULL); return true;}//InitStackbool StackEmpty(LStack S){ //判断一个栈S是否为空 return S.top==NULL?true:false;}//StackEmptyStackp Pop(LStack &S){ //删除栈顶元素，并返回其地址 //若栈为空 返回NULL Stackp p; if(StackEmpty(S)) return NULL; p=S.top; S.top=S.top->next; return p;}//Popvoid Push(LStack &S,Stackp &e){ //插入一个元素e 为新的栈顶 e->next=S.top; S.top=e;}//Pushvoid DestroyStack(LStack &S){ //销毁一个栈S Stackp p; while(!StackEmpty(S)){ p=Pop(S); delete p; }//while}//DestroyStackvoid trans(char c,prio &pri){//运算符转换 switch(c){ case \'+\':pri=add;break; case \'-\':pri=sub;break; case \'*\':pri=mul;break; case \'/\':pri=divi;break; case \'(\':pri=bra_f;break; case \')\':pri=bra_r;break; case \'#\':pri=nus;break; default:cout<<"输入有误"<<endl;exit(0); };//switch}//transvoid doopertor(Stackp &n,Stackp &m,prio pri_in){//运算 switch(pri_in){ case add: n->opnd=n->opnd+m->opnd; break; case sub: n->opnd=n->opnd-m->opnd; break; case mul: n->opnd=n->opnd*m->opnd; break; case divi: n->opnd=n->opnd/m->opnd; break; default: cout<<"致命错误！"<<endl; }//switch}//doopertorint main(){ LStack OPND;//运算数栈 LStack OPTR;//运算符栈 prio pri,pri_in; InitStack(OPND); InitStack(OPTR); Stackp e=new Stack; e->next=NULL; e->optr=nus; Push(OPTR,e); int c,a,flag=0; // c=getchar(); while(c!=\'\\n\'){ if(c>=\'0\'&&c<=\'9\'){ a=c-\'0\'; if(flag==0){ e=new Stack; e->next=NULL,e->opnd=a; Push(OPND,e); flag=1; }//if else{ Stackp q; q=Pop(OPND); q->opnd=q->opnd*10+a; Push(OPND,q); }//else } else{ flag=0; trans(c,pri); pri_in=OPTR.top->optr; Stackp q=new Stack; q->optr=pri; switch(priority[pri_in][pri]){ case \'<\':Push(OPTR,q);break; case \'=\': if(pri==bra_r){ delete q; q=Pop(OPTR); delete q; }//if delete q; break; case \'>\': while(priority[pri_in][pri]==\'>\'){ Stackp m,n; m=Pop(OPND); n=Pop(OPND); doopertor(n,m,pri_in); Push(OPND,n); delete m; n=Pop(OPTR); delete n; pri_in=OPTR.top->optr; }//while if(q->optr!=bra_r) Push(OPTR,q); else{ delete q; q=Pop(OPTR); delete q; } break; default:break; };//switch }//else c=getchar(); }//while //cout<<OPND.top->next->opnd<<endl; cout<<OPND.top->opnd<<endl; DestroyStack(OPND); return 0;} |
