CSc 109 Test 2 26 April 2000 >>>>>>>>>>>>>>>>>>>>>>>>>>ANSWERS<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< 1. (10 pts) Assume the algorithm discussed in class for balancing a binary tree is used to maintain the two balanced trees below so that an in order traversal of the tree lists the data in ascending order. Explain why both tree (a) and tree (b) are balanced. Draw tree (a) after 15 has been added to tree (a) with balance maintained. Draw tree (b) after 13 has been added to tree (b) with balance maintained. Draw tree (b) after 28 (instead of 13) has been added to tree (b) with balance maintained. Draw tree (b) after 19 (instead of 13 or 28) has been added to tree (b) with balance maintained. (a) 20 / 12 15 / \ 12 20 (b) 15 15 / \ 13 / \ 12 20 ----> 12 20 / / \ / \ / \ 10 17 25 10 13 17 25 / \ / \ / \ / \ 16 18 23 30 16 18 23 30 15 20 / \ 28 / \ 12 20 -----> 15 25 / / \ / \ / \ 10 17 25 12 17 23 30 / \ / \ / / \ / 16 18 23 30 10 16 18 28 15 17 / \ 19 / \ 12 20 ----> 15 20 / / \ / \ / \ 10 17 25 12 16 18 25 / \ / \ / \ / \ 16 18 23 30 10 19 23 30 2. (10 pts) Write the following expressions in postfix form, assuming the usual precedence of operations in C++ and putting blank spaces between each term. a. 2+3+4 > 5*3 && x-5 >= 0 2 3 + 4 + 5 3 * > x 5 - 0 >= && b. (2+3*4)*(5+6-7/8) 2 3 4 * + 5 6 + 7 8 / - * 3. (25 pts) I need a program to verify that a line of text begins with an expression satisfying the syntax diagrams below. I have provided the main program. You should provide the remaining functions, one for each diagram, which are designed using recursive descent. The program assumes that there are no blank characters in the expression. In the diagrams curly brackets denote circles (literals) and the square brackets denote boxes (the names of other diagrams). void main(){ char ch; cin.get(ch); if(B(ch)) cout<<"a good expression"; else cout<<"a bad expression"; } B --->{a}-->[A]-->{a}- -->| |-----> ----->{b}-->[B]----- A ----->[C]-->[C]-- -->| |--------> ----->{e}-->[B]-- C --->{c}-------- -->| |----> --->{d}-->[C]-- bool B(char &ch){ if(ch=='a'){ cin.get(ch); if(!A(ch) || ch!='a') return false; cin.get(ch); return true; } if(ch!='b') return false; cin.get(ch); return B(ch); } bool A(char &ch){ if(ch=='e'){ cin.get(ch); return B(ch); } return C(ch) && C(ch); } bool C(char &ch){ if(ch=='c'){ cin.get(ch); return true; } if(ch!='d') return false; cin.get(ch); return C(ch); } 4. (30 pts) Write a template class (both prototypes and definitions) for the class Sorter. An instance of Sorter has a function sort which has two arguments, an array of some type and an int which gives the number of entries in the array. Function sort, when called, returns with the array sorted. Below is a fragment of code which uses this template class. You may use any algorithm you wish for the sort, so long as it works. int x[]={1,7,4,5,9}; double y[]={1.7, 2.3, -9.4, 27.6} Sorter sInt; Sorter sDub; sInt.sort(x,5); sDub.sort(y,4); template class Sorter{ public: Sorter(); void sort(A t[],int n); }; template Sorter::Sorter(){} template void Sorter::sort(A t[],int n){ bool sorted; A temp; do{ sorted=true; for(int j=0; jt[j+1]){ temp=t[j]; t[j]=t[j+1]; t[j+1]=temp; sorted=false; } } }while(!sorted); } 5. (10 pts) Below is the declaration for the class Name. Modify the class by providing the additional prototype(s) and definition(s) which would be needed so that we could use the class Sorter from question 4 to sort an array of Names as they might appear in a telephone book. Below the declaration of the class I show how it would be used in conjunction with Sorter. class Name{ public: Name(); Name(char *fN,char *lN); char * getName(int n); //n==1 for first name, n==2 for last name private: char *firstName,*lastName; } Sorter sName; Name list[20]; ... ... sName.sort(list,7); bool operator>(const Name & t); //Tailored to my class Sorter bool Name::operator>(const Name & t){ if(lastName==NULL || firstName==NULL || t.lastName==NULL || t.firstName==NULL) return false; return(strcmp(lastName,t.lastName)>0 || (strcmp(lastName,t.lastName)==0 && strcmp(firstName,t.firstName)>0)); } NOTE: It is unnecessary to overload "=" in this context. 6. (15 pts) Translate the following SimPL program into Simpletron code for a Simpletron machine with 1000 memory locations. 120 let x=5 20016 130 let v=(x-2)*(2*x+3) 21012 135 print v 20012 31014 21017 20014 33012 30015 33017 21013 11013 43000 0 0 2 3 5