Advanced Data Structures and Data Abstraction
Advanced Data Structures and Data Abstraction CSCI 3310
Popular in Course
Popular in ComputerScienence
This 4 page Class Notes was uploaded by Else Dooley on Sunday October 11, 2015. The Class Notes belongs to CSCI 3310 at East Carolina University taught by Ronnie Smith in Fall. Since its upload, it has received 116 views. For similar materials see /class/221318/csci-3310-east-carolina-university in ComputerScienence at East Carolina University.
Reviews for Advanced Data Structures and Data Abstraction
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 10/11/15
PROGRAMMING STANDARDS An important aspect in measuring your understanding of data structures is measuring your ability to implement and use them In general a major or minor in computer science must demonstrate the ability to successfully complete programming assignments of moderate complexity The programming assignments of this course are designed to confirm this skill as well as measure your mastery of the subject matter A wellwritten program should meet the following standards note that a supplementary description is given on pages 100104 of your text 3 4 PROPER VARIABLE DECLARATION The only variables to be declared outside of a functionmethod definition are instance variables that represent general properties of objects Otherwise use parameter passing to transmit data between functions In addition instance variables should be declared as private and define accessor and mutator functions as needed EXPLICIT INITIALIZATION OF VARIABLES Every variable should be given a value before it is used You can give a variable a value either through an assignment statement or an input statement N O UNUSED PARAMETERS Only pass needed parameters to a function N O UNUSED VARIABLES Every declared variable should have a specific purpose GOOD PROGRAMJVIIN G STYLE The goal in programming is to write clear readable programs which are as efficient as possible In a case where efficiency and clarity are at odds clarity should win out In general a program should be written so that a person who had not seen the problem before should be able to read and understand the code The following are general style guidelines for writing Java programs I Comment extensively Every program should have a comment block at the very top giving the author39s name class and section number program number date and a description of the program The program description should include a detailed description of the problem being solved a high level description of the solution algorithm and a description of the IO format error handling and program assumptions Each function should also have a comment block describing what it does This comment block should also describe the purpose of each parameter Every constant or variable declaration should be commented specifying what that memory cell represents Any long or difficult to read block of code should also be commented For example every loop and every IFTHENELSE branch should be commented as well as any other quottrickyquot pieces of code Use indentation to make the structure of the code more apparent Indentation style varies but be consistent Be sure to use at least two spaces to separate levels of indentation Always use meaningful variable names and symbolic constant names that re ect the use of the memory cell Capital letters should be used to clarify multiword identifiers such as nameOfStudent But be careful Java on UNIXsystems is case sensitive I Use functions to break up the code into meaningful easy to read chunks Try to avoid making a function longer than one page 6 TEST PLANS When you turn in a program you must also tuIn in a l or 2 page written description of the tests you used to determine the correctness of your program Your description should explain the purpose of each set of input values you used in testing your program This description will count for 5 of your grade on each program 7 EXTRA CREDIT I reserve the right to award students bonus points on any program for any work that quotgoes the extra milequot Possible examples of such work includes I Extra error handling I Extrainformative presentation of the output I Extra processing options The number of bonus points depends on the correctness and the degree of innovation and independent thinking shown To claim extra credit it should be described in detail in the header documentation at the beginning of the program headed by EXTRA CREDIT CLA VI 8 LINUX SYSTEM RULES Program Submission for each program you must submit l A written test plan submitted either on paper or electronically 2 A paper copy of your program source files the java files 3 An electronic submission of the source file from our departmental machines You will use the following command for submitting your programs submit ltassignm entinumbergt ltfile7nam egt where ltassignment7numbergt will be an integer representing which assignment it is and ltfile7namegt is the name of your source file After you type in this command and hit RETURN you should see the following message File lt le7namegt was capiedsuccessy iilly In the case where you submit a file more than once you will see a prompt asking if you want to overwrite the earlier submission You may respond with y or n as appropriate 4 In order for the above submit command to work you will need to add hameINTRAsmithr0n3310bin to your path or else prepend that text to your submit command Help Submission You may sometimes run into a problem in working on a program where you might try to get help from me when it is not my office hours To do this you should use the submit command with an assignment number of 0 Use comment lines at the top of your source le to describe the problem Be sure to put the ward HELP an the rst line In addition you should send me an email at rws csecuedu indicating you have submitted a query Another common courtesy is to send me an email saying you ve solved the problem on your own if you have not yet heard from me This keeps from wasting my time looking at a problem you ve already solved Depending on when you submit your request it may be several hours before I am able to examine it Computer Science 3310 Program 4 Your assignment is to write a program that evaluates postfix expressions The form of a postfix expression and the algorithm for evaluating them are discussed in chapter 7 of your text on pages 349351 In particular the algorithm uses a stack for storing the operands until used in carrying out a calculation For this program the operands will be upper case letters and the operators will be from the set of characters The semantics for these operators conforms to their semantics in Java Integer arithmetic will be used In order to assign values to the upper case letters the first portion of the input consists of assignments of integer values to letters Any letter not assigned a value will have the default value of 0 The second portion of the input consists of postfix expressions to evaluate Input Format The first portion of the input one or more lines consists of assignments of integer values to upper case letters The letters are in no particular order but no letter will be assigned two values An example assignment line is D45 The integer values assigned to letters will be in the range of a 32 bit integer The assignment lines always begin with the letter in column 1 of the input line You may assume that there will be one or more spaces between each token ie the ltlettergt ltasstiopgt and ltnumbergt A sentinel line of the form PART2 indicates the end of the assignment lines The second portion of the input one or more lines consists of postfix expressions An example expression line is CBCAEX Each of the input expressions will consist of only upper case letters and the four operators The expression lines begin in column 1 and contain no embedded spaces Any letter appearing in an expression but not assigned a value is assumed to have the default value of 0 You may also assume that the values of any calculations involved in evaluating an expression will all be in the range of a 32 bit integer The input is terminated by the sentinel line END Input Processing I Read from standard input Use the scanner class described on pages 4445 of your text Individually process each token of the assignment lines I Process the expressions as strings The String functions length and charAt should be very helpful Error Handling The following error checking should be performed I After the last character of an expression is processed the stack should consist of one number which is the result I When an operator is encountered there should be at least two operands on the stack If any of these errors occur a suitable error message should be printed and the rest of the input expression ignored You may use exception handling or traditional conditional logic for doing your error handling Processing should resume with the next line Error handling that causes termination of execution of the program will be severely penalized Output Format See sample test case The expression line should be echoed before the result is printed Data Structures To keep up with the assigned values of the operands use an array of 26 integers A slight complication is that the array subscripts will run from 0 to 25 while the ASCII codes associated with the upper case letters range between 65 and 90 However the following function will map an upper case letter into a number between 0 and 25 where 0 will correspond to A and 25 correspond to Z int addrchar ch returns the equivalent integer address for the letter given in ch 39A39 returns 0 39Z39 returns 25 and all other letters return their corresponding position as well public static int addrchar ch return int ch int 39A39 To hold the operands until they are used in calculations a stack will be used You can use the API Stack URL provided on course W WW page Note that it is a Java generic as discussed in class and Section 94 of the text All this means is that you have to specify the type of the stack element when you declare and initialize your stack Input Redirection I encourage you to use it Refer to Program 2 description for guidance Program Development I would encourage you to do this program in 3 phases In phase 1 make sure you can read in the assignment lines associate letters with values and look up those values when reading expression lines In phase 2 you add in the processing of legal expressions and in phase 3 you include the error handling PROGRAM GRADING This program will be worth 150 points The grade weights are as follows Correctness Basic Processing 50 Correctness Error Handling 20 Coding Style 15 Documentation 10 Test Plan 5 PROGRAM DEADLINES April 14 1100 PM Deadline for electronic submission of completed program including all documentation Submission should conform to the requirements discussed in the Programming Standards handout You will only need to send your application program which should be named PostEvaL java Use the submit command with an assignment number of 4 Submissions that do not follow the naming conventions discussed in this assignment for file names are subject to a 25 penalty SAMPLE TEST CASE PART 2 DCHX C AHDB AH END The output would be DCHXC 147 AHDB 6 AH ERROR Mssing operands for expression ignored