stack of linked lists

pobrien11 0 Newbie Poster

20 Years Ago

Hi,
I am completely lost on a program assignment. We are to use the stl stack adapter class. The elements of the stack are linked lists which represent polynomials. So in essense it is a stack of linked lists/polynomials. Note I'm NOT trying to make the stack itself a linked list, rather I'm trying to make the stack hold linked lists. I can get the code to work in int main(){} if I do:

#include <iostream>
#include "poly.h"
#include <stack>

using namespace std;

int main()
{

stack<poly*> st; // the stack of polynomial pointers

poly p1, p3; // create polynomial objects from the poly class

p1.getPoly(); // get the terms and create the 1st polynomial
cout << endl; // go to next line
cout << "The polynomial is: " << p1 << "\n"; 
p3 = p1.derivative(); // take the derivative  
cout << "The derivative is: " << p3 << endl;

poly* p2;
p2 = &p1;
st.push(p2);  // push the polynomial onto the stack
p2 = &p3;
st.push(p2);
p2 = st.top();
cout << *p2;
st.pop();
p2 = st.top();
cout << *p2;
st.pop();
cin.get(); // pause screen so can read the output
}

The code does not work for some reason when I declare poly* p2before calling the derivative function. I don't know why.

My problem lies in that I need to read a command sequence in from the screen and perform the commands. Simple Example: rdw, means ask for a polynomial, push onto the stack, take the derivative, pop the polynomial read in and push the derivative on, and then finally pop the derivative off the stack and write it to the screen. I tried making a function that processes the commands, i.e if it is 'r' then call a read function to create the polynomial and push it onto the stack, if it is 'w' call a write function that pops the stack and writes the polynomial. But garbage comes out when I call the write function. I attached all the files I'm using. Only the read and write functions are implemented so far for the interface. If anyone can help or tell me of someone who can, I would very much appreciate it. Thanks for reading,

Patrick

c++

poly.cpp (11.79 KB)

The attachment preview is chopped off after the first 10 KB. Please download the entire file.

#include <iostream>
#include <strstream>
#include <iomanip>
#include <cassert>
#include "poly.h"

using namespace std;

poly::poly()
{
    first = NULL;
    last = NULL;  
}

poly::poly(const poly& p)
{
    copyList(p);
}

poly::~poly()
{
    destroyList();
}

// Algorithm: If list doesn't exist, create the first node. Next if there are
// more nodes to create, look through the list, if the node to be added is
// larger than any existing node (based on exponential power), the new node goes
// to the front of the list. Otherwise find the location where the new node
// needs to go (will be either the end or someplace between the first and end
// nodes). Finally insert the node based on the location found.
void poly::createNode(const double& coefficient, const int& exponent)
{
   // create a new node, printing error if the node is not created
   Ptr p = new pnode;
   Ptr current, previous;
   
   assert(p!=NULL);
      
   p->coef = coefficient;
   p->exp = exponent; 
   p->next = NULL;
       
   // check if the list exists, i.e. that there are existing nodes.
   // if there are no nodes then point first and last to the new node
   if (first == NULL)
   {
      first = p;
      last = p;
   }   
   // nodes exist, check where to insert the new node
   else
   {
      current = first;
      bool found = false;
      
      // search through the list to find if the node goes at the beginning,
      // end or somewhere between the beginning and end nodes
      while (current != NULL && found == false)
      {
            // if the new node's exponent is larger than the current node's
            // exponent, then save the position for inserting - note this only
            // happens if the new node is larger than the first node
            if (p->exp >= current->exp)
            {
                found = true;
            }
            // the node is either at the end or in between somewhere, save the
            // position
            else
            {
                previous = current; 
                current = current->next;
            }
      }
      
      // if the new node is greater than (the exponent is larger) the first node
      // in the list, then insert the node at the beginning of the list
      if (current == first)
      {
          p->next = first;
          first = p;
      }
      // node goes either at the end, or in between
      else
      {
            previous->next = p;
            p->next = current; 
      }
   }
}

void poly:: destroyList()
{
    Ptr nodeToErase;
    
    while (first != NULL)
    {
        
        nodeToErase = first;
        first = first->next;
        delete nodeToErase;
    }
    
    last = NULL; // set to NULL, first set to NULL in while loop
}

void poly::copyList(const poly& p)
{
    Ptr copyNode, current;
    
    current = p.first;
    
    if (first != NULL) // initialize the polynomial list for copying
        destroyList(); 
    
    if (p.first == NULL)
   	{
        first = NULL;
        last = NULL;
    }
    else
    {
    	first = new pnode;
    
    	assert(first!=NULL);
    
    	// copy first term/node
    	first->coef = current->coef;
    	first->exp = current->exp;
    	first->next = NULL;
    	last = first;
    
    	current=current->next;
    
    	// copy remaining terms/nodes if there are any
    	while(current!=NULL)
    	{
       		copyNode = new pnode;
        
        	assert (copyNode!=NULL);
        
        	copyNode->coef = current->coef;
        	copyNode->exp = current->exp;
        	copyNode->next = NULL;
        
        	last->next = copyNode;
        	last = copyNode;
        
        	current = current->next;
    	}
    }
}
    

void poly::getPoly()
{
    double coefficient;
    int exponent;
    char buf[80];
            
    cout << "Enter the polynomial terms: ";
    
    cin.getline(buf, 80);    // read the input
    istrstream inp(buf,80);  // put input in buffer for error checking 
    
    inp >> coefficient;
    
    while (coefficient != 0.00)
    {
         if (coefficient != 0.00)
         {
              // check if the coefficient is in decimal format
              if (!inp.good())
				   // don't display error message, if invalid format just use
				   // the zero polynomial
                   break; 
              else
              {
                   inp >> exponent;
                   
                   // check if the exponent is an integer
                   if (!inp.good())
                      break;
                   else
                      // create the polynomial term
                      createNode(coefficient, exponent);
              }
         } 
         inp >> coefficient;
    }
}

void poly::print(ostream& os) const
{
    Ptr p = first;

    cout.setf(ios::fixed | ios::showpoint); // set the output parameters

    // check if list is empty, means the zero polynomial
    if (first == NULL)
        os << "0.000";
    else
    {
        os << setprecision(3);   // set decimal precision to 3 places
        os << p->coef;           
        if (p->coef != 0)        // if coefficient is 0, don't show x or exponent
        {
            if (p->exp > 1)      // only show exponent if it is greater than one
                os << "x^" << p->exp;
            else if (p->exp == 1)  // if exponent is power 1, then only show x   
                os << "x";
        }
        
        for (p=p->next; p!=NULL; p=p->next)
        {
            if (p->coef != 0) // if coefficient is 0, don't show the term
            {
                if (p->coef > 0)    // ignore the + if have a negative coefficient
                    os << " + ";
                else if (p->coef < 0) // add a space when writing negative numbers 
                    os << " ";    
                       
             	os << p->coef;
             	if (p->coef != 0)
             	{
                 	if (p->exp > 1)
                    	os << "x^" << p->exp;
                 	else if (p->exp == 1)
                    	os << "x";
             	} // end if
            }// end if
        }// end for
    }// end if
}

poly poly::derivative()
{
    poly polynomial;
    Ptr p = first; 
    double derivativeCoef; // the derivative of the coefficient
    int derivativeExp; // the derivative of the exponent

    // compute the derivative for the polynomial
    for (p; p!=NULL; p=p->next)
    {
        // multiply the coefficient of the polynomial by the exponent
        derivativeCoef = p->exp * p->coef;
        // decrease the exponent power by 1
        derivativeExp = p->exp - 1;
        // store the derivative of the polynomial term
        polynomial.createNode(derivativeCoef,derivativeExp);
    }
    return polynomial;
}

const poly& poly::operator=(const poly& p2)
{
    if (this != &p2)
        copyList(p2);
    return *this;
}

// Algorithm:  Go through both lists until the end of both are reached. If two 
// terms have like powers, add them together and move to the next terms in the 
// lists. If one term is greater than the other, insert the larger term and go 
// to the next term in the list with the larger term. If reach the end of one 
// list, but there are more terms left in the other list, insert all of the 
// remaining terms.
poly poly::operator+ (const poly& p2) const
{
    
    poly p3;
    Ptr ptr1, ptr2;
    double newCoef;
    
    ptr1 = first;
    ptr2 = p2.first;
    
    // go through both polynomial lists until reach the end of both. 
    while (ptr1!=NULL || ptr2!=NULL)
    {
 		// if neither poly. is the zero poly. (i.e. empty list), then compare terms. Otherwise
		// one list is empty so just copy the terms of the non-empty list
		if (ptr1!=NULL && ptr2!=NULL)
		{
       	 	// if the exponent powers of the two poly. terms are equal, add the
        	// terms together and copy to the temp. poly.
        	if (ptr1->exp == ptr2->exp)
        	{
            	newCoef = ptr1->coef + ptr2->coef;
            	p3.createNode(newCoef, ptr1->exp);
            	ptr1 = ptr1->next;
            	ptr2 = ptr2->next;
        	}
        	// if the term of the 1st poly is larger than the term of the 2nd poly.
        	// copy the 1st poly. term and go to the next term in the 1st poly.
        	else if (ptr1->exp > ptr2->exp)
        	{
            	p3.createNode(ptr1->coef, ptr1->exp);
            	ptr1=ptr1->next;
        	}
         	// if the term of the 2nd poly is larger than the term of the 1st poly.
        	// copy the 2nd poly. term and go to the next term in the 2nd poly.
        	else if (ptr2->exp > ptr1->exp)
        	{
            	p3.createNode(ptr2->coef, ptr2->exp);
            	ptr2 = ptr2->next;
        	} // end inner if
		} // end outer if
		else
		{
			// if at the end of the 2nd poly., but still terms left in 1st poly.,
        	// copy the terms from the 1st poly.
        	if (ptr1 != NULL && ptr2 == NULL)
        	{
            	while (ptr1 != NULL)
            	{
                 	p3.createNode(ptr1->coef, ptr1->exp);
                 	ptr1=ptr1->next;
            	}
        	}        
        	// if at the end of the 1st poly., but still terms left in 2nd poly.,
        	// copy the terms from the 2nd poly.
        	else if (ptr2 != NULL && ptr1 == NULL)
        	{
            	while (ptr2 != NULL)
            	{
                 	p3.createNode(ptr2->coef, ptr2->exp);
                 	ptr2 = ptr2->next;  
            	}
        	} // end inner if
		}// end outer if
	}// end while
    return p3;
}

// Algorithm: Note that the algorithm relies on the fact that the insert 
// function orders the nodes according to exponential power. Go throught the 1st
// list and multiply the 1st list terms by each of the 2nd list terms and store
// the resulting polynomial. Then go through the polynomial and add all like
// terms together. Insert fucntion makes sure the terms appear in decending
// order.
poly poly::operat

poly.h (2.41 KB)

#ifndef poly_h
#define poly_h

class poly
{
    public:
        struct pnode
        {
             double coef;   // coefficient of a term of the polynomial.
             int exp;       // exponent of a term of the polynomial.
             pnode* next;   // pointer to the next term of a polynomial in desc. 
                            // order of exponent.
        };
        
        typedef pnode* Ptr;  // define Ptr to be of type pnode pointer.
        
        poly();
        // default constructor
        
        poly(const poly& p);
        // copy constructor - uses copyList() to create a copy of a polynomial
        
        ~poly();
        // destructor - uses destroyList() to free up memory
        
        void createNode(const double& coefficient, const int& exponent);
        // Function to create a term of a polynomial. Takes a double
        // coefficient and assigns to coef, and takes an integer exponent and assigns
        // to exp. Prints an error if the node is not created. NOTE: The 
        // function orders the list, so the input of the terms does not have
        // to be in decending order, this function automatically does it. The
        // overloaded operator * makes use of this functionality.
        
        void destroyList ();
        // destroy the list/polynomial, freeing up the memory allocated
        
        void copyList(const poly& p);
        // create a copy of a polynomial/list
        
        void getPoly();
        // Function to prompt the user on the screen to enter a polynomial.
        
        void print(ostream& os) const;
        // Function to print the polynomial on screen.
        
        poly derivative();
        // Function to compute and return a polynomial's derivative.
              
        const poly& operator=(const poly& p2);
        // copy assignment operator.
        
        poly operator+(const poly& p2)const;
        // overload the addition (+) operator.
        
        poly operator*(const poly& p2)const;
        // overloads the multiplication (*) operator.
    
    private:
        Ptr first; //points to the first node/term of a polynomial.
        Ptr last; //points to the last node/term of a polynomial.
};

ostream& operator<< (ostream& os, const poly& p);
// overloads the output stream (<<) operator as a non-member function using
// the public member function print.
#endif

polyStack.cpp (0.72 KB)

#include <iostream>
#include <stack>
#include "poly.h"
#include "polyStack.h"

using namespace std;

polyStack::polyStack(){}

void polyStack::processCommSeq(const char& command)
{
	switch (command)
	{
		case 'r':   // get a polynomial from the user and create it
					read();
					break;
		
		case 'w':   // display the polynomial off the top of the stack
					write();
					break;

		default:    break;
	}
}

void polyStack::read()
{
	poly p1;
	poly* ptr;
	p1.getPoly(); // get a polynomial from the user
	ptr = &p1;    // point the pointer to the polynomial linked list
	st.push(ptr);  // push the polynomial onto the stack
}

void polyStack::write()
{
	poly* ptr;
	ptr = st.top();
	cout << *ptr;
}

polyStack.h (0.63 KB)

#ifndef polyStack_h
#define polyStack_h

#include <iostream>
#include <stack>
#include <vector>
#include "poly.h"

class polyStack {

	public:

		polyStack();
		// Basic constructor, does not set any of the private data members.

		void processCommSeq(const char& command);
		// Function to take a command inputed from the user and perform the requested task on the
		// polynomial.

		void read();
		// Function to get a polynomial from the user and store it on the stack

		void write();
		// Function to write a polynomial from the stack

	private:

		stack<poly*> st; // the stack of polynomials
};
#endif

Edited 11 Years Ago by TrustyTony because: fixed formating

1 Contributor
0 Replies
87 Views

Be the first to reply

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.