作者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