forked from aaronbloomfield/pdr
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathindex.html
241 lines (239 loc) · 24.5 KB
/
index.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<meta http-equiv="Content-Style-Type" content="text/css" />
<meta name="generator" content="pandoc" />
<title>PDR: Laboratory 3: Stacks</title>
<style type="text/css">code{white-space: pre;}</style>
<link rel="stylesheet" href="../../markdown.css" type="text/css" />
</head>
<body>
<h1 id="pdr-laboratory-3-stacks">PDR: Laboratory 3: Stacks</h1>
<p><a href="../index.html">Go up to the Labs table of contents page</a></p>
<h3 id="objective">Objective:</h3>
<p>To understand the workings of a stack as well as postfix notation, and to be introduced to the STL library</p>
<h3 id="background">Background:</h3>
<p>A stack is a basic data structure similar in use to a physical stack of papers. You can add to the top (push) and take from the top (pop), but you are not allowed to access the middle or bottom. A stack adheres to the <a href="http://en.wikipedia.org/wiki/LIFO_%28computing%29">LIFO</a> property.</p>
<h3 id="readings">Reading(s):</h3>
<ol style="list-style-type: decimal">
<li>Readings can be found online on the <a href="../../docs/readings.html">Readings</a> page</li>
<li>The <a href="http://en.wikipedia.org/wiki/Reverse_Polish_notation">Wikipedia article on Reverse Polish notation</a>, which is another name for postfix notation, has a good description along with a sample calculation.</li>
</ol>
<h2 id="procedure">Procedure</h2>
<h3 id="pre-lab">Pre-lab</h3>
<ol style="list-style-type: decimal">
<li>Read this entire lab document before coming to lab.</li>
<li>Go through <a href="../../tutorials/03-04-more-unix/index.html">Tutorial 3: Unix, part 1</a>, which is the introduction and sections 1-4. This tutorial is originally from the department of Electrical Engineering at the University of Surrey, and is available online <a href="http://www.ee.surrey.ac.uk/Teaching/Unix/">here</a>. You should complete the introductory part and sections 1-4. You should already be somewhat familiar with some of the materials in the first few of these tutorials, as it was in the <a href="../../tutorials/01-intro-unix/index.html">Unix tutorial from the first lab</a>. The rest of the tutorial (sections 5-8) are for next week's lab, but feel free to go through it this week, if you are interested.</li>
<li>Write up at least one question that you still have on Unix (or things you are still confused about) into unix.questions.txt.</li>
<li>Your code for the pre-lab will use the pre-existing STL <code>stack</code> class. The STL is the <a href="http://en.wikipedia.org/wiki/Standard_template_library">Standard Template Library</a>, and is a collection of useful routines analogous to the routines in Java's SDK, albeit much smaller (it contains a vector class, for example).
<ul>
<li>To use the stack STL class, just put <code>#include <stack></code> at the top of your C++ file. A standard clang++ installation should automatically find the STL stack class (this works in Linux).</li>
<li>Documentation on the STL routines can be found at <a href="http://www.sgi.com/tech/stl/">http://www.sgi.com/tech/stl/</a>; the stack documentation is <a href="http://www.sgi.com/tech/stl/stack.html">here</a>.</li>
</ul></li>
<li>Implement a simple postfix stack calculator for integers using your stack.
<ul>
<li><strong>You should use the STL stack class</strong>, rather than implement your own.</li>
<li>An online description of postfix calculators can be found <a href="http://en.wikipedia.org/wiki/Reverse_Polish_notation">on Wikipedia</a> -- you will need to implement this into postfixCalculator.h and postfixCalculator.cpp</li>
<li>Create a simple test driver, testPostfixCalc.cpp, which will be used to demonstrate your calculator (i.e., it will have the <code>main()</code> function). This file should have hard-coded values for input; handling keyboard input is the in-lab.</li>
<li>The last page of this document has some sample test cases you can use.</li>
</ul></li>
<li>Your code must compile!</li>
<li>Be sure to include: your name, the date, and the name of the file in a banner comment at the beginning of each file you submit.</li>
<li>Files to download: none</li>
<li>Files to submit: postfixCalculator.h, postfixCalculator.cpp, testPostfixCalc.cpp, unix.questions.txt</li>
</ol>
<h3 id="in-lab">In-lab</h3>
<ol style="list-style-type: decimal">
<li>Come to class with a <em>working prelab</em>.</li>
<li>Run your postfix calculator on the test sequences posted on the board by the TAs. Since your code only can handle hard-coded values, this will require a code modification and a recompilation to test each case. If your program does not calculate the correct result, use the debugger to find the errors and correct them. These modifications will be submitted to the in-lab.
<ul>
<li>Be sure you are able to explain how all parts your code work. You will be responsible for this material for the midterms and final exam.</li>
</ul></li>
<li>You need to expand your pre-lab code to handle keyboard input. See the specifications in the in-lab section for how to handle the input.</li>
<li>The files you submit should be a FULLY WORKING postfix calculator, which still uses the STL stack class.</li>
<li>Start working on the post-lab (implementing your own stack class) if you get your calculator fully working before lab ends.</li>
<li>Files to download: none (just your pre-lab source code)</li>
<li>Files to submit: postfixCalculator.h, postfixCalculator.cpp, testPostfixCalc.cpp</li>
</ol>
<h3 id="post-lab">Post-lab</h3>
<ol style="list-style-type: decimal">
<li>Implement a stack class (into files stack.h and stack.cpp). <strong>You can NOT use an STL container class for this</strong> (<code>list</code>, <code>vector</code>, <code>stack</code>, etc.) for this, but you can use the STL <code>string</code> class. You should use either your List class from the last lab (if it works), or write up new stack class based on either the lecture notes or the textbook pages on stacks. Note that your stack class can contain a LinkedList object, and a stack class method can just pass the value onto the appropriate method in the LinkedList class. You don't need to implement all possible stack methods (in particular, you can ignore the copy constructor, <code>operator=()</code>, etc.) -- just the four mentioned in the pre-lab (push(), top(), pop(), and empty()). After this lab, it is expected that you will be able to implement a stack class in C++.</li>
<li>Modify your postfix calculator to use the stack class that you have implemented.</li>
<li>Be sure to include: your name, the date, and the name of the file in a banner comment at the beginning of each file you submit. Your submission must contain the following code:
<ol style="list-style-type: decimal">
<li>Your stack code. This will likely be stack.h/cpp, and may (or may not; your choice) include all of the List.h/cpp, ListItr.h/cpp, ListNode.h/cpp files from lab 2
<ul>
<li>For your stack code, you are welcome to submit it in many files, as long as it will compile with <code>clang++ *.cpp</code>, and as long as the total number of files submitted does not exceed 11 files (you can submit 12 files total, but you need to submit a text file, described below, as well)</li>
</ul></li>
<li>A listing of your in-lab calculator code and your calculator test code: postfixCalculator.h/cpp, testPostfixCalc.cpp</li>
</ol></li>
<li>Submit, in addition to your code, a paragraph (in a file called difficulties.txt) describing what difficulties you encountered getting your code working and what you did to solve them.</li>
<li>The files you submit should be a FULLY WORKING postfix calculator. Your code must compile! Even if it doesn't work perfectly, make sure it compiles. In particular, make sure that the capitalization case of the #includes (i.e. <code>#include "Stack.h"</code> versus <code>#include "stack.h"</code>) is correct.</li>
<li>Files to download: none (just your in-lab source code)</li>
<li>Files to submit: stack.h, stack.cpp, postfixCalculator.h, postfixCalculator.cpp, testPostfixCalc.cpp, difficulties.txt - You may submit additional stack/list files as well, if you want</li>
</ol>
<hr />
<h2 id="pre-lab-1">Pre-lab</h2>
<h3 id="code-description">Code Description</h3>
<p>In this lab, you will:</p>
<ul>
<li>Implement a stack class that handles a stack of integer numbers. This stack implementation is done for the post-lab; for the pre-lab and the in-lab, you will be using a pre-existing stack class from C++'s standard template library (STL).
<ul>
<li>Documentation on the STL routines can be found at <a href="http://www.sgi.com/tech/stl/">http://www.sgi.com/tech/stl/</a>; the stack documentation is <a href="http://www.sgi.com/tech/stl/stack.html">here</a>.</li>
</ul></li>
<li>Write a program that uses this class to implement a postfix calculator. This will include the following files:
<ul>
<li>postfixCalculator.h, which is the class declaration of the postfix calculator</li>
<li>postfixCalculator.cpp, which is the implementation of the postfix calculator</li>
<li>testPostfixCalc.cpp that has a hard-coded expression (see below) and evaluates that expression.</li>
</ul></li>
</ul>
<p>The various parts of this lab develop the entire program:</p>
<ul>
<li>The pre-lab develops the calculator itself, without dealing with user input or the stack class</li>
<li>The in-lab develops the user input routines</li>
<li>The post-lab develops the stack class that your calculator uses</li>
</ul>
<p>Note that the program is fully able to be run after each lab portion.</p>
<h3 id="stacks">Stacks</h3>
<p>A stack is a container that implements the LIFO (last in, first out) property. Often it internally uses a linked list, array, vector, or a doubly-linked list to contain the elements. In general, a stack needs to implement the following interface and functionality:</p>
<ul>
<li><code>void push(int e)</code>: This adds the passed element to the top of the stack.</li>
<li><code>int top()</code>: This returns the element on the top of the stack. It does not remove that element from the top. If the stack is empty, then somehow an error must be indicated -- printing an error message and exiting is fine for reporting errors for this lab.</li>
<li><code>void pop()</code>: This removes the element on the top of the stack, but does not return it. If the stack is empty, then somehow an error must be indicated -- for this lab, you can just print out an error message and then exit.</li>
<li><code>bool empty()</code>: This tells whether there are any elements left in the stack (false) or not (true).</li>
</ul>
<p>Often, the <code>top()</code> and <code>pop()</code> functionality are joined as an <code>int pop()</code> function, but in this lab, it is beneficial to separate them.</p>
<p>For this lab, you must implement the stack so there is no maximum capacity (reminder: that implementation is in the post-lab)! For now if <code>pop()</code> or <code>top()</code> are called on an empty stack, terminate the program with the function call <code>exit(-1)</code>, which is from the <code><cstdlib></code> library.</p>
<p>For this lab, you will use a stack of <code>int</code> values.</p>
<h3 id="input">Input</h3>
<p>For this part of the lab, you will not deal with keyboard input (that's in the in-lab) -- thus, your submitted program will always compute the exact same value each time it is run. You will need to hard-code, into the <code>main()</code> method, the values to be operated on by your calculator. Make sure the test(s) in main demonstrates the functionality of all operators!</p>
<p>A sample <code>main()</code> function that might work is as follows -- this should be modified for your particular situation (i.e. how you declare your class, your method names, etc.). This <code>main()</code> function uses the first sample input given at the very end of this document.</p>
<pre><code>int main() {
PostfixCalculator p;
p.pushNum (1);
p.pushNum (2);
p.pushNum (3);
p.pushNum (4);
p.pushNum (5);
p.add();
p.add();
p.add();
p.add();
cout << "Result is: " << p.getTopValue() << endl;
return 0;
}</code></pre>
<p>Keep in mind that you can type up a few of the blocks, and comment them out with the <code>/* ... */</code> comment syntax that you are familiar with from Java -- this will allow you to easily switch between the different hard-coded input test cases.</p>
<h3 id="stack-calculator-implementation">Stack Calculator Implementation:</h3>
<p>Your calculator must implement the following arithmetic operations: ~, +, -, *, and /. The tilde (~) is the unary negation operator -- it negates the top element of the stack, and (unlike the other four operators) does not use a second number from the stack. Note that negative numbers still use a regular minus sign (i.e. '-3') -- this just involves putting the negative number on the stack. But if you want to do negation (which involves popping the top value, negating it, and pushing that new value back on the stack), then you would use the tilde. For the non-commutative operators (operators where the order of the numbers matters, such as minus and divide), the first value you pop we'll call x, the second value you pop we'll call y; the result should be <em>y-x</em> or <em>y/x</em>, NOT <em>x-y</em> (or <em>x/y</em>) -- in other words, the "lower" value in the stack minus/divided by the "higher" one in the stack).</p>
<h3 id="useful-information">Useful Information</h3>
<p>Postfix notation (also known as reverse Polish notation) involves writing the operators after the operands. Note how parentheses are unnecessary in postfix notation.</p>
<ul>
<li>Infix: ( 3 + 6 ) - ( 8 / 4 )</li>
<li>Postfix: 3 6 + 8 4 / -</li>
</ul>
<p>An online description of postfix calculators can be found <a href="http://en.wikipedia.org/wiki/Reverse_Polish_notation">on Wikipedia</a> - note that you do <strong>NOT</strong> need to print out the infix form of the postfix expression; you only need to print the final answer. See the end of this lab for example input and expected output.</p>
<p>When you start handling input (in the in-lab), you will want to store your read-in values into strings. You can use the <a href="http://www.cplusplus.com/reference/string/string/compare/">string compare()</a> method to compare them, but realize that it returns 0 if they are <em>equal</em>, and non-zero if they are not equal.</p>
<p>If you want to see some quick code for converting a string to an int, see the <code>StringToInt()</code> function at the bottom of <a href="http://faq.cprogramming.com/cgi-bin/smartfaq.cgi?answer=1046996179&id=1043284385">this page</a>. Warning: just copying that function without understanding it will only make your life more difficult.</p>
<h3 id="hints">Hints</h3>
<p>In the past, students have run into a few problems with this lab. We list them here in an effort to prevent these particular problems from being encountered again.</p>
<ul>
<li>When compiling your code, remember to compile ALL of your cpp files in the compile command: <code>clang++ postfixCalculator.cpp, testPostfixCalc.cpp</code>. Or you can use <code>clang++ *.cpp</code></li>
<li>Remember to put <code>using namespace std;</code> at the top of EACH file you write. Even if you don't use anything from the standard namespace, putting that at the top of the file will not hurt.</li>
</ul>
<hr />
<h2 id="in-lab-1">In-lab</h2>
<p>The purpose of the in-lab is first to ensure that your pre-lab code (the postfix calculator) is working properly. Then, you will need to add keyboard input to your lab. For the post-lab, you will be implementing your own stack. It will be much easier to debug if you know that your calculator code works -- then, you'll know that your bugs (if any) are in your input routines or your stack code.</p>
<p>If you finish your in-lab before the end of the lab session, start working on your post-lab.</p>
<h3 id="input-1">Input</h3>
<p>For your keyboard input, your program should read in just a single line. You should read this in using STL strings (if you are looking at building a tokenizer, then you are making it much more difficult than it need be). Once you encounter the end of a line, you can assume that there is no more input to read in. Your program should read in a single line, compute the result, and exit (i.e. don't prompt the user for more input). When processing input, you can't know before you read something if it will be an operand (a numeric value) or an operator (a character), so you must read in each space-separated part into a string variable, and analyze that.</p>
<p>All input is read from standard input (i.e. <code>cin</code>)! You should not be dealing with files for this lab. Once you read in a line, your program should exit. When we test your program, we will only be providing it with one line of input, so if your program is waiting for more, that will be a problem.</p>
<p>You need to accept both negative numbers (-5 for example), and numbers with multiple digits (34 is the number thirty-four, not the separate numbers three and four) -- and thus negative numbers with multiple digits (-34, for example). No values, nor intermediate computational results, will exceed what can be stored in an <code>int</code>.</p>
<p>We provide you with a number of input files that match the input shown at the end of this lab document. Recall that you can supply the contents of a file as input to your program (as described in the Unix tutorial):</p>
<pre><code>./a.out < addition.txt</code></pre>
<h3 id="reading-in-tokens">Reading in Tokens</h3>
<p>A token is a single 'thing' passed to the postfix calculator. It can be an operator or a number, but is always separated by spaces. Thus, it is an entire number that is passed to the calculator, and not part of a number. The following code will read in the tokens for this program.</p>
<pre><code>#include <iostream>
using namespace std;
int main() {
while(true) {
string s;
cin >> s;
if(s == "") {
break;
}
cout << s << endl;
}
return 0;
}</code></pre>
<p>For the postfix calculator, each string <code>s</code> that is read in must then be processed to determine if it's a number or an operator. The difficult part is if a minus sign is the first character of the token -- it could be a subtraction sign or the beginning of a negative number (recall that the unary negation operator is the tilde).</p>
<p>You may find it useful to use the <code>isdigit()</code> or <code>atoi()</code> functions provided in <code><cstdlib></code> in this lab. Try searching on the web for info on these routines. The <code>atoi()</code> function operates on a C-style string, which is an array of characters. You can convert a C++ string to one of these by calling the <code>c_str()</code> method of the C++ string object. More string functions can be found at <a href="http://www.sgi.com/tech/stl/">http//www.sgi.com/tech/stl/</a>.</p>
<p>The following illustrates the execution of the previous code. Recall that this program reads in strings from the keyboard and prints them back out to the screen. Let's assume we have a file <code>random-tokens.txt</code>, which contains:</p>
<pre><code>+ 2 3 isn't 2150 great??</code></pre>
<p>When run, it looks like the following:</p>
<pre><code>$ ./a.out < random-words.txt
+
2
3
isn't
2150
great??</code></pre>
<p>Note, as stated above, that this code reads in each space-delimited <em>token</em>. Another way this code can be run is by directly typing into <code>stdin</code>:</p>
<pre><code>$ ./a.out
+ 2 3 isn't 2150 great??
+
2
3
isn't
2150
great??
^D</code></pre>
<p>In the above execution, what was typed in was <code>+ 2 3 isn't 2150 great??</code> (the second line). After the end of the line (i.e., after the Enter key was pressed), the program reads in that, and prints each token on a separate line. Since there was no more into to provide, Control-D (shown as <code>^D</code>) was then pressed (the last line in that execution run). Control-D closes the stdin pipe by providing the EOF flag.</p>
<p><strong><em>NOTE:</em></strong> When hitting Control-D, you have to enter it <em>on it's own line</em>. This means that you first have to hit Enter, then Control-D.</p>
<p>Another way of accomplishing the above code to check if there is any more input is to use the <code>good()</code> method in cin (i.e., <code>cin.good()</code>):</p>
<pre><code>#include <iostream>
using namespace std;
int main() {
while (cin.good()) {
string s;
cin >> s;
cout << s << endl;
}
return 0;
}</code></pre>
<p>They are two different ways of reading from stdin. In the former case, you use control-d to close stdin, whereas in the latter case, <code>cin.good()</code> takes care of that.</p>
<h3 id="assumptions">Assumptions:</h3>
<ol style="list-style-type: decimal">
<li>Assume that the input, i.e. the postfix expression, is entered in on one line and that all numbers and operators are separated by a single space. We will only provide you with valid input.</li>
<li>You can assume that users will enter the proper number of operands/operators. In other words, if an invalid postfix expression is entered, your program can do anything (including crashing) and we won't take off points.</li>
</ol>
<h3 id="terminating-input">Terminating Input</h3>
<p>How should the program know when you are finished providing input? There are a couple of ways to do this.</p>
<ul>
<li>Only read in one line, and not accept any more input -- if you handle it this way, you will have to use the <code>getline()</code> method, but this is likely the harder way to deal with it.</li>
<li>Read in input until <code>cin.good()</code> method returns <code>false</code>; <strong>this will require entering a Control-D at the end of the provided input</strong> (i.e., enter a line of the postfix expression, hit Enter, and then hit Control-D). The input we provide during the execution will provide the Control-D at the end of said input.</li>
</ul>
<p>Either way is fine. Our test scripts will send in all the input <em>on a single line</em>, followed by the Enter key; we will also provide a Control-D if necessary. So whichever means you use to determine the end of your input is fine.</p>
<hr />
<h2 id="post-lab-1">Post-lab</h2>
<p>For the post-lab, you will be implementing your own stack. This can be code that you write yourself, or you can re-use your List code from lab 2 (make sure it works before you re-use it, though!).</p>
<p>You will also have to write up the difficulties.txt file, as described above in the lab procedure section.</p>
<p>Note that you only have to implement the four stack methods described in the pre-lab section (and the constructor, of course): <code>push()</code>, <code>pop()</code>, <code>top()</code>, and <code>empty()</code>. The other methods (copy constructor, <code>operator=()</code>, etc.) do not need to be implemented for this lab.</p>
<p>If you are using an array-based implementation, you must be able to handle when the array fills up; you can't use the <code>vector</code> class for this lab.</p>
<h3 id="submitting-the-stack-list-files">Submitting the stack / list files</h3>
<p>Depending on how you implement the stack class, you may just need the stack.h/cpp files, in addition to the three postfix calculator files (postfixCalculator.h/cpp and testPostfixCalc.cpp). Or you may need stack.h/cpp and stacknode.h/cpp in addition to the three postfix calculator files. Or you may want to include the six List/ListItr/ListNode files from lab 2 as well as stack.h/cpp and the three postfix calculator files. How you do this is up to you - as long as it works, we don't really care, provided that:</p>
<ol style="list-style-type: decimal">
<li>It compiles with <code>clang++ *.cpp</code></li>
<li>The total number of C++ files you submit is 11 or fewer (you can submit 12 files total, but you need to submit a the text file called difficulties.txt as well)</li>
</ol>
<hr />
<h2 id="test-files">Test files</h2>
<p>The following examples provide postfix expressions and their expected value.</p>
<p><a href="input/addition.txt">addition.txt</a>: <code>1 2 3 4 5 + + + +</code>; expected output: 15</p>
<p><a href="input/subtraction.txt">subtraction.txt</a>: <code>20 10 - -3 10 - - 2 -</code>; expected output: 21</p>
<p><a href="input/multiplication.txt">multiplication.txt</a>: <code>-1 -2 -5 3 * 2 -2 * * * *</code>; expected output: 120</p>
<p><a href="input/division.txt">division.txt</a>: <code>-1512 -12 -2 / / -2 / 3 /</code>; expected output: 42</p>
<p><a href="input/negation.txt">negation.txt</a>: <code>-1 ~ ~ ~</code>; expected output: 1</p>
</body>
</html>