作者supercygnus (......)
看板Programming
标题[问题]C++/多项式相加linkedlist/中序转後序求值
时间Sun Sep 16 10:59:05 2012
第一个程式码:多项式相加
#include<iostream>
using namespace std;
struct PolyNode{
float coef;
int exp;
PolyNode *link;
};
void createPolyA(PolyNode **);
void createPolyB(PolyNode **);
void listAll(PolyNode *);
PolyNode* newTerm(float,int);
PolyNode* padd(PolyNode *,PolyNode *);
int main(void){
PolyNode *head_a=NULL;
PolyNode *head_b=NULL;
createPolyA(&head_a);
createPolyB(&head_b);
cout<<"多项式A为:";
listAll(head_a);
cout<<"多项式B为:";
listAll(head_b);
PolyNode *newpoly;
newpoly=padd(head_a,head_b);
system("pause");
return 0;
}
PolyNode* padd(PolyNode* x,PolyNode* y){
PolyNode *p,*q,*head,*tail,*final;
float c;
p=x;q=y;
tail=new PolyNode;
head=tail;
while(p!=NULL&&q!=NULL){
if(p->exp==q->exp){
if((c=p->coef+q->coef)!=0){
tail->link=newTerm(c,p->exp);
tail=tail->link; }
p=p->link;
q=q->link;
}
else if(p->exp<q->exp){
tail->link=newTerm(q->coef,q->exp);
tail=tail->link;
}
else{
tail->link=newTerm(p->coef,p->exp);
tail=tail->link;
}
}
while(p!=NULL){
tail->link=newTerm(p->coef,p->exp);
tail=tail->link;
}
while(q!=NULL){
tail->link=newTerm(q->coef,q->exp);
tail=tail->link;
}
tail->link=NULL;
final=head->link;
free(head);
return final;
}
void createPolyA(PolyNode **head){
PolyNode *ptr;
ptr=new PolyNode;
*head=ptr;
ptr->coef=5;
ptr->exp=4;
ptr->link=new PolyNode;
ptr=ptr->link;
ptr->coef=3;
ptr->exp=3;
ptr->link=new PolyNode;
ptr=ptr->link;
ptr->coef=7;
ptr->exp=1;
ptr->link=new PolyNode;
ptr=ptr->link;
ptr->coef=3;
ptr->exp=0;
ptr->link=NULL;
}
void createPolyB(PolyNode **head){
PolyNode *ptr;
ptr=new PolyNode;
*head=ptr;
ptr->coef=1;
ptr->exp=5;
ptr->link=new PolyNode;
ptr=ptr->link;
ptr->coef=10;
ptr->exp=3;
ptr->link=new PolyNode;
ptr=ptr->link;
ptr->coef=4;
ptr->exp=2;
ptr->link=new PolyNode;
ptr=ptr->link;
ptr->coef=-7;
ptr->exp=1;
ptr->link=new PolyNode;
ptr=ptr->link;
ptr->coef=3;
ptr->exp=0;
ptr->link=NULL;
}
void listAll(PolyNode *ptr){
while(ptr!=NULL){
cout<<ptr->coef<<"X"<<ptr->exp<<" ";
ptr=ptr->link;
}
cout<<endl;
}
PolyNode* newTerm(float c,int e){
PolyNode *p=new PolyNode;
p->coef=c;
p->exp=e;
return p;
}
感觉没有写错,可是跑不出结果,不知道问题出在哪里 0.0 ?
第二个程式码:中序转後序求值
#include<iostream>
#define N 100
#define operator(c) ((c=='+')||(c=='-')||(c=='*')||(c=='/'))?1:0
#define operands(c) ((c)>='0' && (c)<='9')?1:0
using namespace std;
typedef struct{
int stackarray[N];
int sp;
}Stack;
int transform(char*,char*,Stack*);
void push(Stack *,int);
void pop(Stack *,int *);
int in_stack_priority(int);
int in_coming_priority(int);
int evaluate(char *,Stack *);
int cal(int,int,char);
int pop2(Stack *);
int main(void){
Stack s;
s.sp=-1;
char input[N];
char final[N];
cout<<"请输入中序运算式";
cin>>input;
transform(input,final,&s);
cout << "中序式 => " << input << " 後序式=> " <<final<<endl;
cout<<"计算出来的值 => "<<evaluate(final,&s)<<endl;
system("pause");
return 0;
}
int transform(char *infix,char *postfix,Stack *p){
int i=0,j=0;
int element;
char token;
token=infix[i];
while(token!='\0'){
if(operands(token))
postfix[j++]=token;
else if(token=='(')
push(p,token);
else if(token==')'){
while(p->sp>=0){
pop(p,&element);
if(element=='(')
break;
postfix[j++]=element;
}
}
else if(operator(token)){
while(p->sp!=-1){
element=p->stackarray[p->sp];
if((in_coming_priority(token))<=(in_stack_priority(element))){
pop(p,&element);
postfix[j++]=element;
}
else
break;
}
push(p,token);
}
i++;
token=infix[i];
}
while(p->sp!=-1){
pop(p,&element);
postfix[j++]=element;
}
postfix[j]='\0';
}
void push(Stack *p,int x){
p->sp++;
p->stackarray[p->sp]=x;
}
void pop(Stack *p,int *x){
*x=p->stackarray[p->sp];
p->sp--;
}
int in_stack_priority(int c){
char op[5]={'(','+','-','*','/'};
char prio[5]={0,1,1,2,2};
for(int i=0;i<5;i++){
if(c==op[i])
return prio[i];
}
}
int in_coming_priority(int c){
char op[5]={'(','+','-','*','/'};
char prio[5]={4,1,1,2,2};
for(int i=0;i<5;i++){
if(c==op[i])
return prio[i];
}
}
int evaluate(char *postfix,Stack *p){
char token;
int i=0;
int result;
int a,b;
token=postfix[i];
char elem1[5],elem2[5];
while(token!='\0'){
if(operands(token))
push(p,token);
else if(operator(token)) {
a=pop2(p);
b=pop2(p);
result=cal(b,a,token);
push(p,result);
}
i++;
token=postfix[i];
}
pop(p,&result);
return result;
}
int cal(int x,int y,char c){
switch(c){
case '+':
return x+y;
break;
case '-':
return x-y;
break;
case '*':
return x*y;
break;
case '/':
return x/y;
break;
}
}
void push2(Stack *p,int x){
p->sp++;
p->stackarray[p->sp]=x;
}
int pop2(Stack *p){
return p->stackarray[p->sp];
p->sp--;
}
转後序没问题,但是转後序之後求值求不出来 0.0 跑出的答案不对
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 111.253.210.88
1F：→ MOONRAKER:水晶球，显出景象！ 118.163.12.174 09/17 12:32