cal.cpp

数据结构作业

#include<iostream.h>
#include<ctype.h>
#include<assert.h>
#include<math.h>
template <class Type> class Stack;

template <class Type> class StackNode {
friend class Stack<Type>;
private: 
    Type data;	                         //结点数据	
    StackNode<Type> *link;       //结点链指针
public:
    StackNode ( Type d = 0, StackNode<Type>
         *l = NULL ) : data ( d ), link ( l ) { }
}; 
template <class Type> class Stack {
private:
    StackNode<Type> *top;       //栈顶指针
public:
    Stack ( ) : top ( NULL ) { }
    ~Stack ( );
    void Push ( const Type & item);   //进栈
      int Pop ( );                                      //退栈
     Type GetTop ( );       //读取栈顶元素
     void MakeEmpty ( );   //实现与~Stack( )同
    int IsEmpty ( ) { return top == NULL; }
};
template <class Type> Stack<Type>::
~Stack ( ) {
     StackNode<Type> *p;
     while ( top != NULL )       //逐结点回收
 	 { p = top;  top = top->link;  delete p; }
}

template <class Type> void Stack<Type> ::
Push ( const Type &item ) {
    top = new StackNode<Type> ( item, top );
    //新结点链入*top之前, 并成为新栈顶
}
template <class Type> int Stack<Type> ::
Pop ( ) { 
    if ( IsEmpty ( ) ) return 0;		
    StackNode<Type> *p = top;
    top = top->link;	          //修改栈顶指针
    delete p;   return 1;         //释放
}

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


int icp(char ch)
{	
	int i;
	switch(ch){
		case '=':i=0;break;
		case '(':i=8;break;
		case '^':i=6;break;
		case '*':
		case '/':
		case '%':
			i=4;break;
		case '+':
		case '-':i=2;break;
		case ')':i=1;break;
	
	}
	return i;
}

int isp(char ch)
{	
	int i;
	switch(ch){
		case '=':i=0;break;
		case '(':i=1;break;
		case '^':i=7;break;
		case '*':
		case '/':
		case '%':
			i=5;break;
		case '+':
		case '-':i=3;break;
		case ')':i=8;break;
	
	}
	return i;
}
double DoOperator(double op1,double op2,char ch)
{
	switch(ch){

	case '+':op1+=op2;break;
	case '-':op1-=op2;break;
	case '*':op1*=op2;break;
	case '/':op1/=op2;break;
	case '^':op1=pow(op1,op2);break;
		
	}
	return op1;
}
void main()
{
	Stack<char>OPTR;
	Stack<double>OPND;
	double op1,op2,newoperand;
	char c,ch;

	OPTR.Push('=');
	cout<<"链表堆栈求解中缀算术表达式："<<endl;
	cout<<"请输入中缀算术表达式(中间可不加空格，可包含+、-、*、/、^、(、)，以“=”结束)："<<endl;
	cout<<"分步骤计算如下："<<endl;
	do
	{
		cin>>ch;
		if(isdigit(ch))
		{
			cin.putback(ch);
			cin>>newoperand;
			OPND.Push(newoperand);
					
		}
		else
		{
			if (isp(OPTR.GetTop())< icp(ch) )
			OPTR.Push(ch);
		
			
			else 
			{
				while(isp(OPTR.GetTop())> icp(ch) && OPTR.GetTop()!='(')
			{

				op2=OPND.GetTop();OPND.Pop();
				op1=OPND.GetTop();OPND.Pop();
				c=OPTR.GetTop();OPTR.Pop();
				OPND.Push(DoOperator(op1,op2,c));
				cout<<op1<<c<<op2<<'='<<DoOperator(op1,op2,c)<<endl;

			}
			if(ch!=')' )  OPTR.Push(ch);
			}
			if(isp(OPTR.GetTop())==icp(ch) &&  ch==')') OPTR.Pop(); 
		}
	}while(ch != '=');
	cout<<"算术表达式最后的计算结果等于"<<OPND.GetTop()<<endl;
}