多项式计算 - 数据结构与算法

楼主

问题点数：0 回复次数：1

多项式计算

//Queue.h class Queue;

class Node{

private: Node *next; int data; int ndata;

public: Node(int d1,int n1,Node *l=NULL):data(d1),ndata(n1),next(l){}; friend class Queue;

}; class Queue{

public: Queue(); ~Queue(); void EnQue(int d,int n); void DeQue(int &d,int &n); bool IsEmpty(){return rear==front;}

void MakeEmpty(); int getlong(){return count;}

private:

Node *rear,*front; int count; };

Queue::Queue() { rear=front=NULL; count=0; }

Queue::~Queue() { MakeEmpty(); }

void Queue::EnQue(int d,int n) { Node *current=new Node(d,n,NULL);

if(rear==NULL)

rear=front=current;

else{ rear->next=current;

rear=current; } }

void Queue::DeQue(int &d,int &n) { Node *current;

assert(!IsEmpty());

current=front;

d=current->data;

n=current->ndata;

front=front->next;

delete current; }

void Queue::MakeEmpty() { Node *current;

while(front) { current=front;

front=front->next;

delete current; } } //stack.h template<typename T>class LinStack;

template<typename T>class StackNode{ private:

StackNode<T> *next;

T data; public:

StackNode(const T &item,StackNode<T> *perNext=NULL);

friend class LinStack<T>; };

template<typename T>StackNode<T>::StackNode(const T &item,StackNode<T> *perNext=NULL){ data=item; next=perNext; }

template<typename T>class LinStack{ private: StackNode<T> *top; public: LinStack(); ~LinStack(); void MakeEmpty(); void Push(const T &item); bool IsEmpty(){return top==NULL;} T pop() ; T Gettop(){ return top->data;}

void ClerStack();

}; template<typename T>LinStack<T>::LinStack(){ top=NULL; } template<typename T>LinStack<T>::~LinStack(){ MakeEmpty(); } template<typename T>void LinStack<T>::MakeEmpty(){ StackNode<T> *temp; while(top!=NULL){ temp=top; top=top->next; delete temp; } } template<typename T>void LinStack<T>::Push(const T &item){ StackNode<T> *newNode; newNode=new StackNode<T>(item,top); top=newNode; } template<typename T>T LinStack<T>::pop() {

assert(!IsEmpty());

StackNode<T> *temp; temp=top; T data=temp->data; top=top->next; delete temp; return data; } #include<iostream> #include<assert.h> #include"Queue.h" #include"stack.h" using namespace std;

typedef struct i{ int data;

int ndata; }Item;

int perence(char op) { switch(op) { case '+': case '-': return 1; case '*': case '/': return 2; default: return 0; } } void expersion(char *exp,LinStack<char> s,char *s1) { char *c=exp;

s.Push('@'); while(*c) { if(*c==' ')

c++;

else if(*c=='(') { s.Push(*c);

c++; }

else if(*c==')') { while(s.Gettop()!='(')

*s1++=s.pop();

s.pop();

c++; } else if(*c=='+'||*c=='-'||*c=='*'||*c=='/') { while(perence(*c)<perence(s.Gettop()))

*s1++=s.pop();

s.Push(*c);

c++; } else{ while(*c>='0'&&*c<='9')

*s1++=*c++; } *s1++=' '; } *s1++=' ';

char ch=s.pop();

while(ch!='@') { if(ch=='(')

exit(1); else { *s1++=ch;

*s1++=' ';

ch=s.pop(); } }

*s1='\0'; }

void calculation(char *s1,LinStack<double> sd) { double num1,num2;

char *c=s1;

double item=0.0;

while(*c) { switch(*c) { case '+': num1=sd.pop();

num2=sd.pop();

sd.Push(num2+num1);

c++;

break; case '-': num1=sd.pop();

num2=sd.pop();

sd.Push(num2-num1);

c++; break; case '*': num1=sd.pop();

num2=sd.pop();

sd.Push(num2*num1);

c++;

break; case '/': num1=sd.pop();

num2=sd.pop();

if(num2==0)

exit(1); else sd.Push(num2/num1);

c++; break; case ' ': c++; break; default: while(*c>='0'&&*c<='9') { item=item*10+*c-'0';

c++; } sd.Push(item); item=0.0;

break; } } if(!sd.IsEmpty())

cout<<"答案是:"<<sd.pop()<<endl; } void main() { Queue q;

LinStack<char> s;

LinStack<double> sd;

Item *item;

int d,n,size,i,j; char exp[255],s1[255];

long int sum,x,x1=0;

cout<<"确定多项式数组大小:"<<endl;

cin>>size;

item=new Item[size]; for(i=0;i<size;i++) { cout<<"输入系数:"<<endl; fflush(stdin); cin>>item[i].data;

cout<<"输入x的次方:"<<endl;

fflush(stdin);

cin>>item[i].ndata; }

for(i=0;i<=size;i++)

q.EnQue(item[i].data,item[i].ndata);

delete item;

cout<<"确认未知数x的值:"<<endl;

cin>>x;

x1=x;

cout<<"依照以下的数字组成中缀表达式:"<<endl; for(i=0;i<size;i++) { q.DeQue(d,n);

if(n==0) { sum=d*x;

cout<<sum<<'\t'; }

else{ for(j=0;j<n-1;j++) x*=x;

sum=d*x;

x=x1;

cout<<sum<<'\t'; }

} cout<<endl;

cout<<"输入中缀表达式:"<<endl; for(i=0;i<255;i++) { cin>>exp[i];

if(exp[i]=='=')

break; } exp[i]='\0'; expersion(exp,s,s1);

cout<<"输出后缀表达式:"<<endl;

cout<<s1<<endl;

calculation(s1,sd); } 输入格式：

例如我要计算　4x^3+2x^3+2x^2 当x＝3时的值　（^3表示3次方，^2表示平方，依此类推)

确定多项式数组大小: 3 输入系数: 4 输入x的次方: 3 输入系数: 2 输入x的次方: 3 输入系数: 2 输入x的次方: 2 确认未知数x的值: 3 依照以下的数字组成中缀表达式: 这个是先计算 4x^3 2x^3 2x^2 的值 324 162 18 输入中缀表达式: 324 - 162 + 18 =