msp.cpp

本程序的主要功能是实现多项式的求值

#include <ctype.h>
#include <iostream>
using namespace std;
enum Error_code{success,underflow,overflow};


template <class Node_entry>
struct Node
{
	Node_entry entry;
	Node<Node_entry> *next;
	Node();
	Node(Node_entry tm,Node<Node_entry> *p=NULL);
};

template <class Node_entry>
Node<Node_entry>::Node()
{
	next=NULL;
}

template <class Node_entry>
Node<Node_entry>::Node(Node_entry tm,Node<Node_entry> *p)
{
	entry=tm;
	next=p;
}

//"Stack.h"

template <class Stack_entry>
class Stack
{
	private:
		Node<Stack_entry> *head;
		int count;
	public:
		Stack();
		Stack(const Stack<Stack_entry> &s);
		bool empty() const;
		Error_code push(const Stack_entry &x);
		Error_code top(Stack_entry &x) const;
		Error_code pop();
		Stack<Stack_entry> & operator=(const Stack<Stack_entry> &s);
		~Stack();
};

template <class Stack_entry>
Stack<Stack_entry>::Stack()
{
	head=NULL;
	count=0;
}


template <class Stack_entry>
Stack<Stack_entry>::Stack(const Stack<Stack_entry> &s)
{
	Node<Stack_entry> *p=s.head;
	Node<Stack_entry> *q=head=new Node<Stack_entry>(p->entry);
	while(p->next!=NULL)
	{
		p=p->next;
		q->next=new Node<Stack_entry>(p->entry);
		q=q->next;
	}
}

template <class Stack_entry>
bool Stack<Stack_entry>::empty() const
{	return(head==NULL);  	}

template <class Stack_entry>
Error_code Stack<Stack_entry>::push(const Stack_entry  &x)
{
	Node<Stack_entry> *p=new Node<Stack_entry>(x,head);
	if(p==NULL)return overflow;
	head=p;
	return success;
}

template <class Stack_entry>
Error_code Stack<Stack_entry>::top(Stack_entry &x) const
{
	if(head==NULL)return underflow;
	x=head->entry;
	return success;
}

template <class Stack_entry>
Error_code Stack<Stack_entry>::pop()
{
	Node<Stack_entry> *p=head;
	if(p==NULL)return underflow;
	head=head->next;
	delete p;
	return success;
}

template <class Stack_entry>
Stack<Stack_entry> &Stack<Stack_entry>::operator =(const Stack<Stack_entry> &s)
{
	Node<Stack_entry> *p=head;
	while(p!=NULL)
	{
		head=head->next;
		delete p;
		p=head;
	}
	p=s.head;
	Node<Stack_entry> *q=head=new Node<Stack_entry>(p->entry);
	while(p->next!=NULL)
	{
		p=p->next;
		q->next=new Node<Stack_entry>(p->entry);
		q=q->next;
	}
	return (*this);
}

template <class Stack_entry>
Stack<Stack_entry>::~Stack()
{
	Node<Stack_entry> *p=head;
	while(p!=NULL)
	{
		head=head->next;
		delete p;
		p=head;
	}
}

//"Queue.h"
template <class queue_entry>
class Queue
{
	protected:
		struct Node
		{
			queue_entry item;
			Node *next;
			Node(queue_entry item_t,Node *n=NULL)
			{item=item_t;next=n;}
		};
		Node *front,*rear;
		int count;
	public:
		Queue()
		{front=NULL;rear=NULL;count=0;}
		Queue(const Queue<queue_entry> &s);
		bool empty() const
		{return(front==NULL&&rear==NULL);}
		int size() const
		{return count;}
		void clear();
		Error_code append(const queue_entry &x);
		Error_code retrieve(queue_entry &x) const;
		Error_code serve();
		Error_code serve_and_retrieve(queue_entry &x);
		Queue<queue_entry> &operator=(const Queue<queue_entry> &s);
		~Queue();
};

template <class queue_entry>
Queue<queue_entry>::Queue(const Queue<queue_entry> &s)
{
	Node *new_copy,*original_node=s.front;
	if(s.empty())front=rear=NULL;
	else
	{
		front=new_copy=new Node(original_node->item);
		while(original_node->next!=NULL)
		{
			original_node=original_node->next;
			new_copy->next=new Node(original_node->item);
			new_copy=new_copy->next;
		}
		rear=new_copy;
	}
	count=s.count;
}


template <class queue_entry>
Error_code Queue<queue_entry>::append(const queue_entry &x)
{
	Node *new_copy=new Node(x);
	if(new_copy==NULL)return overflow;
	if(!empty())
	{
		rear->next=new_copy;
		rear=rear->next;
	}
	else front=rear=new_copy;
	++count;
	return success;
}

template <class queue_entry>
Error_code Queue<queue_entry>::retrieve(queue_entry &x) const
{
	if(empty())return underflow;
	x=front->item;
	return  success;
}

template <class queue_entry>
Error_code Queue<queue_entry>::serve()
{
	if(empty())return underflow;
	Node *p=front;
	front=front->next;
	if(p==rear)
	{
		delete p;
		rear=NULL;
	}
	else delete p;
	--count;
	return  success;
}

template <class queue_entry>
Error_code Queue<queue_entry>::serve_and_retrieve(queue_entry &x)
{
	if(empty())return underflow;
	x=front->item;
	Node *p=front;
	front=front->next;
	if(p==rear)
	{
		delete p;
		rear=NULL;
	}
	else delete p;
	--count;
	return  success;
}

template <class queue_entry>
Queue<queue_entry> & Queue<queue_entry>::operator=(const Queue<queue_entry> &s)
{
	Node *new_copy,*original_node=s.front;
	if(s.empty())front=rear=NULL;
	else
	{
		front=new_copy=new Node(original_node->item);
		while(original_node->next!=NULL)
		{
			original_node=original_node->next;
			new_copy->next=new Node(original_node->item);
			new_copy=new_copy->next;
		}
		rear=new_copy;
	}
	count=s.count;
	return *this;
}

template <class queue_entry>
void Queue<queue_entry>::clear()
{	while(serve()==success); 	}

template <class queue_entry>
Queue<queue_entry>::~Queue()
{
	while(serve()==success);
}

struct Term
{
	double coefficient;
	int degree;
	Term(int deg=0,double coe=0.0)
	{
		coefficient=coe;
		degree=deg;
	}
};

class Polynomial:private Queue<Term>
{
public:
	void read();
	void print() const;
	void equals_sum(Polynomial p,Polynomial q);
	void equals_difference(Polynomial p,Polynomial q);
	void equals_product(Polynomial p,Polynomial q);
	bool equals_quotient(Polynomial p,Polynomial q);
     int degree() const;
private:
	void mult_term(Polynomial p,Term t);
};

int Polynomial::degree() const
{
	if(empty())return -1;
	Term lead;
	retrieve(lead);
	return lead.degree;
}

void Polynomial::read()
/*post:The polynomial is read from cin.*/
{clear();
 double coefficient;
 int last_exponent,exponent;
 bool first_term=true;
 cout<<"enter the coefficient and exponent for the polynomial."
	 <<"are pair per line.Exponent must be in descending order."<<endl
     <<"enter a coefficient of 0 or an exponent of 0 to terminate."<<endl;
	 do{cout<<"coefficient:"<<flush;
	    cin>>coefficient;
		if(coefficient!=0.0)
		{cout<<"exponent:"<<flush;
		   cin>>exponent;
		   if((!first_term && exponent>=last_exponent)||exponent<0)
		   {exponent=0;
		    cout<<"bad exponent:polynomial terminates without its last term."
				<<endl;
		   }
		   else {Term new_term(exponent,coefficient);
		          append(new_term);
				  first_term=false;
		   }
		   last_exponent=exponent;
		}
	 }while(coefficient!=0.0 && exponent!=0);
}

void Polynomial::print() const
{
	cout<<endl;
	Node *print_node=front;
	bool first_term=true;
	while(print_node!=NULL)
	{
		Term &print_term=print_node->item;
		if(first_term)
		{
			first_term=false;
			if(print_term.coefficient<0)cout<<"-";
		}
		else if(print_term.coefficient<0)cout<<"-";
		else cout<<"+";
		double r=(print_term.coefficient>=0)
			?print_term.coefficient:-(print_term.coefficient);
		if(r!=1)cout<<r;
		if(print_term.degree>1)cout<<"X^"<<print_term.degree;
		if(print_term.degree==1)cout<<"X";
		if(r==1&&print_term.degree==0)cout<<"1";
		print_node=print_node->next;
	}
	if(first_term)cout<<"0";
	cout<<endl<<endl;
}

void Polynomial::equals_sum(Polynomial p,Polynomial q)
{
	clear();
	while(!p.empty()||!q.empty())
	{
		Term p_term,q_term;
		if(p.degree()>q.degree())
		{
			p.serve_and_retrieve(p_term);
			append(p_term);
		}
		else if(q.degree()>p.degree())
		{
			q.serve_and_retrieve(q_term);
			append(q_term);
		}
		else
		{
			p.serve_and_retrieve(p_term);
			q.serve_and_retrieve(q_term);
			if(p_term.coefficient+q_term.coefficient!=0.0)
			{
				Term answer_term(p_term.degree,p_term.coefficient+q_term.coefficient);
				append(answer_term);
			}
		}
	}
}

void Polynomial::equals_difference(Polynomial p,Polynomial q)
{
	clear();
	while(!p.empty()||!q.empty())
	{
		Term p_term,q_term;
		if(p.degree()>q.degree())
		{
			p.serve_and_retrieve(p_term);
			append(p_term);
		}
		else if(q.degree()>p.degree())
		{
			q.serve_and_retrieve(q_term);
			append(q_term);
		}
		else
		{
			p.serve_and_retrieve(p_term);
			q.serve_and_retrieve(q_term);
			if(p_term.coefficient+q_term.coefficient!=0.0)
			{
				Term answer_term(p_term.degree,p_term.coefficient-q_term.coefficient);
				append(answer_term);
			}
		}
	}
}

void Polynomial::mult_term(Polynomial p,Term t)
{
	clear();
	while(!p.empty())
	{
		Term p_term;
		p.serve_and_retrieve(p_term);
		Term answer_term(p_term.degree+t.degree,p_term.coefficient*t.coefficient);
		append(answer_term);
	}
}

void Polynomial::equals_product(Polynomial p,Polynomial q)
/*post:the Polynomial object is reset as the product of the two parameters.*/
{clear();
 while(!p.empty())
 {Term p_term,q_term;
  p.serve_and_retrieve(p_term);
   append(p_term);
   while(!q.empty())
   {q.serve_and_retrieve(q_term);
     append(q_term);
	 Term answer_term(p_term.degree+q_term.degree,p_term.coefficient*q_term.coefficient);
     append(answer_term);
		 }
 }
}

bool Polynomial::equals_quotient(Polynomial p,Polynomial q)
{
	if(q.empty())return false;
	if(!p.empty())
	{
		while(1)
		{
			Term t1,t2;
			p.retrieve(t1);
			q.retrieve(t2);
			if(t1.degree<t2.degree)
			{
				break;
			}
			else
			{
				Term t3(t1.degree-t2.degree,t1.coefficient/t2.coefficient);
				Polynomial temp;
				append(t3);
				temp.mult_term(q,t3);
				p.equals_difference(p,temp);
			}
		}
	}
	return true;
}

bool do_command(char command,Stack<Polynomial> &stored_polynomial)
{
Polynomial p,q,r,s;
switch(command)
{
	case '?':
	   p.read();
	   if(stored_polynomial.push(p)==overflow)
	   cout<<"Warning:Stack full,lost polynomial"<<endl;
	   break;
	case '=':
	   if(stored_polynomial.empty())
		cout<<"Stack empty."<<endl;
	   else
	   {
		stored_polynomial.top(p);
		p.print();
	   }
	   break;
	case '+':
	   if(stored_polynomial.empty())
		cout<<"Stack empty."<<endl;
	   else
	   {
		stored_polynomial.top(p);
		stored_polynomial.pop();
		if(stored_polynomial.empty())
		{
			cout<<"stack has just one polynomial"<<endl;
		stored_polynomial.push(p);
		}
		else
		{
			stored_polynomial.top(q);
			stored_polynomial.pop();
			r.equals_sum(q,p);
			if(stored_polynomial.push(r)==overflow)
			cout<<"Warning:Stack full,lost polynomial"<<endl;		
}
}
break;
case '-':
if(stored_polynomial.empty())
cout<<"Stack empty."<<endl;
	else
	{
		stored_polynomial.top(p);
		stored_polynomial.pop();
		if(stored_polynomial.empty())
		{
			cout<<"stack has just one polynomial"<<endl;
			stored_polynomial.push(p);
		}
		else
		{
			stored_polynomial.top(q);
			stored_polynomial.pop();
			r.equals_difference(q,p);
			if(stored_polynomial.push(r)==overflow)
			     cout<<"Warning:Stack full,lost polynomial"<<endl;
		}
	}
	break;
case '*':
	if(stored_polynomial.empty())
		cout<<"Stack empty."<<endl;
	else
	{
		stored_polynomial.top(p);
		stored_polynomial.pop();
		if(stored_polynomial.empty())
		{
			cout<<"stack has just one polynomial"<<endl;
			stored_polynomial.push(p);
		}
		else
		{
			stored_polynomial.top(q);
			stored_polynomial.pop();
			r.equals_product(q,p);
			if(stored_polynomial.push(r)==overflow)
			     cout<<"Warning:Stack full,lost polynomial"<<endl;
		}
	}
	break;
case '/':
	if(stored_polynomial.empty())
		cout<<"Stack empty."<<endl;
	else
	{
		stored_polynomial.top(p);
		stored_polynomial.pop();
		if(stored_polynomial.empty())
		{
			cout<<"stack has just one polynomial"<<endl;
			stored_polynomial.push(p);
		}
		else
		{
			stored_polynomial.top(q);
			stored_polynomial.pop();
			if(!(r.equals_quotient(q,p)))
			      cout<<"Error!!!"<<endl;
			if(stored_polynomial.push(r)==overflow)
			      cout<<"Warning:Stack full,lost polynomial"<<endl;
		}
	}
	break;
case 'q':
	cout<<"calculation finished."<<endl;
	return false;
}
return true;
}

char get_command()
{
	char command;
	bool waiting=true;
	//cout<<"Select command and press<enter>:";
	while(waiting)
	{
		cout<<"Select command and press<enter>:";
		cin>>command;
		command=tolower(command);
		if(command=='%'||command=='+'||command=='-'||command=='*'
			||command=='/'||command=='q'||command=='?'
			||command=='=')waiting=false;
		char ch;
		do
		{
			cin.get(ch);
		}while(ch!='\n');
		if(waiting)cout<<"command is error.input again."<<endl;
		
	}

	return command;
}

void introduction()
{
	cout<<endl
		<<"  The volid commands are:"<<endl
		<<"  ? :Input a Polynomial"<<endl
		<<"  = :output a polynomial"<<endl
		<<"  + :sum two polynomials"<<endl
		<<"  - :different two polynomials"<<endl
		<<"  * :multiply two polynomials"<<endl
		<<"  / :quotient two polynomials"<<endl
		<<"  q :quit calculator."<<endl
		<<"Press<Enter>to continue."<<flush;
	char c;
	do
	{
		cin.get(c);
	}while(c!='\n');
}


void main()
{
cout<<"  polynomial caculate"<<endl<<endl;
introduction();
Stack <Polynomial>stored_polynomial;
while(do_command(get_command(),stored_polynomial));
}