forked from uva-cs/pdr
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathindex.html
197 lines (197 loc) · 18.1 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
<!DOCTYPE html>
<html>
<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 type="text/css">code{white-space: pre;}</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>Write up at least one question that you still have on Unix (or things you are still confused about)</li>
<li>Implement a postfix stack calculator for integers using the C++ STL stack</li>
<li>Create a simple program to test your calculator</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 type="1">
<li>Ensure your postfix calculator works on all the provided test cases</li>
<li>Expand your test program to handle keyboard input</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>Describe any difficulties you encountered getting your code working and what you did to solve them</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 library.
<ul>
<li>Documentation on the standard library routines can be found at <a href="https://en.cppreference.com" class="uri">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 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 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="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</li>
<li><code>-</code> : subtraction</li>
<li><code>*</code> : multiplication</li>
<li><code>/</code> : division</li>
<li><code>~</code> : unary negation</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>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 <strong>must</strong> be <em>y-x</em> or <em>y/x</em> -- in other words, the "lower" value in the stack minus/divided by the "higher" one in the stack.</li>
</ul>
<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 your postfix expressions into the <code>main()</code> method. Make sure your tests in main demonstrate 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="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="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>
<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 add keyboard input to your lab. 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>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.</p>
<p>You will 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 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="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-1">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>To convert input that represents numbers into their integer form, <code><cstdlib></code> provides the <code>int atoi(char* s)</code> function. Unfortunately, <code>atoi</code> requires C-style strings -- 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>
<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. 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 need to write up a difficulties.txt file which contains a paragraph describing any difficulties you encountered getting your code working and what you did to solve them.</p>
<p>Your stack is only required to implement the four methods as described in the prelab: <code>push()</code>, <code>pop()</code>, <code>top()</code>, and <code>empty()</code>. It must also have no maximum capacity -- in other words, we should be able to push as many elements as we'd like.</p>
<p>Most of you will implement your stack in one of the following ways:</p>
<ol type="1">
<li>Re-use your list class from lab 2. You may need to add one or two methods to it for extra convenience.</li>
<li>Build a linked-list / pointer-based stack as discussed in lecture. Your stack class would contain a pointer to the head node of the stack, and push and pop would modify the singly-linked list accordingly.</li>
<li>Manually implement an array-based stack. If you choose this method, your array must be able to automatically resize if the stack grows large enough to sufficiently fill the array. This is probably the most difficult of the three options.</li>
</ol>
<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 type="1">
<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 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>