实验表达式.cpp

模式识别的两个重要算法:剃度下降法,固定增量法.另付数据结构中:高级排序算法,波兰式

#include<assert.h>
#include<iostream.h>
template <class Type>


class Stack
{
protected:
    int top;	                   //栈顶指针
    Type *elements;	              //栈元素数组
    int maxSize;	                  //栈最大容量
public:
    Stack ( int sz = 10 );        //构造函数
    ~Stack ( ){ delete [ ] elements; }
	void Push (Type  item);    //进栈
    //void Pop( Type & item);            //出栈
	Type Pop();
    Type GetTop ();                   //取栈顶
	void Trans(Type str[],Type exp[]);
	void Compvalve(Type exp[]);

    void MakeEmpty ( ){ top=-1; }   
    int IsEmpty( )const { return top==-1;}
    int IsFull ( ) const  
	{ return top==maxSize-1;}
};


template <class Type>
Stack<Type> ::Stack ( int s ) : top (-1), maxSize (s)
{
    elements = new Type[maxSize];
    assert ( elements != NULL );        //断言
}

template <class Type>
void Stack<Type> ::Push ( Type  item )
{
    assert ( !IsFull ( ) );	   //先决条件断言
    elements[++top] = item;  
};


template <class Type>
Type Stack<Type>::Pop()
{   
	Type Item;     
	if(IsEmpty()==1)return 0;//栈空不退栈
	Item=elements[top]; 		
	top--; 		
	return Item ;  
	             //退出栈顶元素
}
template <class Type>
Type Stack<Type>::GetTop ( )
{
    assert (!IsEmpty( ));	   //先决条件断言
	if(IsEmpty())return 0;
    return elements[top] ;       //取出栈顶元素
}

/////////////////////////////////////////////////////////
template <class Type>
void Stack<Type>::Trans(Type str[],Type exp[])//转换成波兰式
{    
	Type ch;
	int i,k;
	k=0,i=0;
	ch=str[i];
	i++;
	
	while(ch!='#')
	{
		if(ch>='0'&&ch<='9')
		{exp[k++]=ch;}
		else if(   ch==   '('    )Push(ch);			
		else if(   ch==   ')'    )		
		{				
			while(    GetTop()!=   '('    )						
			{ 					
						exp[k++]=Pop();						
			}			
			Pop();				
		}				
		else if(ch=='+'||ch=='-')				
		{				
			while(IsEmpty()!=1&&GetTop()!=   '('   )							
			{							
				exp[k++]=Pop();		
			}						
			Push(ch);		
		}					
		else if(ch=='*'||ch=='/')						
		{						
			while(GetTop()=='*'||GetTop()=='/')								
			{								
				exp[k++]=Pop();							
			}							
			Push(ch);						
		}						
		ch=str[i++];
	}
	while(IsEmpty()!=1)		
	{	
	
		exp[k++]=Pop();
	}
	exp[k]='#';
	for(int j=0;j<k;j++)
		cout<<exp[j];
	cout<<endl;
}
template <class Type>
void Stack<Type>::Compvalve(Type exp[])//计算
{
	char c;
	int i=0,k=0,top=-1;
	while(exp[k]!='#')k++;
    c=exp[i++];
    float stack[100],data;
	while(c!='#')
	{
		data=c-'0';                         //将字符转换成数字
		if(c>='0'&&c<='9')stack[++top]=data;
		else
		{			
			switch (c)			
			{						
			case'+': stack[top-1]=stack[top-1]+stack[top];break;
			case'-': stack[top-1]=stack[top-1]-stack[top];break;
			case'*': stack[top-1]=stack[top-1]*stack[top];break;
			case'/': 
				{
					if(stack[top]!=0)
					stack[top-1]=stack[top-1]/stack[top];
					else cout<<"除数为0！"<<endl;						
					break;
				}
			}
			top--;
		}
		c=exp[i++];
	}
	cout<<stack[top]<<endl;
}

void main()
{
	typedef Stack<char> IntStack;
	IntStack st(100);	
	int k=0;
	char a;
	char str[100],exp[100];
	cin>>a;
	while(a!='#')
	{
		str[k++]=a;
		cin>>a;
	}
	st.Trans(str,exp);
	cout<<"结果为：";
	st.Compvalve(exp);

}