Stack s; InitStack(s); int i=0,j=0; ElemType e; Push(s,Buffer[i]); i++; while(Buffer[i]!='#'){ if(!IsOperator(Buffer[i])){ // 是操作数 Buffer[j]=Buffer[i]; i++; j++; } else{ // 是操作符 GetTop(s,e); if(Prior(e,Buffer[i])){// 当栈顶优先权高于当前序列时，退栈 Pop(s,e); Buffer[j]=e; j++; } else{ Push(s,Buffer[i]); i++; } } } while(!StackEmpty(s)){ Pop(s,e); Buffer[j]=e; j++; } }
Status IsOpertor(char c) { char *p=\ while(*p){ if(*p==c) return TRUE; p++; } return FALSE; }
Status Prior(char c1,char c2) { char ch[]=\ int i=0,j=0; while(ch[i] && ch[i]!=c1) i++; if(i==2) i--; // 加和减可认为是同级别的运算符 if(i==4) i--; // 乘和除可认为是同级别的运算符 while(ch[j] && ch[j]!=c2) j++; if(j==2) j--; if(j==4) j--; if(i>=j) return TRUE; else return FALSE; }
3.22 如题3.21的假设条件，试写一个算法，对以逆波兰式表示的表达式求值。 解：
char CalVal_InverPoland(char Buffer[]) { Stack Opnd; InitStack(Opnd); int i=0; char c; ElemType e1,e2; while(Buffer[i]!='#'){ if(!IsOperator(Buffer[i])){ Push(Opnd,Buffer[i]); } else{ Pop(Opnd,e2); Pop(Opnd,e1); c=Cal(e1,Buffer[i],e2); Push(Opnd,c); } i++; } return c; }
21
char Cal(char c1,char op,char c2) { int x,x1,x2; char ch[10]; ch[0]=c1; ch[1]='\\0'; x1=atoi(ch); ch[0]=c2; ch[1]='\\0'; x2=atoi(ch); switch(op){ case '+': x=x1+x2; break; case '-': x=x1-x2; break; case '*': x=x1*x2; break; case '/': x=x1/x2; break; default: break; } itoa(x,ch,10); return ch[0]; }
3.23 如题3.21的假设条件，试写一个算法，判断给定的非空后缀表达式是否为正确的逆波兰表达式，如果是，则将它转化为波兰式。解：
#include
#include \
typedef char ARRAY[30]; typedef ARRAY ElemType; typedef struct NodeType{ ElemType data; NodeType *next; }NodeType,*LinkType; typedef struct{ LinkType top; int size; }Stack;
void InitStack(Stack &s);
Status Push(Stack &s,ElemType e); Status Pop(Stack &s,ElemType e); Status IsOperator(char c); Status StackEmpty(Stack s);
Status InvToFroPoland(char a[]);
int main() { char a[30]; cout<<\请输入逆波兰算术表达式字符序列：\ cin>>a; if(InvToFroPoland(a)) cout< Status InvToFroPoland(char a[]) { Stack s; InitStack(s); int i=0; ElemType ch; ElemType c1; ElemType c2; while(a[i]!='#'){ if(!IsOperator(a[i])){ if(a[i]>='0' && a[i]<='9'){ ch[0]=a[i]; ch[1]='\\0'; Push(s,ch); } 22 else return FALSE; } else{ ch[0]=a[i]; ch[1]='\\0'; if(!StackEmpty(s)){ Pop(s,c2); if(!StackEmpty(s)){ Pop(s,c1); strcat(ch,c1); strcat(ch,c2); Push(s,ch); } else return FALSE; } else return FALSE; } i++; } if(!StackEmpty(s)){ Pop(s,c1); strcpy(a,c1); } else return FALSE; if(!StackEmpty(s)) return FALSE; return OK; } void InitStack(Stack &s) { s.top=NULL; s.size=0; } Status Push(Stack &s,ElemType e) { LinkType p; p=new NodeType; if(!p) exit(OVERFLOW); p->next=s.top; s.top=p; strcpy(p->data,e); s.size++; return OK; } Status Pop(Stack &s,ElemType e) { LinkType p; if(s.top){ strcpy(e,s.top->data); p=s.top; s.top=p->next; delete p; s.size--; } return OK; } Status StackEmpty(Stack s) { if(s.size==0) return TRUE; else return FALSE; } Status IsOperator(char c) { char *p=\ while(*p){ if(*p==c) return TRUE; p++; } return FALSE; } 3.24 试编写如下定义的递归函数的递归算法，并根据算法画出求g(5,2)时栈的变化过程。m?0,n?0 g?m,n???0??g?m?1,2n??nm?0,n?0解： int g(int m,int n); int main() 23 { int m,n; cout<<\请输入m和n的值：\ cin>>m>>n; if(n>=0) cout< int g(int m,int n) { if(m>0) return(g(m-1,2*n)+n); else return 0; } 假设主函数的返回地址为0，递归函数3条语句的地址分别为1、2、3。 3 0 64 3 1 32 3 2 16 3 3 8 3 4 4 0 5 2 3.25 试写出求递归函数F(n)的递归算法，并消除递归： F?n???n?1n?0 ????n?F?n2?n?0 解： #include 3.26 求解平方根 A的迭代函数定义如下： ?pp2?A?e sqrt?A,p,e??????sqrt?2 ??A,1??A???p??,e?p?A?e?2?p????其中，p是A的近似平方根，e是结果允许误差。试写出相应的递归算法，并消除递归。 解： #include double Sqrt(double A,double p,double e); int main() { double A,p,e; cout<<\请输入A p e:\ cin>>A>>p>>e; cout< double Sqrt(double A,double p,double e) { if((p*p-A)>-e && (p*p-A) 3.27 已知Ackerman函数的定义如下： ?n?1m?0 akm?m,n????akm?m?1,1?m?0,n?0 ??akm?m?1,akm?m,n?1??m?0,n?0 (1) 写出递归算法； (2) 写出非递归算法； 24
