EECS 280 Project 4: Linked List and Calculator | p4-calculatorhttps://eecs280staff.github.io/p4-calculator/ 1/11p4 calculatorEECS 280 Project 4: Linked List and CalculatorProject Due Monday, 19 Nov 2018, 8pmTable of ContentsProject RoadmapList ClassWriting unit tests for ListStack ClassPostfix (RPN) CalculatorRequirements and RestrictionsStarter CodeAppendix A: What’s in a typename?Appendix B: Project 4 Coding Practices ChecklistProject RoadmapThis is a big picture view of what you’ll need to do to complete this project. Most of the pieceslisted here also have a corresponding section later on in the spec that goes into more detail.This project will be autograded for correctness, comprehensiveness of your test cases, andprogramming style. See the style checking tutorial for the criteria and how to check your styleautomatically on CAEN.You may work alone or with a partner. Please see the syllabus for partnership rules.Download the starter codeUse the tutorial from project 1 to get your visual debugger set up. Use this wget linkhttps://eecs280staff.github.io/p4-calculator/starter-files.tar.gz .Before setting up your visual debugger, you’ll need to rename each .h.starter file to a .h file.11/6/2018 EECS 280 Project 4: Linked List and Calculator | p4-calculatorhttps://eecs280staff.github.io/p4-calculator/ 2/11$ mv List.h.starter List.h$ mv Stack.h.starter Stack.hYou’ll also need to create these new files and add function stubs.$ touch calc.cppThese are the executables you’ll use in this project:List_compile_check.exeList_public_test.exeList_tests.exeStack_public_test.execalc.exeIf you’re working in a partnership, set up version control for a team.Familiarize yourself with the code structureThe code structure is templated and object oriented, with classes representing a doubly linkedlist and a stack.Test and implement the ADTsYou are provided interfaces for the List and Stack classes. Test and implement these.List : This container class is similar to the linked list discussed in the lecture, but with a fewdifferences: it is doubly linked to allow efficient inserts and deletes anywhere in the list, and itsupports an iterator. We will also evaluate your test cases for List to see how well theyexpose bugs.Stack : You will then use your List to implement a Stack , which only allows push and popoperations from one end. This Stack class makes use of the List class, so you shouldimplement the List class first.Test and implement the postfix calculatorWrite and test a main() function that runs an interactive calculator program. You will use theStack class to implement a postfix (also known as RPN) calculator. In a postfix calculator,operators appear after their operands, rather than in between them. For example, to compute (2 +3) * 5, you would type 2 3 + 5 *11/6/2018 EECS 280 Project 4: Linked List and Calculator | p4-calculatorhttps://eecs280staff.github.io/p4-calculator/ 3/11SubmitSubmit the following files to the autograder.List.hStack.hcalc.cppList_tests.cppList ClassThe member functions you have to implement are given in List.h.starter . You should copy thatfile to List.h and then implement each member function. The main difference from the versionin lecture is that it is doubly?linked. It also allows you to create an iterator and then use the iteratorto search, insert, or delete at any position in the list. Note that this is a class template, so that itcan hold data of any type. For class templates, it is necessary to give the code for memberfunctions inside the header file (it turns out that the compiler requires that in order to instantiatethe class, given a specific type). Therefore, there will not be a List.cpp . See the lecture slideson how to add member functions in the header file for a class template.You must not change the public interface of the List class, and you must use a doubly?linkedlist (i.e., nodes chained using pointers) implementation (no arrays or vectors, etc.). The basicmember functions that List provides are in List.h.starter .You must manage memory allocation so that there are no memory leaks, etc. For example, whenadding an item, you will need to dynamically allocate the memory for a node to hold the item’svalue and the pointers to the next and previous nodes in the linked list. When removing items, youwill need to delete that previously allocated memory. The List destructor needs to ensure thatall the nodes in the linked list are deleted.To compile and run your List tests, run the following commands:$ make List_tests.exe$ ./List_tests.exeSince C++ only instantiates templates that are needed, we have included a simple program thatattempts to instantiate every member of the List template to make sure they compile. Tocompile and run the public List compilation test, run the following commands:$ make List_compile_check.exe$ ./List_compile_check.exe11/6/2018 EECS 280 Project 4: Linked List and Calculator | p4-calculatorhttps://eecs280staff.github.io/p4-calculator/ 4/11Writing unit tests for ListYou must write and submit tests for the List class. Your test cases MUST use the unit testframework, otherwise the autograder will not be able to evaluate them. Since unit tests should besmall and run quickly, you are limited to 50 TEST() items per file and your whole test suite mustfinish running in less than 5 seconds. Please bear in mind that you DO NOT need 50 unit tests tocatch all the bugs. Writing targeted test cases and avoiding redundant tests can help catch morebugs in fewer tests.How we grade your testsWe will autograde your List unit tests by running them against a number of implementations ofthose modules. If a test of yours fails for one of those implementations, that is considered a reportof a bug in that implementation.We grade your tests by the following procedure:1. We compile and run your test cases with a correct solution. Test cases that pass areconsidered valid. Tests that fail (i.e. falsely report a bug in the solution) are invalid. Theautograder gives you feedback about which test cases are valid/invalid. Since unit testsshould be small and run quickly, your whole test suite must finish running in less than 5seconds.2. We have a set of intentionally incorrect implementations that contain bugs. You get pointsfor each of these “buggy” implementations that your valid tests can catch.3. How do you catch the bugs? We compile and run all of your valid test cases against eachbuggy implementation. If any of these test cases fail (i.e. report a bug), we consider that youhave caught the bug and you earn the points for that bug.Stack ClassYou should complete the implementation of List (and test it) before working on Stack . Theskeleton code for Stack is given in Stack.h.starter . Copy Stack.h.starter to Stack.h . Youmust only use the public interface of the List class to implement the stack. The List classshould not have any friends.The core functions of the Stack class are push(item) , pop() , and top() . See the RMEs forthe description of these operations. Given the List type, the basic operations on a stack,push() and pop() , are straightforward to implement. To push, you can simply add an element atone end of the list (either end will do). To pop, you simply remove the element from the same end11/6/2018 EECS 280 Project 4: Linked List and Calculator | p4-calculatorhttps://eecs280staff.github.io/p4-calculator/ 5/11of the list. Another function is top() that simply returns the top element (as a reference toeliminate an unnecessary copy and to allow it to be modified) without modifying the stack.Though you will not be turning them in, you should write your own test cases for the Stack classsince the public tests are not comprehensive. Write them in a file called Stack_tests.cpp .To compile and run your Stack tests, run the following commands:$ make Stack_tests.exe$ ./Stack_tests.exePostfix (RPN) CalculatorYou will now use your Stack template to develop a Reverse?Polish Notation calculator incalc.cpp. The calculator must support integers and floating?point values (doubles).Important: In order for your program to produce the correct output you must set the floating?point precision of cout to 4 using the following line of code at the beginning of your main function:cout.precision(4);An RPN calculator is one in which the operators appear after their respective operands, ratherthan in between them. So, instead of computing the following:((2 3) * 4) / (?6)an RPN calculator would compute this equivalent expression (note that “n” means negate):2 3 - 4 * 6 n /RPN notation is convenient for several reasons. First, no parentheses are necessary since thecomputation is always unambiguous. Second, such a calculator is convenient to implement with astack. In the case above, when you see a number, you simply push it on the stack. When you seean operator, you pop the top two values (or just one for a unary operator), apply the operator onthem, and then push the result back on the stack. In the case above, the stack would change asfollows (top value shown first):Stack after seeing 2 : [2]Stack after seeing 3 : [ 3, 2]Stack after seeing - operator: [1]11/6/2018 EECS 280 Project 4: Linked List and Calculator | p4-calculatorhttps://eecs280staff.github.io/p4-calculator/ 6/11Stack after seeing 4 : [4, 1]Stack after seeing * operator: [4]Stack after seeing 6 : [6, 4]Stack after seeing n operator: [6, 4]Stack after seeing / operator: [0.6667]Notice that the stack only contains numbers at all times. The operators never go on the stack.The calculator program is invoked with no arguments, and it starts out with an empty stack. Ittakes its input from the standard input stream and writes its output to the standard output stream.Here are the commands your calculator must respond to and what you must do for each. Eachcommand is separated from the next one by one or more whitespace characters (includingpossibly newlines).Input Actionnumber>a number can be in any of the following forms: one or more digits [0 – 9] (i.e. 2, 42, 900) one or more digits followed by a decimal point (i.e. 2., 42., 900.) zero or more digits, followed by a decimal point, followed by one or more digits(i.e. 3.5, 2.333333, .5)Notice that all these are non?negative values. Push the value on the stack. Thefollowing are examples of things that are not valid numbers for user input: 2, 0,1,234. Only non?negative numbers are entered (to simplify your project).+pop the top two numbers off the stack, add them together, and push the resultonto the top of the stack. This requires a stack with at least two operands.Note: You should avoid making multiple calls to Stack member functions withinone statement, since the order in which operands are evaluated is undefined inC++. For example, in the expressionexpr1 + expr2it is possible for expr2 to be evaluated before expr1 . This can result inundefined behavior when expr1 and expr2 have side effects.-pop the top two numbers off the stack, subtract the first number popped fromthe second, and push the result onto the top of the stack. This requires a stackwith at least two operands.*pop the top two numbers off the stack, multiply them together, and push theresult onto the top of the stack. This requires a stack with at least two operands.11/6/2018 EECS 280 Project 4: Linked List and Calculator | p4-calculatorhttps://eecs280staff.github.io/p4-calculator/ 7/11Input Action/pop the top two numbers off the stack, divide the second value popped by thefirst number, and push the result onto the top of the stack. This requires a stackwith at least two operands.Note: Your calculator must check for division by zero. If the user attempts todivide by zero, do the following before continuing the program as normal: Put the two popped elements back on the stack in their original order Print an error message using exactly the following line of code:cout dduplicate: pop the top item off the stack and push two copies of the number ontothe top of the stack. This requires a stack with at least one operand.rreverse: pop the top two items off the stack, push the first popped item onto thetop of the stack and then the push the second item onto the top of the stack (thisjust reverses the order of the top two items on the stack). This requires a stackwith at least two operands.pprint: print the top item on the stack to standard output, followed by a newline.This requires a stack with at least one operand and leaves the stack unchanged.c clear: pop all items from the stack. This input is always valid.aprint all: print all items on the stack in one line, from top most to bottom most,each value followed by a single space. The end of the output must be followed byexactly one newline. This input is always valid and leaves the stack unchanged.For an empty stack, for example, only the newline will be printed. For a stack withtwo elements, say with stack contents being [47, 42] (top value shown first),the following will be printed:47 42 (Where corresponds to the newline character produced by endl or ).nnegate: negate the top item on the stack. This requires a stack with at least oneoperand.qquit: exit the calculator with a 0 exit value. This input is always valid. End of file(e.g., typing control?D on Linux) must also cause the calculator to exit with status0. Note: do not call exit(0) , because it will cause memory leaks!Each command is separated by whitespace.11/6/2018 EECS 280 Project 4: Linked List and Calculator | p4-calculatorhttps://eecs280staff.github.io/p4-calculator/ 8/11For simplicity, you can assume that you are given valid input in our tests. No errorchecking on inputs to the calculator is required.Implement your calculator in a file called calc.cpp .To compile your calculator, you can use:$ make calc.exeTo run your calculator interactively, you can use:$ ./calc.exeAnd then start typing the commands.Negative zeroThe C++ double format distinguishes between positive and negative zero. The following exampleillustrates negative zero:$ ./calc.exe1 n 0 * p-0Your program should not do anything special for negative zero.Requirements and RestrictionsIt is our goal for you to gain practice with good C++ code, classes, and dynamic memory.DO DO NOTModify .cpp files, List.h and Stack.h Modify other .h filesFor List and Stack, make helper memberfunctions privateModify the public interface of List orStackUse these libraries: , , , , Use other libraries11/6/2018 EECS 280 Project 4: Linked List and Calculator | p4-calculatorhttps://eecs280staff.github.io/p4-calculator/ 9/11DO DO NOT#include a library to use its functionsAssume that the compiler will find thelibrary for you (some do, some don’t)Use C++ strings Use C?stringsSend all output to standard out (A?A stdout) byusing coutSend any output to standard error (A?Astderr) by using cerrconst global variables Global or static variablesPass large structs or classes by reference Pass large structs or classes by valuePass by const reference when appropriate “I don’t think I’ll modify it …”Use Valgrind to check for memory errors “It’s probably fine…”Starter CodeYou can find the starter files on the course website.File(s) DescriptionList.h.starterSkeleton List class template header file without functionimplementations. Rename this file to List.h and then addyour function implementations.Stack.h.starterSkeleton Stack class template. Rename it to Stack.h andthen add your function implementations.List_tests.cpp Add your List unit tests to this file.List_compile_check.cpp A “does my code compile” test for List.hList_public_test.cpp A very small test case for List.h .Stack_public_test.cpp A few basic test cases for Stack.h .calc_test00.incalc_test00.out.correctcalc_test01.incalc_test01.out.correctSimple test cases for the calculator program.11/6/2018 EECS 280 Project 4: Linked List and Calculator | p4-calculatorhttps://eecs280staff.github.io/p4-calculator/ 10/11File(s) DescriptionMakefileA Makefile that has targets for compiling the published testcases and your own tests. Use$ make testto compile and run all tests.unit_test_framework.hunit_test_framework.cppThe unit test framework you must use to write your test cases.Appendix A: What’s in a typename?You saw the use of typename for declaring templates. When compiling your project, you may getthe following kind of error:If you see an error message that talks about missing ‘typename’ prior to dependent type name,simply stick in the keyword “ typename ” before the type declaration. In the instance above, itwould become:typename List::Iterator i;The same thing would apply if you declared a loop variable. For example:for (List::Iterator i; /*...*/)may need to become (if you get an error from the compiler):for (typename List::Iterator i; /*...*/)Discussion of dependent types and why we have to insert the keyword typename is beyond thescope of this course (the reason is quite subtle and deep). If you want to see some explanation,see this article:http://pages.cs.wisc.edu/~driscoll/typename.html./Stack.h:94:8: error: missing typename prior to dependent type name List::IterList::Iterator i;^~~~~~~11/6/2018 EECS 280 Project 4: Linked List and Calculator | p4-calculatorhttps://eecs280staff.github.io/p4-calculator/ 11/11Appendix B: Project 4 Coding Practices ChecklistThe following are coding practices you should adhere to when implementing the project. Adheringto these guidelines will make your life easier and improve the staff’s ability to help you in officehours. You do not have to submit this checklist.General code quality:Helper functions used if and where appropriate. Helper functions are designed to performone meaningful task, not moreLines are not too longDescriptive variable and function names (i.e. int radius instead of int x )Effective, consistent, and readable line indentationCode is not too deeply nested in loops and conditionalsMain function is reasonably shortAvoids redundant use of this keywordTest case quality:Test cases are small and test one behavior each.Test case names are descriptive, or test cases are commented with a short description ofwhat they test.Test cases are written using the unit testing framework.Project specific quality:Calculator operations (+, etc.) in main are implemented as helper functions.The big three are only implemented when required.本团队核心人员组成主要包括硅谷工程师、BAT一线工程师，精通德英语！我们主要业务范围是代做编程大作业、课程设计等等。我们的方向领域：window编程 数值算法 AI人工智能 金融统计 计量分析 大数据 网络编程 WEB编程 通讯编程 游戏编程多媒体linux 外挂编程 程序API图像处理 嵌入式/单片机 数据库编程 控制台 进程与线程 网络安全 汇编语言 硬件编程 软件设计 工程标准规等。其中代写编程、代写程序、代写留学生程序作业语言或工具包括但不限于以下范围:C/C++/C#代写Java代写IT代写Python代写辅导编程作业Matlab代写Haskell代写Processing代写Linux环境搭建Rust代写Data Structure Assginment 数据结构代写MIPS代写Machine Learning 作业 代写Oracle/SQL/PostgreSQL/Pig 数据库代写/代做/辅导Web开发、网站开发、网站作业ASP.NET网站开发Finance Insurace Statistics统计、回归、迭代Prolog代写Computer Computational method代做因为专业，所以值得信赖。如有需要，请加QQ：99515681 或邮箱：99515681@qq.com 微信：codehelp
网友评论