逆波兰表达式.cpp

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

#include   <conio.h>
#include   <stdio.h>
#include   <assert.h>
#include   <afx.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('#');
	}

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


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

    else if(e==')'){
         while((!OPTR.IsEmpty())&&(c=OPTR.GetTop())!='('){
				  OPND.Push(c);OPTR.Pop();
		 }
				e=getchar();OPTR.Pop();
	}	
}	
printf("\n逆波兰算术表达式为(“#”为分隔符号)：\n\n");

while(!OPND.IsEmpty()){c=OPND.GetTop();OPTR.Push(c);OPND.Pop();}
CString str1,str2;int k=0;
str1.Empty;str2.Empty();

while(!OPTR.IsEmpty()){
	c=OPTR.GetTop();
	printf("%c",c);
	OPTR.Pop();
	if(c!='+'&&c!='-'&&c!='*'&&c!='/')
		OPND.Push(c);
	else{
		if(!OPND.IsEmpty()){
			e=OPND.GetTop();
			if(e=='#'){
				e=OPND.Pop();
				e=OPND.GetTop();
			}
			while(e!='#'&&!OPND.IsEmpty()){
				str2.Insert(str2.GetLength(),e);
				OPND.Pop();
				e=OPND.GetTop();
			}
			OPND.Pop();
			e=OPND.GetTop();
			while(e!='#'&&!OPND.IsEmpty()){
				str1.Insert(str1.GetLength(),e);
				OPND.Pop();
				if(!OPND.IsEmpty())
					e=OPND.GetTop();
			}
			if(c=='+')
				str1.Format("%d",atoi(str1)+atoi(str2));
			else if(c=='-')
				str1.Format("%d",atoi(str1)-atoi(str2));
			else if(c=='*')
				str1.Format("%d",atoi(str1)*atoi(str2));
			else if(c=='/')
				str1.Format("%d",atoi(str1)/atoi(str2));
			while(!str1.IsEmpty()){
				OPND.Push(str1.GetAt(str1.GetLength()-1));
				str1.Delete(str1.GetLength()-1);
			}
			OPND.Push('#');
			str1.Empty();
			str2.Empty();
		}
	}
}
printf("\n\n运算结果：");
if(OPND.GetTop()=='#')
	OPND.Pop();
while(!OPND.IsEmpty()){
	printf("%c",OPND.GetTop());
	OPND.Pop();
}
printf("\n");
getch();
}