逆波兰表达式.txt

编译程序的实验~~ 很详细哈..需要的下来看看!

#include   <conio.h>
#include   <stdio.h>
#include   <assert.h>
template <class Type> class PL;			
template <class Type> class PLNode {
friend class PL<Type>;
private: 
    Type data;	                         //结点数据	
    PLNode<Type> *link;	 //结点链指针	
    PLNode ( Type d=0, PLNode<Type>
         *l=NULL ) : data (d), link (l) { }
};

template <class Type> 
class PL {		
public:
    PL ( ) : top ( NULL ) { }
    ~PL ();
    void Push ( const Type & e);
    Type Pop ( );
    Type GetTop ( );
    void MakeEmpty ( ) { top=NULL; }
    int IsEmpty ( ) const 
         { return top == NULL; }
private:
    PLNode<Type> *top;       //栈顶指针
};

template <class Type>
  PL<Type>::~PL( ) {
     PLNode<Type> *p;
     while ( top != NULL )      //逐结点回收
 	 { p = top;  top = top->link;  delete p; }
}


template <class Type> 
void PL<Type>::Push (const Type &e){
    top=new PLNode<Type>(e,top);
    //新结点链入top之前, 并成为新栈顶
}

template <class Type> Type PL<Type>::
Pop ( ) {
    assert( !IsEmpty ( ) );			
    PLNode<Type>*p=top;
    Type retvalue=p->data;	 //暂存栈顶数据
    top=top->link;		         //修改栈顶指针
    delete p;   return retvalue;	 //释放,返回数据
}

template <class Type> Type PL<Type>::
GetTop ( ) {
    assert( !IsEmpty ( ) );
    return top->data;
} 



void main()
{PL <char> OPTR,OPND,A;char c;char  e;int i=0;
printf("本程序只考虑加、减、乘、除和小括号（）\n\n");
printf("请输入中缀算数表达式：");
e=getchar();
while(e!='\n'){
    
	if(e>='0'&&e<='9'){
		OPND.Push(e);e=getchar();
		    while(e!='\n'&&e>='0'&&e<='9'){			
				OPND.Push(e);e=getchar();
			}
	    OPND.Push('#');
	}

    if(e=='/'||e=='*'){		                 
		    while((!OPTR.IsEmpty ( ))&&(c=OPTR.GetTop())!='('){
				        OPTR.Pop();OPND.Push(c);
			}
             OPTR.Push(e);e=getchar();			
	}


    if(e=='+'||e=='-'){		        	            	               
			while((!OPTR.IsEmpty ( ))&&(c=OPTR.GetTop())!='('){
				  OPTR.Pop();OPND.Push(c);
			}
              OPTR.Push(e);e=getchar();			   
	}
    
	if(e=='('){
		OPTR.Push(e);e=getchar();
	}

    if(e==')'){
         while((!OPTR.IsEmpty ( ))&&(c=OPTR.GetTop())!='('){
				  OPND.Push(c);OPTR.Pop();
		 }
				e=getchar();OPTR.Pop();
	}	
}	
printf("逆波兰算术表达式为：\n");
while(!OPND.IsEmpty ( )){c=OPND.GetTop();OPTR.Push(c);OPND.Pop();};
while(!OPTR.IsEmpty ( )){c=OPTR.GetTop();printf("%c",c);OPTR.Pop();};
getch();
}