|
#2
2008-10-26 15:46
|

#include "iostream.h"
enum Error_code{success,underflow,overflow};
typedef Polynomial Node_entry;
typedef Node_entry Stack_entry;
typedef Term Node2_entry;
typedef Node2_entry Queue_entry;
struct Term //多项式项结点
{
int degree;
double coefficient;
Term(int exponent=0,double scalar=0);
};
Term::Term(int exponent,double scalar)
{
degree=exponent;
coefficient=scalar;
}
struct Node_1//存栈结点
{
Node_entry entry_1;
Node_1 *next;
Node_1();
Node_1(Node_entry item,Node_1 *add_on=NULL);
};
Node_1::Node_1()
{
next=NULL;
}
Node_1::Node_1(Node_entry item,Node_1 *add_on)
{
entry_1=item;
next=add_on;
}
struct Node_2//存队列结点
{
Node2_entry entry_2;
Node_2 *next;
Node_2();
Node_2(Node2_entry item,Node_2 *add_on=NULL);
};
Node_2::Node_2()
{
next=NULL;
}
Node_2::Node_2(Node2_entry item,Node_2 *add_on)
{
entry_2=item;
next=add_on;
}
//定义栈类实现类似
class Stack
{
public:
Stack(){top_node=0;}
bool empty() const;
Error_code push(const Stack_entry &item);
Error_code pop();
Error_code top(Stack_entry &item) const;
~Stack();
protected:
Node_1 *top_node;
};
bool Stack::empty() const
{
bool outcome=true;
if(top_node==NULL)
outcome=false;
return outcome;
}
Stack::~Stack()
{
while(!empty())
pop();
}
Error_code Stack::push(const Stack_entry &item)//item为多项式
{
Node_1 *new_top=new Node_1(item,top_node);//创建链表实现栈的链式存储
if(new_top==NULL)
return overflow;
top_node=new_top;
return success;
}
Error_code Stack::pop()
{
Node_1 *old_top=top_node;
if(top_node==NULL)
return underflow;
top_node=old_top->next;
delete old_top;
return success;
}
Error_code Stack::top(Stack_entry &item) const //item为一多项式
{
Error_code outcome=success;
if(top_node==NULL)
outcome=underflow;
else
item= top_node->entry_1; //写成item=*top_node;
return outcome;
}
//定义队列类
class Extended_queue
{
public:
Extended_queue();
bool empty() const;
Error_code append(const Queue_entry &item);
Error_code serve();
Error_code retrieve(Queue_entry &item)const;//取队头元素
Error_code serve_and_retrieve(Queue_entry &item);
~Extended_queue();
protected:
Node_2 *front,*rear;
};
Extended_queue::Extended_queue()
{
front=rear=NULL;
}
Extended_queue::~Extended_queue()
{
Node_2 *next;
while(front)
{
next=front->next;
delete front;
front=next;
}
}
bool Extended_queue::empty() const
{
return((front)?false:true);
}
Error_code Extended_queue::append(const Queue_entry &item2)//传来一个结构体类型变量 iterm2
{
Node_2 *new_rear=new Node_2(item2);//创建链表实现队列链式存储
if(new_rear==NULL) return overflow;
if(rear==NULL) front=rear=new_rear;//第一个多项式进队
else
{
rear->next=new_rear;
rear=new_rear;
}
return success;
}
Error_code Extended_queue::serve()
{
if(front==NULL) return underflow;
Node_2 *old_front=front;
front=old_front->next;
if(front==NULL) rear=NULL;
delete old_front;
return success;
}
Error_code Extended_queue::retrieve(Queue_entry &item)const
{
if(front==NULL) return underflow;
item=front->entry_2;
return success;
}
Error_code Extended_queue::serve_and_retrieve(Queue_entry &item)
{
if(front==NULL) return underflow;
item=front->entry_2;
Node_2 *old_front=front;
front=old_front->next;
if(front==NULL) rear=NULL;
delete old_front;
}
//把多项式类定义成队列的派生类
class Polynomial:private Extended_queue
{
public:
void read();
void print();
void equals_sum(Polynomial p,Polynomial q);
int degree() const;
void equals_difference(Polynomial p,Polynomial q);
//void equals_product(Polynomial p,Polynomial q);
//Error_code equals_quotient(Polynomial p,Polynomial q);
};
int Polynomial::degree() const
{
if(empty()) return -1;
Term lead;
retrieve(lead);//取多项式头结点
return lead.degree;
}
void Polynomial::read()
{
clear();
double coefficient;//系数
int last_exponent,exponent;
bool first_term = true;
cout<<"Enter the coefficients and exponents for the polynomial,"
<<"one pair per line.Exponents 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)//如果系数不为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
{
Node_2 *print_node=front;
bool first_term=true;
while(print_node!=Null)
{
Term &print_term=print_node->entry_2;
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==1)
cout<<"1";
print_node=print_node->next;
}
if(first_term)
cout<<"0";
cout<<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的第一项指数>多项式q第一项的指数
{
p.serve_and_retrieve(p_term);
append(p_term);
}
else
if(q.degree()>p.degree())
{
p.serve_and_retrieve(q_term);//给q_term赋值
q.append(q_term);
}
else
{
p.serve_and_retrieve(p_term);
q.serve_and_retrieve(q_term);
if(p_term.coefficient+q_term.coefficient!=0)//degree指数
{
Term answer_term(p_term.degree,p_term.coefficient+q_term.coefficient);
append(answer_term);
}
}
}
}
//获取输入命令
char get_command()
{
char command;
bool waiting = true;
cout<<"Select command and press<Enter>:";
while(waiting)
{
cin>>command;
command=tolower(command);//转为小写字母
if(command=='?'||command == '+'||
command == '-'||command == '*'||command == '/'||
command == 'q'||command=='='||command=='c'||command=='a'
||command=='r')
waiting = false;//检查错误输入
else
{
cout<<"Please enter a valid command:"<<endl
<<"[?]push to stack [=]print top"<<endl
<<"[+][-][*][/] are arithmetic operations"<<endl
<<"[Q]uit."<<endl;
}
}
return command;
}
bool do_command(char command,Stack &stored_polynomials)//引用stored_polymomials
{
Polynomial p,q,r;//定义三个多项式对象
int flag=0;//用于区分读入多项式p,q;
switch(command)
{
case '?':
p.read(flag);//读入多项式p
if(stored_polynomials.push(p)==overflow)//多项式入栈
cout<<"Warning:Stack full,lost polynomial"<<endl;
break;
case '=':
if(stored_polynomials.empty())
cout<<"Stack empty"<<endl;
else
{
stored_polynomials.top(p);
p.print();
}
break;
case '+':
if(stored_polynomials.empty())
cout<<"Stack empty"<<endl;
else
{
stored_polynomials.top(p);//取栈顶多项式
stored_polynomials.pop();
if(stored_polynomials.empty())
{
cout<<" Stack has just one polynomial"<<endl;
stored_polynomials.push(p);
}
else
{
stored_polynomials.top(q);
stored_polynomials.pop();
r.equals_sum(q,p);
if(stored_polynomials.push(r)==overflow)
cout<<"Warning:Stack full,lost polynomial"<<endl;
}
}
break;
case 'q':
cout<<"Calculation finished."<<endl;
return false;
}
return true;
}
void main()
{
Stack stored_polynomials;//定义一个存储多项式的栈对象
while(do_command(get_command(),stored_polynomials));
}
[[it] 本帖最后由 无悔大学四年 于 2008-10-26 15:38 编辑 [/it]]