Go up to the Labs table of contents page
To understand the workings of a stack as well as postfix notation, and to be introduced to the STL library
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 LIFO property.
stack class. The standard library includes a collection of useful routines analogous to the routines in Java's SDK, albeit much smaller (it contains a vector class, for example).
#include <stack> at the top of your C++ file. A standard clang++ installation should automatically find the standard stack class (this works in Linux).main() function). This file should have hard-coded values for input; handling keyboard input is the in-lab.list, vector, stack, etc.) for this, but you can use the standard library's string 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. Your stack class can use a linked-list/pointer-based implementation, or an array-based implementation. 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, operator=(), 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++.clang++ *.cpp, 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)#include "Stack.h" versus #include "stack.h") is correct.In this lab, you will:
The various parts of this lab develop the entire program:
Note that the program is fully able to be run after each lab portion.
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:
void push(int e): This adds the passed element to the top of the stack.int top(): 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.void pop(): 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.bool empty(): This tells whether there are any elements left in the stack (false) or not (true).Often, the top() and pop() functionality are joined as an int pop() function, but in this lab, it is beneficial to separate them.
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 pop() or top() are called on an empty stack, terminate the program with the function call exit(-1), which is from the <cstdlib> library.
For this lab, you will use a stack of int values.
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 main() method, the values to be operated on by your calculator. Make sure the test(s) in main demonstrates the functionality of all operators!
A sample main() 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 main() function uses the first sample input given at the very end of this document.
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;
}Keep in mind that you can type up a few of the blocks, and comment them out with the /* ... */ comment syntax that you are familiar with from Java -- this will allow you to easily switch between the different hard-coded input test cases.
Your calculator must implement the following arithmetic operations:
+ : addition- : subtraction* : multiplication/ : division~ : unary negationNotes:
Postfix notation (also known as reverse Polish notation) involves writing the operators after the operands. Note how parentheses are unnecessary in postfix notation.
An online description of postfix calculators can be found on Wikipedia - note that you do NOT 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.
When you start handling input (in the in-lab), you will want to store your read-in values into strings. You can use == to compare strings. Alternatively, you can use the string compare() method to compare them, but realize that it returns 0 if they are equal, and non-zero if they are not equal. The == operator on strings works as expected (returns true if they are the same).
If you want to see some quick code for converting a string to an int, see the StringToInt() function at the bottom of this page. Warning: just copying that function without understanding it will only make your life more difficult.
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.
clang++ postfixCalculator.cpp testPostfixCalc.cpp. Or you can use clang++ *.cppusing namespace std; 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.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.
If you finish your in-lab before the end of the lab session, start working on your post-lab.
For your keyboard input, your program should read in just a single line. You should read this in using 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.
All input is read from standard input (i.e. cin)! 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.
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 int.
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):
./a.out < addition.txtA 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.
#include <iostream>
using namespace std;
int main() {
string s;
while (cin >> s) {
cout << s << endl;
}
return 0;
}For the postfix calculator, each string s 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).
You may find it useful to use the isdigit() or atoi() functions provided in <cstdlib> in this lab. Try searching on the web for info on these routines. The atoi() 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 c_str() method of the C++ string object. More string methods can be found at http://en.cppreference.com/w/cpp/string/basic_string.
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 random-tokens.txt, which contains:
+ 2 3 isn't 2150 great??When run, it looks like the following:
$ ./a.out < random-words.txt
+
2
3
isn't
2150
great??Note, as stated above, that this code reads in each space-delimited token. Another way this code can be run is by directly typing into stdin:
$ ./a.out
+ 2 3 isn't 2150 great??
+
2
3
isn't
2150
great??
^DIn the above execution, what was typed in was + 2 3 isn't 2150 great?? (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 ^D) was then pressed (the last line in that execution run). Control-D closes the stdin pipe by providing the EOF flag.
NOTE: When hitting Control-D, you have to enter it on it's own line. This means that you first have to hit Enter, then Control-D.
How should the program know when you are finished providing input? There are a couple of ways to do this.
getline() method, but this is likely the harder way to deal with it.Either way is fine. Our test scripts will send in all the input on a single line, 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.
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!).
You will also have to write up the difficulties.txt file, as described above in the lab procedure section.
Note that you only have to implement the four stack methods described in the pre-lab section (and the constructor, of course): push(), pop(), top(), and empty(). The other methods (copy constructor, operator=(), etc.) do not need to be implemented for this lab.
Most of you will implement your stack in one of the following ways:
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:
clang++ *.cppThe following examples provide postfix expressions and their expected value.
addition.txt: 1 2 3 4 5 + + + +; expected output: 15
subtraction.txt: 20 10 - -3 10 - - 2 -; expected output: 21
multiplication.txt: -1 -2 -5 3 * 2 -2 * * * *; expected output: 120
division.txt: -1512 -12 -2 / / -2 / 3 /; expected output: 42
negation.txt: -1 ~ ~ ~; expected output: 1