Question

can someone help me with a function going through a linked list and find alike terms. Like if i have 2x^2+2x^3+2x^3 then i want to add the like terms

Answer 1

most likely what I would suggest is finding out the element of the list, and then reading the first couple or so characters until you reach a variable like X? I'm assuming it's based on the 2x? or is the variable itself? Would x^2 + 2x^2 work?

Answer 2

my program takes many coefficients and degrees and then sorts it from lowest degree to highest degree, i want then to compare each one to another to see if they have same coefficient and if they are add the coefficients and move to the next one.
for example if I have 2x^2+x^2+5x^2+x^3+x^5 then it would print 8x^2+x^3+x^5

Answer 3

One option would be to use a regular expression (regexp).
\d+..\d+ would yield %1 %2 and %3 as 2x^2, 2x^3 and 2x^3

Answer 4

let me show you what I got

Answer 5

my struct:

struct Term {
int deg;
float coef;
Term *next;
};
typedef Term* Poly;

Answer 6

wouldn't work with that one though because there is no number in front of one of the x, would need a different regex if using that method

Answer 7

thats how i want it to compare and add

Term* p;
p=poly;
if (p==0)
cout<<"---empty list---";
while(p !=0)
if (p->coef==(p->next)->coef){
cout<<(p->deg)+((p->next)->deg)<<"x^"<<(p->coef)<<endl;
p=p->next;}
else{
cout<<p->deg<<"x"<<p->coef<<"+";
p=p->next;}

Answer 8

poly is a sorted polynomial list, (coef in reality is a deg and vice-versa)

Answer 9

I suppose another option is using the str.split option to split the terms on the operators like (+,-) and then searching for duplicates in that split, combine then and then join it all back together.

Answer 10

i kind of want to dude the way im doing

Answer 11

it adds the 2 coefficients but it doesn't go to the 3rd and 4th part of the polynomial

Answer 12

for example if i put 2x^2 + 1x^2 + 3x^2 then i get:


3x^2
4x^2
Segmentation fault

Answer 13

ok, so wouldn't it make sense that if a match is found you change p insteadd of just going on to next term like for the above.
First round: 2x^2 + 1x^2 + 3x^2 becomes
Second round: 3x^2 + 3x^2 then
Third round: 6x^2
In other words rather then simply going to next term, if there is a match, reform p and start over.

Answer 14

but then its gonna loop forever

Answer 15

not if you make it so that once it compares all terms and finds no matches it stops

Answer 16

how?

Answer 17

something like a match_found variable, if it finds a match it sets it ti True, and if not it sets False so the while loop would test for this and if false it knows it's done

Answer 18

can you give me an example using my code, because im really confused, i have been seating a lot of hours being stock on this

Answer 19

ok, gimme a few minutes

Answer 20

I think something like this pseudocode will work, not tested in real code.
ptemp=""
done=False
While done=False
Check p->coef against each other term
If no match found
ptemp=ptemp + current p
p=rest of p
if p-> next is last term
ptemp=ptemp+rest of p
done=True
else match found
p=combination of two matches and rest of string
if p-> next is last term
ptemp=ptemp+rest of p
done=True

Answer 21

ptemp should contain answer when done

Answer 22

ptemp i the new term?

Answer 23

Check would be a for loop that iterates through each term comparing current first term against each remaining term.

Answer 24

i don't get how it would stop the while loop though?

Answer 25

So basically For p->next to p last compare p to current term

Answer 26

The compare being the if statement.

Answer 27

Basically what it does is peels off non matching terms and puts them in ptemp as they are no longer needed. By the time it's done the whole thing is in ptemp.

Answer 28

The loop stops when done is true which is set if p-> next is the last term, hmm this may not be quite right .... might stop early...

Answer 29

Yeah the if p -> next is last term should check that p is second to last term as well so you know you are comparing last 2 terms otherwise it would stop after comparing first with last.

Answer 30

is check a for loop or a if else

Answer 31

Check would basically be (For p->next to p->last)

Answer 32

then the next line the if would be (if p->coef is same as current p from for loop)

Answer 33

Or not the same I guess the way I structured it in pseudo

Answer 34

So (if p->coef is not equal current p coef from for loop)

Answer 35

im even more confused now

Answer 36

hmm, maybe not quite either

Answer 37

is there an easier way? since the polynomial is already sorted

Answer 38

let me rewrite pseudo

Answer 39

the polynomial is sorted though

Answer 40

can you write something similar to my code, as I don't really get the pseudo code

Answer 41

my struct is
struct Term {
int deg;
float coef;
Term *next;
};
typedef Term* Poly;

Answer 42

this might make more sense for now, will try to write something
ptemp=""
done=False
While done=False
For p->next to p->last
If p->coef = p->coef of for loop
match_found=True
else
match_found=False
If match_found=False
ptemp=ptemp + current p
p=rest of p
if p-> next is last term
ptemp=ptemp+rest of p
done=True
else
p=combination of two matches and rest of string
if p-> next is last term
ptemp=ptemp+rest of p
done=True

Answer 43

let me give you the whole code so you can see what im doing

Answer 44

list.h

#include <iostream>
using namespace std;
#ifndef LIST_H
#define LIST_H
struct Term {
int deg;
float coef;
Term *next;
};
typedef Term* Poly;
Poly new_list();
void insert_front(Poly* ppoly,int deg, float coef);
void print_list(Poly poly);
void delete_front(Poly* ppoly);
bool is_empty(Poly poly);
Poly merge(Poly *ppoly,Poly *ppoly2);
void split_list(Poly* ppoly,Poly *ppoly2);
void mergesort(Poly* pl);
void reduce(Poly poly);
#endif

Answer 45

list.cpp


#include "list.h"
Poly new_list(){
Poly poly = 0;
return poly;
}
void insert_front(Poly* ppoly,int deg, float coef){
Term* t;
t = new Term;
t->coef=coef;
t->deg = deg;
t->next = *ppoly;
*ppoly = t;
return;
}
void print_list(Poly poly){
Term* p;
p = poly;
if(p == 0)
cout << "--- empty list ---";
while(p !=0){
cout << p->deg<<"x^"<<p->coef<<" + ";
p = p->next;
}
cout << endl;
}
void delete_front(Poly* ppoly){
Term* t;
if( !is_empty(*ppoly) ){ // list is not empty
t = (*ppoly);
*ppoly = (*ppoly)->next;
delete t;
}
}

bool is_empty(Poly poly){
return (poly == 0); //return true if list empty
}

Poly merge(Poly* ppoly, Poly* ppoly2){
Term **pp;
Poly merged, list1,list2;
merged= new_list();
list1 = *ppoly;
list2 = *ppoly2;
pp= &merged;
while(list1 != NULL && list2 != NULL){
if(list2->coef > list1->coef){
*pp = list1;
list1 = list1->next;
(*pp)->next = NULL;
}else{
*pp = list2;
list2 = list2->next;
(*pp)->next = NULL;
}
pp = &( (*pp)->next );
}
if(list1 != NULL)
*pp = list1;
if(list2 != NULL)
*pp = list2;

*ppoly = NULL;
*ppoly2 = NULL;
return merged;
void split_list(Poly* ppoly, Poly* ppoly2){
Poly l1= *ppoly;
Poly l2= *ppoly;
Poly* pp = &l1;
while( l2 != NULL){
l2 = l2->next;
if(l2 != NULL){
l2 = l2->next;
pp = &((*pp)->next);
}
}
l2 = *pp;
(*pp) = NULL;
*ppoly=l1;
*ppoly2=l2;
}

void mergesort(Poly* pl){
Poly l1 = *pl;
Poly l2 = new_list();
Poly merged = new_list();
if(l1 == NULL || l1->next == NULL)
return; //sorted or empty
split_list(&l1,&l2);
mergesort(&l1);
mergesort(&l2);
merged = merge(&l1,&l2);
*pl = merged;
}
void reduce(Poly poly){
mergesort(&poly);
print_list(poly);
int i;
cout<<"combining like terms:"<<endl;
Term* p;
p=poly;
if (p==0)
cout<<"---empty list---";
while(p !=0){
if (p->coef==(p->next)->coef){
p->deg=(p->deg)+((p->next)->deg);
cout<<p->deg<<"x^"<<(poly->deg)<<endl;
}
else{
cout<<p->deg<<"x"<<p->coef<<"+";}
}

}

Answer 46

main.cpp

#include <cstdlib>
#include "list.h"
int main(){
Poly poly=new_list();
Poly poly2=new_list();
Poly merged= new_list();
int n;
int deg;
float coef;
n=1;
while (n==1)
{
cout<<"Enter coefficient ";
cin>> coef;
cout<<"Enter degree ";
cin>>deg;
insert_front(&poly,coef,deg);
cout<<"Enter 1 to continue or 0 to break ";
cin>>n;
}
print_list(poly);
cout<<"sorted\n";
reduce(poly);

Answer 47

basically i want to reduce the polynomial if it has the alike terms