Description
1. Write a C++ function named pathExiststhat determines whether or not a there’s a path from start to finish in a rectangular maze. Here is the prototype: boolpathExists(stringmaze[],intnRows,intnCols,intsr,intsc,inter,intec); //Returntrueifthereisapathfrom(sr,sc)to(er,ec) //throughthemaze;returnfalseotherwise The parameters are A rectangular maze of Xs and dots that represents the maze. Each string of the array is a row of the maze. Each ‘X’represents a wall, and each ‘.’represents a walkway.
The number of rows in the maze. The number of columns in the maze. Each string in the maze parameter must be this length. The starting coordinates in the maze: sr, sc; the row number is in the range 0 through nRows−1, and the column number is in the range 0 through nCols−1. The ending coordinates in the maze: er, ec; the row number is in the range 0 through nRows−1, and the column number is in the range 0 through nCols−1. Here is an example of a simple maze with 5 rows and 7 columns: “XXXXXXX” “X…X.X” “XXX.X.X” “X…..X” “XXXXXXX” The function must return true if in the maze as it was when the function was called, there is a path from maze[sr][sc]to maze[er][ec]that includes only walkways, no walls; otherwise it must return false. The path may turn north, east, south, and west, but not diagonally.
When the function returns, it is allowable for the maze to have been modified by the function. Your solution must use the following simple class (without any changes), which represents an (r,c) coordinate pair: classCoord { public: Coord(intrr,intcc):m_r(rr),m_c(cc){} intr()const{returnm_r;} intc()const{returnm_c;} private: intm_r; intm_c; }; https://www.coursehero.com/file/13887126/CS32-Homework-2-Winter-2016/ This study resource was shared via CourseHero.com 3/12/2016 CS32 Homework2, Winter 2016 http://web.cs.ucla.edu/classes/winter16/cs32/Homeworks/2/spec.html 2/7 (Our convention is that (0,0) is the northwest (upper left) corner, with south (down) being the increasing r direction and east (right) being the increasing c direction.)
Your implementation must use a stack data structure, specifically, a stack of Coords. You may either write your own stack class, or use the stack type from the C++ Standard Library. Here’s an example of the relevant functions in the library’s stack type: #include usingnamespacestd; intmain() { stackcoordStack; //declareastackofCoords Coorda(5,6); coordStack.push(a); //pushthecoordinate(5,6) coordStack.push(Coord(3,4));//pushthecoordinate(3,4) … Coordb=coordStack.top(); //lookattopiteminthestack coordStack.pop(); //removethetopitemfromstack if(coordStack.empty()) //Isthestackempty? cout<<“empty!”<<endl; cout<<coordStack.size()<<endl; //numofelements } Here is pseudocode for your function: Pushthestartingcoordinate(sr,sc)ontothecoordinatestackand updatemaze[sr][sc]toindicatethatthealgorithmhasencountered it(i.e.,setmaze[sr][sc]tohaveavalueotherthan’.’). Whilethestackisnotempty, { Popthetopcoordinateoffthestack.Thisgivesyouthecurrent (r,c)locationthatyouralgorithmisexploring. Ifthecurrent(r,c)coordinateisequaltotheendingcoordinate, thenwe’vesolvedthemazesoreturntrue! Checkeachplaceyoucanmovefromthecurrentcellasfollows: IfyoucanmoveNORTHandhaven’tencounteredthatcellyet, thenpushthecoordinate(r-1,c)ontothestackandupdate maze[r-1][c]toindicatethealgorithmhasencounteredit. IfyoucanmoveEASTandhaven’tencounteredthatcellyet, thenpushthecoordinate(r,c+1)ontothestackandupdate maze[r][c+1]toindicatethealgorithmhasencounteredit. IfyoucanmoveSOUTHandhaven’tencounteredthatcellyet, thenpushthecoordinate(r+1,c)ontothestackandupdate maze[r+1][c]toindicatethealgorithmhasencounteredit. IfyoucanmoveWESTandhaven’tencounteredthatcellyet, thenpushthecoordinate(r,c-1)ontothestackandupdate maze[r][c-1]toindicatethealgorithmhasencounteredit. } Therewasnosolution,soreturnfalse https://www.coursehero.com/file/13887126/CS32-Homework-2-Winter-2016/ This study resource was shared via CourseHero.com 3/12/2016 CS32 Homework2, Winter 2016 http://web.cs.ucla.edu/classes/winter16/cs32/Homeworks/2/spec.html 3/7 Here is how a client might use your function: intmain() { stringmaze[10]={ “XXXXXXXXXX”, “X……..X”, “XX.X.XXXXX”, “X..X.X…X”, “X..X…X.X”, “XXXX.XXX.X”, “X.X….XXX”, “X..XX.XX.X”, “X…X….X”, “XXXXXXXXXX” }; if(pathExists(maze,10,10,6,4,1,1)) cout<<“Solvable!”<<endl; else cout<<“Outofluck!”<<endl; } Because the focus of this homework is on practice with the data structures, we won’t demand that your function be as robust as we normally would.
In particular, your function may make the following simplifying assumptions (i.e., you do not have to check for violations): the maze array contains nRows rows (you couldn’t check for this anyway); each string in the maze is of length nCols; the maze contains only Xs and dots when passed in to the function; the top and bottom rows of the maze contain only Xs, as do the left and right columns; srand erare between 0 and nRows-1, and scand ecare between 0 and nCols-1; maze[sr][sc]and maze[er][ec]are ‘.'(i.e., not walls) (Of course, since your function is not checking for violations of these conditions, make sure you don’t pass bad values to the function when you test it.) For this part of the homework, you will turn in one file named mazestack.cppthat contains the Coord class and your stack-based pathExistsfunction. (Do not leave out the Coord class and do not put it in a separate file.) If you use the library’s stack type, your file should include the appropriate header.
2. Given the algorithm, main function, and maze shown at the end of problem 1, what are the first 12 (r,c) coordinates popped off the stack by the algorithm? For this problem, you’ll turn in either a Word document named hw.docor hw.docx, or a text file named hw.txt, that has your answer to this problem (and problem 4).
3. Now convert your pathExistsfunction to use a queue instead of a stack, making the fewest changes to achieve this. You may either write your own queue class, or use the queue type from the C++ Standard Library: #include usingnamespacestd; intmain() { queuecoordQueue; //declareaqueueofCoords Coorda(5,6); coordQueue.push(a); //enqueueitematbackofqueue coordQueue.push(Coord(3,4)); //enqueueitematbackofqueue … Coordb=coordQueue.front(); //lookatfrontitem coordQueue.pop(); //removethefrontitemfromqueue if(coordQueue.empty()) //Isthequeueempty? cout<<“empty!”<<endl; cout<<coordQueue.size()<<endl; //numofelements }
For this part of the homework, you will turn in one file named mazequeue.cppthat contains the Coord class and your queue-based pathExistsfunction. (Do not leave out the Coord class and do not put it in a separate file.) If you use the library’s queue type, your file should include the appropriate header.
4. Given the same main function and maze as are shown at the end of problem 1, what are the first 12 (r,c) coordinates popped from the queue in your queue-based algorithm? How do the two algorithms differ from each other? (Hint: how and why do they visit cells in the maze in a different order?) For this problem, you’ll turn in either a Word document named hw.docor hw.docx, or a text file named hw.txt, that has your answer to this problem (and problem 2).
5. Implement this function that evaluates an infix integer arithmetic expression that consists of the binary operators +, -, *, and /, parentheses, and operands (with blanks allowed for readability). The /operator denotes integer division (with truncation), so that the value of eight divided by five is 1, not 1.
6. Operators have their conventional precedence and associativity. Multiplication must be explicitly indicated with the *operator. The operands in the expression are single lower case letters. Along with the expression string, you will pass the function a Map with key type charand value type int. Each letter character in the expression represents the integer value in the map that is paired with that letter key. For example, if the map maps ato 3, cto 5, lto 2, and uto 11, then the expression u-c+l*awould evaluate to 12. Here is the function: intevaluate(stringinfix,constMap&values,string&postfix,int&result); //Evaluatesanintegerarithmeticexpression //Precondition:infixisaninfixintegerarithmetic // expressionconsistingofsinglelowercaseletteroperands, // parentheses,andtheoperators+,-,*,/,withembeddedblanks
//Postcondition:Ifinfixisasyntacticallyvalidinfixinteger // expressionwhoseonlyoperandsaresinglelowercaseletters // (whetherornottheyappearinthevaluesmap),thenpostfixis // settothepostfixformoftheexpression;otherwisepostfixmay // ormaynotbechanged,resultisunchanged,andthefunction // returns1. Ifinfixissyntacticallyvalidbutcontainsat // leastonelowercaseletteroperandthatdoesnotappearinthe // valuesmap,thenresultisunchangedandthefunctionreturns2. // Ifinfixissyntacticallyvalidandallitslowercaseoperand // lettersappearinthevaluesmap,thenifevaluatingthe // expression(usingforeachletterintheexpressionthevaluein // themapthatcorrespondstoit)attemptstodividebyzero,then // resultisunchangedandthefunctionreturns3;otherwise, // resultissettothevalueoftheexpressionandthefunction // returns0. Adapt the algorithms presented on pp. 205-209 of the textbook to convert the infix expression to postfix, then evaluate the postfix form of the expression.
The algorithms use stacks. Rather than implementing the stack types yourself, you must use the stackclass template from the Standard C++ library. You may not assume that the infix string passed to the function is syntactically valid; you’ll have to detect whether it is or not. For this problem, you will turn in a file named eval.cppwhose structure is probably of the form #includelinesyouneed,including”Map.h” declarationsofanyadditionalfunctionsyoumighthavewritten tohelpyouevaluateanexpression intevaluate(stringinfix,constMap&values,string&postfix,int&result) { yourexpressionevaluationcode } implementationsofanyfunctionsyoumighthavewritten tohelpyouevaluateanexpression amainroutinetotestyourfunction Use a correct implementation of Map (perhaps from the Homework 1 or Project 2 solution).
You will not turn in Map.hor Map.cpp. (We will use correct versions when we test your code.) If we take your eval.cppfile, rename your main routine (which we will never call) to something harmless, prepend the lines #include”Map.h” #include #include #include #include
#include usingnamespacestd; if necessary, and append the lines intmain() { charvars[]={‘a’,’e’,’i’,’o’,’u’,’y’,’#’}; int vals[]={ 3, -9, 6, 2, 4, 1 }; Mapm; for(intk=0;vars[k]!=’#’;k++) m.insert(vars[k],vals[k]); stringpf; intanswer; assert(evaluate(“a+e”,m,pf,answer)==0 && pf==”ae+” && answer==-6); answer=999; assert(evaluate(“”,m,pf,answer)==1 && answer==999); assert(evaluate(“a+”,m,pf,answer)==1 && answer==999); assert(evaluate(“ai”,m,pf,answer)==1 && answer==999); assert(evaluate(“ai”,m,pf,answer)==1 && answer==999); assert(evaluate(“()”,m,pf,answer)==1 && answer==999); assert(evaluate(“y(o+u)”,m,pf,answer)==1 && answer==999); assert(evaluate(“a+E”,m,pf,answer)==1 && answer==999); assert(evaluate(“(a+(i-o)”,m,pf,answer)==1 && answer==999); //unaryoperatorsnotallowed: assert(evaluate(“-a”,m,pf,answer)==1 && answer==999); assert(evaluate(“a*b”,m,pf,answer)==2 && pf==”ab*” && answer==999); assert(evaluate(“y+o*( a-u) “,m,pf,answer)==0 && pf==”yoau-*+” && answer==-1); answer=999; assert(evaluate(“o/(y-y)”,m,pf,answer)==3 && pf==”oyy-/” && answer==999); assert(evaluate(“a “,m,pf,answer)==0 && pf==”a” && answer==3); assert(evaluate(“((a))”,m,pf,answer)==0 && pf==”a” && answer==3); cout<<“Passedalltests”<<endl; } then the resulting file must compile and build successfully when Map.hand Map.cppare present, and when executed, produce no output other than Passedalltests. (Tips: In case you didn’t already know it, you can append a character cto a string sby saying s +=c. You’ll have to adapt the code from the book, since it doesn’t do any error checking. It’s possible to do the error checking as you do the infix-to-postfix conversion instead of in a separate step before that; as you go through the infix string, almost all syntax errors can be detected by noting whether it is legal for the current nonblank character to follow the nearest nonblank character before it.
By Monday, February 1, there will be a link on the class webpage that will enable you to turn in this homework. Turn in one zip file that contains your solutions to the homework problems. The zip file should contain mazestack.cpp, if you solved problem 1 mazequeue.cpp, if you solved problem 3 eval.cpp, if you solved problem 5 hw.doc, hw.docx, or hw.txt, if you solved problems 2 and/or 4 Each source file you turn in may or may not contain a main routine; we’d prefer that it doesn’t. If it does, our testing scripts will rename your main routine to something harmless.
Our scripts will append our own main routine, then compile and run the resulting source file. Therefore, to get any credit, each source file you turn in must at least compile successfully (even though it’s allowed to not link because of a missing main routine). In each source file you turn in, do not comment out your implementation; you want our test scripts to see it! (Some people do this when testing other files’ code because they put all their code in one project instead of having a separate project for each of problems 1, 3, and 5.)
