Data Structures

Computing

Quiz 6 :
Stacks

bookmark
Unbookmark

Quiz 6 :
Stacks

Program Plan: Program to test the Polynomial class developed in the "Section 6.3". Polynomial.h: Class declaration: • Create the "Polynomial" class. • Inside the class, declare the data members and an array of the polynomial in the private. o Declare the variable "degree" as integer. o Declare an array for the list of coefficients "arr" as integer. • Then declare the functions "input()", "output()", "evaluate()", "add(int n1, int n2)" and "mul(int n1, int n2)" in the public. Polynomial.cpp: Definition of " input() " operation: • User to input the degree of the polynomial and it is stored in the variable "degree". • Initialize the elements of an array. • "for loop" to getting the coefficient value from the user and it is stored in the array. Definition of " output() " operation: • "for loop" to print the polynomial expression for the corresponding degree. o "if statement" is used to check an array value and an integer "i" value to print the coefficient and degree of the polynomial. Definition of " evaluate() " operation: • Declare the variable "x" as integer. • Input the x value and the value is stored in the variable "x". • Declare the variable "sum" as integer and initialized to zero. • "for loop" to evaluate the polynomial expression. o "if statement" is used to check an array value and an integer "i" value to evaluate the polynomial expression using addition, multiplication and power operations. Definition of Addition Operation: In "add(int n1, n2)" function, the value of n1 and n2 are added and it returns the integer value. Definition of Multiplication Operation: In "mul(int n1, n2)" function, the value of n1 and n2 are multiplied and it returns the integer value. Driver.h: Main method: • Create an instance for the "Polynomial" class. • Using an instance, the input function is called by the statement "poly.input". • Using an instance, the input function is called by the statement "poly.output". • Using an instance, the input function is called by the statement "poly.evaluate". Program: Polynomial.h: / / Include required header files #include using namespace std; / / declaration of class class Polynomial { private: / / declare the variable degree as integer int degree; / / declare an array for the list of coefficients int *arr; public: / / function declaration for input operation void input(); / / function declaration for output operation void output(); / / function declaration for evaluate operation void evaluate(); / / function declaration for addition operation int add(int n1, int n2); / / function declaration for multiplication operation int mul(int n1, int n2); }; Polynomial.cpp: / / Include required header files #include #include "Polynomial.h" using namespace std; / / input operation void Polynomial::input() { / / input the degree cout "Enter degree of the polynomial:"; / / integer is stored in the variable degree cin degree; / / initializing an array arr = new int[degree + 1]; / / for loop to getting the coefficient for (int i = 0; i = degree; i++) { / / input the coefficient cout "Enter the Coefficient c" i ":"; / / value of coefficient is stored in an array cin arr[i]; } } / / output operation void Polynomial::output() { cout "The Polynomial Expression is "; / / for loop to print the expression for (int i = 0; i = degree; i++) { / * condition to check an array value is not equal to zero * / if (arr[i] != 0) { / / condition to check i is equal to zero if (i == 0) / / print the value of array which is constant cout arr[i]; / / condition to check i is equal to one else if (i == 1) / / print the value of array for coefficient of x cout arr[i] "x"; else / / else print the value of array for coefficient of x^ cout arr[i] "x^" i; / / condition to i is not equal to degree and array value is greater than zero if (i != degree arr[i + 1] 0) / / print plus symbol cout "+"; } } cout endl; } / / evaluate operation void Polynomial::evaluate() { / / declare x as integer int x; / / input the x value cout "Enter x value: "; / / integer is stored in the variable x cin x; / / declare sum as integer and initialized to zero int sum = 0; / / for loop to evaluate the expression for (int i = 0; i = degree; i++) { / * condition to check an array value is not equal to zero * / if (arr[i] != 0) { / / condition to check i is equal to zero if (i == 0) / * addition operation is called and the value is stored in sum * / sum = add(sum, arr[i]); / / condition to check i is equal to one else if (i == 1) / / multiplication and addition operation is called and the value is stored in sum sum = add(sum, mul(arr[i], x)); else / / else power, multiplication and addition operation is called and the value is stored in sum sum = add(sum, mul(arr[i], pow(x, i))); } } / / print the value for an expression cout "The value of the polynomial expression for x = " x " is " sum endl; } / / addition operation int Polynomial::add(int n1, int n2) { / / return the value after addition return n1 + n2; } / / multiplication operation int Polynomial::mul(int n1, int n2) { / / return the value after multiplication return n1 * n2; } Driver.cpp: / / Include required header files #include #include "Polynomial.h" using namespace std; / / main method int main() { / / instance is created for the class polynomial Polynomial poly; / / call the input function poly.input(); / / call the output function poly.output(); / / call the evaluate function poly.evaluate(); system("pause"); } Sample Output: Enter degree of the polynomial:4 Enter the Coefficient c0:1 Enter the Coefficient c1:3 Enter the Coefficient c2:0 Enter the Coefficient c3:-7 Enter the Coefficient c4:5 The Polynomial Expression is 1+3x-7x^3+5x^4 Enter x value: 2 The value of the polynomial expression for x = 2 is 31

Programming Plan : The Program to test the Polynomial class developed in the "Section 6.3" using menu option. Polynomial.h: Class declaration: • Create the "Polynomial" class. • Inside the class, declare the data members and an array of the polynomial in the private. o The variable "mDeg" is declared as integer. o Declare an array for the list of coefficients. • Then declare the functions "read()", "display()", "evaluate()", "addition" and "multiplication" in the public. Polynomial.cpp: Definition of " read() " operation: • User to input the degree of the polynomial and it is stored in the variable "mDeg". • "for loop" to getting the coefficient value from the user and it is stored in the array. Definition of " display() " operation: • "for loop" to print the polynomial expression for the corresponding degree. o The condition is used to check "mDeg" and an index to print the coefficient and degree of the polynomial. Definition of " evaluate() " operation: • Initialize power equal to 1 and result equal to 0 • "for loop" to evaluate the polynomial expression. o The condition is used to check "mDeg" and an index to evaluate the polynomial expression for a given x value. Definition of Addition Operation: In addition operation, conditions to check the two polynomial degrees and add the two polynomials. Then it returns the polynomial expression. Definition of Multiplication Operation: In multiplication operation, conditions to check the two polynomial degrees and multiplies the two polynomials. Then it returns the polynomial expression. Driver.h Main method: • Menu item is created for the polynomial class and display the menu items. • Declare "choice, poly, p, q" in Driver class. • "for loop" to select an items for n number of times and input the menu selection. • "switch statement" to do the operations for the selected items in the menu. Program: Polynomial.h / / Include required header files #include #ifndef POLYNOMIAL #define POLYNOMIAL / / initialize array size const int MAX_DEGREE = 100; / / declare typedef for CoefType typedef double CoefType; / / declaration of class class Polynomial { public: / / function declaration for read operation void read(istream in); / / function declaration for display operation void display(ostream out) const; / / function declaration for addition Polynomial operator+(const Polynomial poly); / / function declaration for multiplication Polynomial operator*(const Polynomial poly); / / function declaration for evaluate() CoefType evaluate(double value); private: / / declare the variable mDeg as integer int mDeg; / / declare an array for the list of coefficients CoefType mCof[MAX_DEGREE + 1]; }; / / for input istream operator (istream in, Polynomial p); / / for output ostream operator (ostream out, const Polynomial p); #endif Polynomial.cpp: / / Include required header files #include #include #include "Polynomial.h" using namespace std; / / input definition istream operator (istream in, Polynomial p) { p.read(in); return in; } / / read operation void Polynomial::read(istream in) { / / input the degree cout "Enter the degree ( = " MAX_DEGREE "): "; / / an integer is stored in the variable mDeg in mDeg; / / check the given input is greater than the array size assert(mDeg = MAX_DEGREE); / / declare the CoefType to co CoefType co; / / input the coefficients cout "Enter coefficients in ascending order:\n"; / / for loop to getting the coefficient for (int index = 0; index = mDeg; index++) { / / input is stored in co in co; / / value of coefficient is stored in an array mCof[index] = co; } } / / output definition ostream operator (ostream out, const Polynomial p) { p.display(out); return out; } / / display operation void Polynomial::display(ostream out) const { / / for loop to print the expression for (int index = 0; index mDeg; index++) / / print the value of array for coefficient of x^ out mCof[index] "x^" index " + "; out mCof[mDeg] "x^" mDeg endl; } / / evaluate operation CoefType Polynomial::evaluate(CoefType value) { / / initialize power equal to 1 CoefType power = 1, / / initialize result equal to 0 result = 0; / / for loop to evaluate the expression for (int index = 0; index = mDeg; index++) { / / evaluated answer is stored in the variable result result += mCof[index] * power; / / value is stored in power power *= value; } / / it returns the result return result; } / / Addition operation Polynomial Polynomial::operator+(const Polynomial b) { / / an instance is created for the Polynomial class Polynomial c; / / condition to check mDeg is lesser than b.mDeg if (mDeg b.mDeg) { / / assign b to c c = b; / / for loop to add two polynomials for (int i = 0; i = mDeg; i++) / / coefficients are stored in an array c.mCof[i] += mCof[i]; / / degree value is assigned c.mDeg = b.mDeg; } else { / / referring an instance c c = *this; / / for loop to add two polynomials for (int i = 0; i = b.mDeg; i++) / / coefficients are stored in an array c.mCof[i] += b.mCof[i]; / / while loop to check the condition for coefficients and degrees are equal to equal while (c.mCof[c.mDeg] == 0) / / decrement the degree c.mDeg--; } / / it return expression return c; } / / Multiplication operation Polynomial Polynomial::operator*(const Polynomial b) { / / an instance is created for the Polynomial class Polynomial c; / / two expression degrees are added and stored in c.mDeg c.mDeg = mDeg + b.mDeg; / / for loop to check the condition for degree for (int i = 0; i = c.mDeg; i++) / / assign 0 to an array c.mCof[i] = 0; / / for loop to multiply two polynomials for (int i = 0; i = mDeg; i++) for (int j = 0; j = b.mDeg; j++) / / coefficient are multiplied and stored in c.mCof[i+j] c.mCof[i + j] += mCof[i] * b.mCof[j]; / / it returns expression return c; } Driver.cpp: / / Include required header files #include using namespace std; #include "Polynomial.h" / / main method int main() { / / menu creation const char MENU[] = "0. Display this menu\n" "1. Enter a polynomial\n" "2. -- Output it\n" "3. -- Evaluate it\n" "4. Enter two polynomials\n" "5. -- Output them\n" "6. -- Add them\n" "7. -- Multiply them\n" "8. Quit.\n"; / / menu items to display cout MENU endl; / / declare the variable choice int choice; / / declare poly, p and q Polynomial poly, p, q; / / for loop to select an items for n number of times for (;;) { / / input the item selection cout "Enter menu selection: "; / / input is stored in the variable choice cin choice; / / switch statement for input or output operations for the selected menu switch (choice) { case 0: cout MENU endl; break; case 1: cin p; break; case 2: cout p endl; break; case 3: cout "Enter value for x: "; double x; cin x; cout p.evaluate(x) endl; break; case 4: cin p q; break; case 5: cout "p = " p endl "q = " q endl; break; case 6: cout "p + q = " p + q endl; break; case 7: cout "p * q = " p * q endl; break; case 8: return 0; default: cout "illegal choice\n"; } } } Sample Output: 0. Display this menu 1. Enter a polynomial 2. -- Output it 3. -- Evaluate it 4. Enter two polynomials 5. -- Output them 6. -- Add them 7. -- Multiply them 8. Quit. Enter menu selection: 1 Enter the degree ( = 100): 4 Enter coefficients in ascending order: 1 3 0 -7 5 Enter menu selection: 2 1x^0 + 3x^1 + 0x^2 + -7x^3 + 5x^4 Enter menu selection: 3 Enter value for x: 2 31 Enter menu selection: 4 Enter the degree ( = 100): 2 Enter coefficients in ascending order: 3 9 0 Enter the degree ( = 100): 2 Enter coefficients in ascending order: 6 3 7 Enter menu selection: 5 p = 3x^0 + 9x^1 + 0x^2 q = 6x^0 + 3x^1 + 7x^2 Enter menu selection: 6 p + q = 9x^0 + 12x^1 + 7x^2 Enter menu selection: 7 p * q = 18x^0 + 63x^1 + 48x^2 + 63x^3 + 0x^4

Program Plan: Program to test the "nodeCount()" function in the linked list. List.h: Class declaration: • First, define the "List" class. o Inside the "List" class, create a "Node" class in the private and define val members, default constructor and explicit value constructor. o Define the default constructor and operations such as insert(), display() are in the public part of "List" class. List.cpp: List() constructor: • Assign the variable "first" to 0 and "nSize" to 0. insert() function: • "if statement" to check the index is lesser than 0 or index is greater than nSize. o The condition is true, it displays the error message. • The variable "nSize" is incremented, new node of "datVal" is assigned to "newPtrr" and "first" is assigned to "predPtrr". • "if statement" to check index is equal to 0 for insert new node in the list. o The condition is true, assign "first" to "newPtrr of nxt" and "newPtrr" to "first". • The condition is false, "for loop" to insert a node in the list. o Assign "predPtrr of nxt" to "predPtrr", "predPtrr of nxt" to "newPtrr of nxt" and "newPtrr" to "predPtrr of nxt". display() function: • Assign the "first" to NodePointer of "ptrr". • "while loop" to check the condition and display the list. nodeCount() function: • Declare a variable "count" as integer and initialize to 0. • Assign first to pointer. • Using "while loop", nodes in a list are counted. The condition is to check pointer is not equal to zero. o The count is incremented by one while the node not having zero. o Then assign pointer of nxt to pointer. • The loop continues until the pointer becomes zero. • The function returns the count. Driver.cpp: main() function: • Create an instance for the class "List". • Insert the val items in the linked list using "insert()" function. • Count the nodes in the linked list while calling the "nodeCount()" function. Program: List.h / / include required header files #ifndef LINKEDLIST #define LINKEDLIST #include / / declare typedef typedef int ElementType; / / class declaration class List { private: / / class declaration for node class Node { public: / / declare the variables ElementType val; Node * nxt; / / Default constrctor Node() / / initializes nxt to 0 : nxt(0) { } / / Explicit-value constrctor Node(ElementType datValue) / / initializes val member to datValue and nxt to 0 : val(datValue), nxt(0) { } }; / / class Node is ended / / declare typedef typedef Node * NodePointer; public: / / default constructor List(); / / function declaration for insert() void insert(ElementType datVal, int index); / / function declaration for display() void display(ostream out) const; / / function declaration for nodeCount() int nodeCount(); private: / / declare the variable first NodePointer first; / / declare the variable nSize int nSize; }; / / List class is ended / / output definition ostream operator (ostream out, const List aList); / / input definition istream operator (istream in, List aList); #endif List.cpp: / / include required header files #include using namespace std; #include "List.h" / / Definition of the class constructor List::List() / / variable first and nSize are 0 : first(0), nSize(0) { } / / Definition of insert() void List::insert(ElementType datVal, int index) { / / condition to check index is lesser than 0 or index is greater than nSize if (index 0 || index nSize) { / / condition is true, it display the error message cerr "Illegal location to insert -- " index endl; return; } / / variable nSize is incremented nSize++; / / Node of datVal is assigned to newPtrr List::NodePointer newPtrr = new Node(datVal), / / assign first to predPtrr predPtrr = first; / / condition to check index is equal to 0 / / insert node if list is empty if (index == 0) { / / first is assigned to newPtrr of nxt newPtrr- nxt = first; / / newPtrr is assigned to first first = newPtrr; } / / condition is false else { / / for loop insert node in the list for (int i = 1; i index; i++) / / predPtrr of nxt is assigned to predPtrr predPtrr = predPtrr- nxt; / / predPtrr of nxt is assigned to newPtrr of nxt newPtrr- nxt = predPtrr- nxt; / / newPtrr is assigned to predPtrr of nxt predPtrr- nxt = newPtrr; } } / / Definition of display() void List::display(ostream out) const { / / first is assigned to ptrr List::NodePointer ptrr = first; / / while loop check the condition ptrr is not equal to 0 / / display the list while (ptrr != 0) { / / outputs the ptrr of val out ptrr- val " "; / / ptrr of nxt is assigned to ptrr ptrr = ptrr- nxt; } } / / Definition of the output operator ostream operator (ostream out, const List aList) { / / calls the operation display aList.display(out); / / returns the out return out; } / / Definition of nodeCount() int List::nodeCount() { / / initialize count equal to 0 int count = 0; / / assign first to ptrr List::NodePointer ptrr = first; / / count the nodes while (ptrr != 0) { / / count is incremented by 1 count++; / / assign ptrr of nxt to ptrr ptrr = ptrr- nxt; } return count; } Driver.cpp: / / include required header files #include using namespace std; #include "List.h" / / main function int main() { cout "\nTesting node-counting operation:\n"; / / an instance is created for the class List aList; / / inserting value to the linked list aList.insert(3, 0); aList.insert(2, 1); aList.insert(8, 2); aList.insert(5, 3); aList.insert(4, 4); / / number of nodes in the linked list is displayed cout "\nFor " aList endl "number of nodes = " aList.nodeCount() endl; } Sample Output: Testing node-counting operation: For 3 2 8 5 4 number of nodes = 5