forked from aaronbloomfield/pdr
-
Notifications
You must be signed in to change notification settings - Fork 228
/
Copy pathindex.html
364 lines (364 loc) · 17.2 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
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
<!DOCTYPE html>
<html xmlns="http://www.w3.org/1999/xhtml" lang="" xml:lang="">
<head>
<meta charset="utf-8" />
<meta name="generator" content="pandoc" />
<meta name="viewport" content="width=device-width, initial-scale=1.0, user-scalable=yes" />
<title>PDR: Laboratory 3: Stacks</title>
<style>
code{white-space: pre-wrap;}
span.smallcaps{font-variant: small-caps;}
span.underline{text-decoration: underline;}
div.column{display: inline-block; vertical-align: top; width: 50%;}
div.hanging-indent{margin-left: 1.5em; text-indent: -1.5em;}
ul.task-list{list-style: none;}
.display.math{display: block; text-align: center; margin: 0.5rem auto;}
</style>
<link rel="stylesheet" href="../../markdown.css" />
<!--[if lt IE 9]>
<script src="//cdnjs.cloudflare.com/ajax/libs/html5shiv/3.7.3/html5shiv-printshiv.min.js"></script>
<![endif]-->
</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 C++ Standard Template Library (STL).</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="tutorial">Tutorial</h3>
<p>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 they were covered 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.</p>
<h3 id="recommended-readings">Recommended Readings</h3>
<ul>
<li>Postfix Calculation and Stacks and Queues sections on the <a
href="../../docs/readings.html">Readings</a> page</li>
</ul>
<h2 id="procedure">Procedure</h2>
<h3 id="pre-lab">Pre-lab</h3>
<ol type="1">
<li>Implement a postfix stack calculator for integers using the C++ STL
stack. For this prelab you are only required to implement addition and
subtraction</li>
<li>Create a simple program that takes in keyboard input to test your
calculator</li>
<li>Files to download: none</li>
<li>Files to submit: postfixCalculator.h, postfixCalculator.cpp,
testPostfixCalc.cpp</li>
</ol>
<h3 id="in-lab">In-lab</h3>
<ol type="1">
<li>Expand your test program to handle negative numbers, multiplication,
division, and negation</li>
<li>Ensure your postfix calculator works on all the provided test
cases</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 type="1">
<li>Implement a stack class</li>
<li>Modify your postfix calculator to use your stack rather than the STL
stack</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 - 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 library.
<ul>
<li>Documentation on the standard library routines can be found at <a
href="https://en.cppreference.com">https://en.cppreference.com</a>. The
stack class’s documentation can be found <a
href="https://en.cppreference.com/w/cpp/container/stack">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 accepts user-input (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 with only addition and
subtraction, and also deals with user input (excluding negative
numbers)</li>
<li>The in-lab adds multiplication, division, and negation to the
calculator, and also handles negative numbers from user input</li>
<li>The post-lab develops the stack class that your calculator uses</li>
</ul>
<p>Note that the program should be able to fully 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, as that is what the STL stack does.</p>
<p>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="postfix-notation">Postfix Notation</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>.</p>
<h3 id="stack-calculator-implementation">Stack Calculator
Implementation</h3>
<p>We will be using the C++ STL stack to implement our postfix
calculator. The stack class’s documentation can be found <a
href="https://en.cppreference.com/w/cpp/container/stack">here</a>.</p>
<p>Your calculator must implement the following arithmetic
operations:</p>
<ul>
<li><code>+</code>: addition (prelab)</li>
<li><code>-</code>: subtraction (prelab)</li>
<li><code>*</code>: multiplication (inlab)</li>
<li><code>/</code>: division (inlab)</li>
<li><code>~</code>: unary negation (inlab)</li>
</ul>
<p>Notes:</p>
<ul>
<li>We use the tilde (~) as the unary negation operator – this negates
the top element of the stack, and (unlike the other four operators) does
not use a second number from the stack. Do not confuse this operator
with the tilde operator in C++, which performs bitwise negation.
Negative numbers still use a regular minus sign (i.e. ‘-3’) and just
pushes 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.</li>
<li>Each binary operation follows the format <code>left_operand
right_operand operator</code>. For example, <code>1 2 -</code>
translates to <code>1 - 2</code>.</li>
</ul>
<h3 id="input">Input</h3>
<p>For your keyboard input, your program should read in a single line of
space-delimited tokens from standard input. You should read this in
using <code>string</code>s (if you are looking at building a tokenizer,
then you are making it much more difficult than it need be). 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 before parsing
it. 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 via input redirection (as
described in the Unix tutorial):</p>
<pre><code>./a.out < addition.txt</code></pre>
<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>Continuously read in input with <code>cin</code>. <strong>This will
require entering a Control-D at the end of the provided input</strong>
(i.e., enter 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>
<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>
</ul>
<p>As mentioned in the Unix tutorial, Control-D stands for “end of
file”, which lets <code>cin</code> know that there is no more input to
read.</p>
<p><strong><em>NOTE:</em></strong> When hitting Control-D, you have to
enter it <em>on its own line</em>. This means that you first have to hit
Enter, then Control-D.</p>
<h3 id="sample-execution-run">Sample Execution Run</h3>
<p>Below is a sample execution run to show you the input and output
format we are looking for.</p>
<p>Input</p>
<pre><code>1 2 + 3 -</code></pre>
<p>Output</p>
<pre><code>0</code></pre>
<p>You do not need to supply any input prompting for this assignment.
When the program runs, nothing should print out to the terminal and the
user should be able to input a postfix expression.</p>
<h3 id="assumptions">Assumptions</h3>
<ol type="1">
<li>The input, i.e. the postfix expression, will be entered on one line
and that all numbers and operators will be separated by a single
space.</li>
<li>The input will contain a valid postfix expression, a newline, and a
Control-D if necessary.</li>
</ol>
<h3 id="hints">Hints</h3>
<h4 id="reading-input">Reading input</h4>
<p><code>cin</code> is the opposite of <code>cout</code> – rather than
printing to standard output, it reads from standard input. When you type
a line and press enter, that entire line gets sent to <code>cin</code>,
which then automatically splits on whitespace to produce multiple
<em>tokens</em>. Therefore, if we were to supply <code>+ 2 3 isn't 2150
great??</code> as input, we would get six tokens back. This is very
helpful as the postfix expressions are already space-delimited.</p>
<p>A sample code snippet to continuously read from standard input would
look something like this:</p>
<pre><code>string token;
while (cin >> token) {
// Do stuff with `token`!
// For example, we can print each token back out on its own line:
cout << token << endl;
}</code></pre>
<h4 id="parsing-tokens">Parsing tokens</h4>
<p>There are two cases you will need to handle when parsing each token:
operators and numbers.</p>
<p>C++ allows you to compare strings for equality with <code>==</code>.
For example, you can check if <code>s</code> is the division operator
with <code>if (s == "/")</code>.<br />
Hint: we can check for all the operators, since there are only five of
them. If all the checks fail, what does that mean the token has to
be?</p>
<p>cin takes in all input as strings, but we need to convert those to
ints so that we can push them into the stack. Perhaps you should take a
look at <a
href="https://en.cppreference.com/w/cpp/string/basic_string">the
<code>string</code> documentation</a> to see if anything can help you
out.</p>
<h4 id="templates">Templates</h4>
<p>The C++ <code>stack</code> class is templated, which means it can
hold whatever type you specify (think back to ArrayLists in Java). Since
we will be using <code>int</code>s for our postfix calculator, we can
specify that by saying <code>stack<int></code> when declaring our
stack.</p>
<h4 id="checking-if-the-stack-is-empty">Checking if the stack is
empty</h4>
<p>Given that you will need to check if the stack is empty before every
<code>top</code> and <code>pop</code> call, it may be worth it to add
helper methods to your postfix calculator that, when called, will
perform the necessary checks before top/pop.</p>
<h4 id="compiling">Compiling</h4>
<p>When compiling your code, remember to compile ALL of your cpp files
in the compile command:</p>
<pre><code>clang++ postfixCalculator.cpp testPostfixCalc.cpp</code></pre>
<p>You can also use <code>clang++ *.cpp</code> if there are no other C++
files in your directory.</p>
<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
handle negative integer inputs and add the remaining three operators:
multiplication, division, negation. By the end of the in-lab, your
postfix calculator should be able to read in a single line of
space-delimited tokens representing a postfix expression and print out
the result of the expression before exiting.</p>
<h3 id="input-1">Input</h3>
<p>The core functionality of user input should be completed in the
pre-lab. For this section, you must add code that allows the program to
accept negative numbers (e.g -1, -10) for use with the calculator. In
addition to handling negative numbers, you must also add functionality
that allows the user to enter the symbols for multiplication, division,
and negation, which are respectively: <code>*</code>, <code>/</code>,
<code>~</code></p>
<h3 id="output">Output</h3>
<p>See the Sample Execution Run section of the pre-lab for
specifications.</p>
<h3 id="hints-1">Hints</h3>
<p>By expanding the integer input to also include negative numbers, you
must be careful not to accidentally parse a negative number as the
subtraction operator. For example, if your code were to only check the
first character of every token, then it may mistake a number like
<code>-5</code> as the subtraction operator <code>-</code>. To handle
this, your code should check the length of tokens and their first
character in order to determine exactly what the user has just input to
your calculator.</p>
<hr />
<h2 id="post-lab-1">Post-lab</h2>
<p>For the post-lab, you will be implementing your own stack and then
modifying your postfix calculator to use that stack instead of the STL
stack.</p>
<p>Your stack class must:</p>
<ul>
<li>Implement the <code>void push(int e)</code>, <code>void
pop()</code>, <code>int top()</code>, and <code>bool empty()</code>
methods to perform the same functionality as the STL stack</li>
<li>Internally use a linked list</li>
<li>Have no maximum capacity (we should be able to push as many elements
as we’d like)</li>
<li>Not use any STL containers</li>
</ul>
<p>You may modify and re-use your LinkedList code from Lab 2, or you may
write your own code, as long as you satisfy the above requirements.</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 is compiles with
<code>clang++ *.cpp</code></p>
<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>