/****************************************************************** * Name: Chris Mooney, chris@dod.net * * Course: COS161, M-W 4:10 - 5:35 * * Project: #5 * * File Name: diy-polynomial.cpp * * * * Specification: Program that does polynomial addition using * * NO classes * * * * You can find these files at: * * - [http://chris.dod.net/src/cos161/diy-polynomial..cpp] * * * * GNU Public License Information: * * * * This program is free software; you can redistribute it and/or * * modify it under the terms of the GNU General Public License as * * published by the Free Software Foundation; either version 2, or * * (at your option) any later version. * * * * This program is distributed in the hope that it will be useful, * * but WITHOUT ANY WARRANTY; without even the implied warranty of * * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * * GNU General Public License for more details. * * * * For a copy of the GPL, write to the Free Software Foundation, * * 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. * * * * Chris Mooney ....................... UNIX Systems Administrator * * Daemons ofThe Damned ............... http://home.dod.net/ * * P.O. Box 7012 ...................... Tel: (619) 665-3845 * * Portland, ME 04112 ................. chris@dod.net * * * * My PGP Public Key Block can be found at: * * http://chris.dod.net/pgp-public-key.asc * * * * Fingerprint: E5C2 E88A CED4 02CB 9D3C 8316 1001 E946 B592 F11C * ******************************************************************/ #include /* for standard I/O */ #include /* for the str* functions */ using namespace std; /* populate global namespace */ /* NodeType struct for linked lists */ template struct NodeType { UserType1 coefficient; /* will contain a UserType1 */ UserType1 exponent; /* will contain a UserType1 */ UserType2 variable; /* will contain a UserType2 */ /* a pointer to the next element */ NodeType *next; NodeType *currentPos; }; int buffSize = 512; /* max char buffer */ /* prototype for our Init function. look ma I'm using templates */ template void Init(NodeType **list); /* prototype for our Build function */ template void Build(char *input, NodeType **list); /* prototype for our Add function */ template void Add(NodeType **sum, NodeType **poly1, NodeType **poly2); /* prototype for our PrintList function */ template void PrintList(NodeType **list); /* prototype for our LengthIs function */ template int LengthIs(NodeType ***list); /* prototype for our ResetList function */ template void ResetList(NodeType ***list); /* prototype for our GetNextItem function */ template NodeType* GetNextItem(NodeType ***list); /* prototype for our MakeEmpty function */ template void MakeEmpty(NodeType **list); /* prototype for our InsertItem function */ template void InsertItem(NodeType ***list, NodeType *tempNode); /* prototype for our DeleteItem function */ template void DeleteItem(NodeType ***list, NodeType **item); /*********************************************************************** * main() -- controlling program to add two polynomials * * * * Parameters * * void * * Returns * * int * * Precondition * * NONE * * Postcondition * * a whole lot of fun * ***********************************************************************/ int main() { /* self explanatory, input is the input string poly1 and 2 are the polynomials and sum is the result */ char *input; NodeType *polynomial_1 = NULL; NodeType *polynomial_2 = NULL; NodeType *sum = NULL; /* malloc array */ input = (char *)malloc(buffSize); if(input == NULL) { fprintf(stderr, "Heap Full\n"); exit(1); } /* get the first input string */ fgets(input, buffSize, stdin); while(input[0] != 'q') /* while the user doesn't want to quit */ { /* if this is polynomial 1 then build it */ if(input[0] == 'P' && input[1] == '1') { printf("%s", input); Build(input, &polynomial_1); } else if(input[0] == 'P' && input[1] == '2') { /* now build polynomial 2 */ printf("%s", input); Build(input, &polynomial_2); /* the part we have all been waiting for add them */ Add(&sum, &polynomial_1, &polynomial_2); /* and print the output */ PrintList(&sum); /* make sure to clean up sum when we are done */ MakeEmpty(&polynomial_1); MakeEmpty(&polynomial_2); MakeEmpty(&sum); } else { /* if the input start with anything else exit */ fprintf(stderr, "Incorrect Input\n"); return(1); } /* clean up the input char and get another */ free(input); input = NULL; /* malloc array */ input = (char *)malloc(buffSize); if(input == NULL) { fprintf(stderr, "Heap Full\n"); exit(1); } /* get the first input string */ fgets(input, buffSize, stdin); } return(0); } /*********************************************************************** * Init() -- think of this like a default constructor * * * * Parameters * * NodeType -- our list pointer by reverence * * Returns * * void * * Precondition * * NONE * * Postcondition * * list will contain space * ***********************************************************************/ template void Init(NodeType **list) { /* malloc struct */ *list = (NodeType *) malloc(sizeof(NodeType)); if(*list == NULL) { fprintf(stderr, "Heap Full\n"); exit(1); } /* malloc array */ (*list)->variable = (char *)malloc(buffSize); if((*list)->variable == NULL) { fprintf(stderr, "Heap Full\n"); exit(1); } (*list)->currentPos = NULL; (*list)->next = NULL; } /*********************************************************************** * Build() -- build our polynomials from input * * * * Parameters * * input -- our input string pointer by reverence * * NodeType -- our list pointer by reverence * * Returns * * void * * Precondition * * input contains something * * Postcondition * * list will contain our polynomial * ***********************************************************************/ template void Build(char *input, NodeType **list) { int tempInt = 0; /* to get the string from sscanf */ bool start = false; /* do we start the real parse or not */ bool exp = false; /* move onto exponent or not */ char *tempStr; /* for strtok */ NodeType *tempNode; Init(&tempNode); /* initialize tempNode */ tempStr = strtok(input, " "); /* separate strings */ while(tempStr != NULL) /* while there is still input to get */ { if(start) /* put it together yet? */ { /* if this is a number */ if(tempStr[0] == '0' || tempStr[0] == '1' || tempStr[0] == '2' || tempStr[0] == '3' || tempStr[0] == '4' || tempStr[0] == '5' || tempStr[0] == '6' || tempStr[0] == '7' || tempStr[0] == '8' || tempStr[0] == '9' || tempStr[0] == '-') { /* are we taking the exponent of the coefficient */ if(exp) { sscanf(tempStr, "%d", &tempInt); tempNode->exponent = tempInt; /* insert the new link */ InsertItem(&list, tempNode); /* stop memory leaks */ free(tempNode->variable); tempNode->variable = NULL; exp = false; /* start over */ } else { /* grab the coefficient */ sscanf(tempStr, "%d", &tempInt); tempNode->coefficient = tempInt; } } else if(strcasecmp(tempStr, "^") == 0) { exp = true; /* we are on the coefficient now */ } else if(strcasecmp(tempStr, "+") == 0 || strcasecmp(tempStr, "-") == 0 || strcasecmp(tempStr, "*") == 0 || strcasecmp(tempStr, "/") == 0) { /* do nothing */ } else { /* malloc array */ tempNode->variable = (char *)malloc(buffSize); if(tempNode->variable == NULL) { fprintf(stderr, "Heap Full\n"); exit(1); } /* what sort of variable did we get y? or x? */ strncpy(tempNode->variable, tempStr, buffSize); } } /* ready ... set ... GO */ if(strcasecmp(tempStr, "=") == 0) { start = true; } /* please sir.. can I have more */ tempStr = strtok(NULL, " "); } } /*********************************************************************** * Add() -- adds two polynomials together and puts the result into sum * * * * Parameters * * NodeType -- our sum pointer by reverence * * NodeType -- our polynomial_1 pointer by reverence * * NodeType -- our polynomial_2 pointer by reverence * * Returns * * void * * Precondition * * poly1 and poly2 contain polynomials while sum is empty * * Postcondition * * sum will contain the sum of both polynomials * ***********************************************************************/ template void Add(NodeType **sum, NodeType **poly1, NodeType **poly2) { int count1 = 1; int count2 = 1; NodeType *tempNode1; NodeType *tempNode2; NodeType *newItem; Init(&newItem); /* get the first items from out sorted lists */ ResetList(&poly1); tempNode1 = GetNextItem(&poly1); ResetList(&poly2); tempNode2 = GetNextItem(&poly2); /* loop while both lists have something in them */ while(LengthIs(&poly1) > 0 || LengthIs(&poly2) > 0) { /* if they are the same exponent */ if(tempNode1->exponent == tempNode2->exponent) { /* add and insert the new value */ newItem->exponent = tempNode1->exponent; strncpy(newItem->variable, tempNode1->variable, buffSize); newItem->coefficient = tempNode1->coefficient + tempNode2->coefficient; InsertItem(&sum, newItem); /* now delete that value */ DeleteItem(&poly1, &tempNode1); count2--; DeleteItem(&poly2, &tempNode2); count1--; /* if there is something still in the list */ if(LengthIs(&poly1) > 0) { ResetList(&poly1); tempNode1 = GetNextItem(&poly1); count2 = 1; /* reset the counter */ } else { count2 = -1; /* make it clear that the list us empty */ } /* if there is something still in the list */ if(LengthIs(&poly2) > 0) { ResetList(&poly2); tempNode2 = GetNextItem(&poly2); count1 = 1; /* reset the counter */ } else { count1 = -1; /* make it clear that the list us empty */ } } else /* if the exponents do not match */ { if(LengthIs(&poly2) > 0) { if(LengthIs(&poly2) >= count1) { tempNode2 = GetNextItem(&poly2); count1++; /* if poly1.LengthIs happens to be a longer list */ if(LengthIs(&poly1) > LengthIs(&poly2)) { tempNode1 = GetNextItem(&poly1); count2++; } } } /* clean up the leftovers */ if(LengthIs(&poly1) < count2 || LengthIs(&poly2) < count1) { /* go until both lists are empty */ while(LengthIs(&poly1) > 0 || LengthIs(&poly2) > 0) { if(LengthIs(&poly1) > 0) { ResetList(&poly1); newItem = GetNextItem(&poly1); InsertItem(&sum, newItem); DeleteItem(&poly1, &newItem); } if(LengthIs(&poly2) > 0) { ResetList(&poly2); newItem = GetNextItem(&poly2); InsertItem(&sum, newItem); DeleteItem(&poly2, &newItem); } } count1 = -1; /* be very clear that we are empty */ count2 = -1; /* be very clear that we are empty */ } } } free(newItem->variable); /* clean up variable */ newItem->variable = NULL; /* be clean */ } /*********************************************************************** * PrintList() -- this will print the list out in polynomial format * * * * Parameters * * NodeType -- our list pointer by reverence * * Returns * * void * * Precondition * * list contains a polynomial * * Postcondition * * list is printed in polynomial format * ***********************************************************************/ template void PrintList(NodeType **list) { int i; NodeType *tempNode; /* get each item and print it out */ printf("SUM = "); for(i = 2; i <= LengthIs(&list); i++) { tempNode = GetNextItem(&list); printf("%d%s^%d + ", tempNode->coefficient, tempNode->variable, tempNode->exponent); } /* and the last one */ tempNode = GetNextItem(&list); printf("%d%s^%d\n\n", tempNode->coefficient, tempNode->variable, tempNode->exponent); } /*********************************************************************** * LengthIs() -- this function returns the length of our list * * * * Parameters * * NodeType -- our list pointer by reverence * * Returns * * int -- list size * * Precondition * * none * * Postcondition * * the size of our list is returned * ***********************************************************************/ template int LengthIs(NodeType ***list) { int count = 0; NodeType *tempPtr; tempPtr = **list; /* make tempPtr list */ /* traverse list, count each node in turn (very expensive) */ while (**list != NULL) { **list = (**list)->next; /* move list along */ count++; /* list size */ } **list = tempPtr; return(count); } /*********************************************************************** * ResetList() -- this function resets the current position in list * * * * Parameters * * NodeType -- our list pointer by reverence * * Returns * * void * * Precondition * * list contains something * * Postcondition * * currentPos of list is set to NULL * ***********************************************************************/ template void ResetList(NodeType ***list) { (**list)->currentPos = NULL; } /*********************************************************************** * GetNextItem() -- gets the next item in the list pointed to by list * * * * Parameters * * NodeType -- our list pointer by reverence * * Returns * * NodeType -- a pointer to the current position * * Precondition * * list contains information * * Postcondition * * the next position is returned or we start over * ***********************************************************************/ template NodeType* GetNextItem(NodeType ***list) { if ((**list)->currentPos == NULL) /* Wrap at end of list */ { (**list)->currentPos = **list; } else { (**list)->currentPos = (**list)->currentPos->next; } return((**list)->currentPos); } /*********************************************************************** * MakeEmpty() -- clears out our list * * * * Parameters * * NodeType -- our list pointer by reverence * * Returns * * void * * Precondition * * list contains information * * Postcondition * * list nodes are deallocated * ***********************************************************************/ template void MakeEmpty(NodeType **list) { NodeType *tempPtr; /* traverse list, deallocating each node in turn*/ while (*list != NULL) { tempPtr = *list; /* make tempPtr list */ *list = (*list)->next; /* move list along */ free(tempPtr->variable); /* ouch that almost got me */ free(tempPtr); /* remove old location from heap */ tempPtr = NULL; /* again being clean about things */ } } /*********************************************************************** * InsertItem() -- insert a new node into the list * * * * Parameters * * NodeType -- our list pointer by reverence * * NodeType -- our tempNode pointer by reverence * * Returns * * void * * Precondition * * list is empty and tempNode contains input * * Postcondition * * list contains new node * ***********************************************************************/ template void InsertItem(NodeType ***list, NodeType *tempNode) { bool moreToSearch; /* pointer to node being inserted */ NodeType *newNode; /* trailing pointer */ NodeType *predLoc; /* traveling pointer */ NodeType *tempPtr; tempPtr = **list; /* temporary holder */ predLoc = NULL; /* start this with NULL */ /* is the beginning the end */ moreToSearch = (tempPtr != NULL); /* find place to insert */ while (moreToSearch) { /* if we are not there yet */ if (tempPtr->exponent < tempNode->exponent) { /* hold the last place */ predLoc = tempPtr; /* move forward */ tempPtr = tempPtr->next; /* are we at the end of the list yet */ moreToSearch = (tempPtr != NULL); } else { /* we have gone past our spot */ moreToSearch = false; } } /* Prepare node for insertion */ newNode = (NodeType *) malloc(sizeof(NodeType)); if(newNode == NULL) { fprintf(stderr, "Heap full\n"); exit(1); /* exit if true */ } /* malloc array */ newNode->variable = (char *)malloc(buffSize); if(newNode->variable == NULL) { fprintf(stderr, "Heap Full\n"); exit(1); } newNode->next = NULL; newNode->currentPos = NULL; /* put our item into the new node */ newNode->exponent = tempNode->exponent; newNode->coefficient = tempNode->coefficient; strncpy(newNode->variable, tempNode->variable, buffSize); /* If this is the first location */ if (predLoc == NULL) { /* put at start of list */ newNode->next = **list; **list = newNode; } else { /* insert between two nodes */ newNode->next = tempPtr; predLoc->next = newNode; } } /*********************************************************************** * DeleteItem() -- hunt down and remove a node form the list * * * * Parameters * * NodeType -- our list pointer by reverence * * NodeType -- our item pointer by reverence * * Returns * * void * * Precondition * * list is out list and item is the item to remove * * Postcondition * * item is removed from list * ***********************************************************************/ template void DeleteItem(NodeType ***list, NodeType **item) { NodeType *tempPtr; /* the pointer to find */ NodeType *delPtr; /* the pointer to delete */ tempPtr = **list; /* start at the beginning of list */ /* locate the node to be removed */ if ((*item)->exponent == (**list)->exponent) { delPtr = tempPtr; /* if they are equal */ **list = (**list)->next; /* readjust list */ } else /* not found yet keep moving */ { /* loop until we find the item or list ends */ while(tempPtr->next != NULL && !((*item)->exponent == (tempPtr->next)->exponent)) { tempPtr = tempPtr->next; } /* if not the end of list */ if(tempPtr->next != NULL) { delPtr = tempPtr->next; /* this is the one we want */ /* correct the list */ tempPtr->next = (tempPtr->next)->next; } else { return; /* the item to delete was not there */ } } free(delPtr); /* we shall set you free */ }