Tutorial for Program 2
Written by DarkTussin
Coding our Stack:
Let's start with the stack, since we will be doing all of our calculations and posting all of our values into it.
Our Stack class consists of several functions and a single piece of data:
Our Node pointer that points to our first node.
Our Node class, consists of two elements.
The first element is a Node pointer of its own, and an integer value.
Picture it like this:
------------------
[ Reference Node ]
[ ]
[ Node Pointer ] ---> 0
[ Integer ]
[ ]
[ 0 ]
------------------
Our node class is incredibly simple:
Here's an example using just our Node class:
As you can see, the first node points to the memory location of the second.
This is how we maintain organization in our stack
------------------ ------------------
[ First Node ] [ Second Node ]
[ ] [ ]
[ Node Pointer ]--------->[ Node Pointer ] ---> 0
[ Integer ] [ Integer ]
[ ] [ ]
[ 5 ] [ 10 ]
------------------ ------------------
So how do we use this in our stack?
Let's take a look at our stack class:
We have a constructor, a destructor and 3 functions
We also have 1 data element: our reference node
Our constructor and destructor are very simple,
and you will see that our destructor uses the pop function
we will be writing to remove each node in the chain until
it finally gets to the reference node and deletes it.
Our push and pop functions are the main functions we will be using for
almost all of our calculations, so let's step through what they do:
This is the meat of our stack code.
Hopefully this will help you visualize it [if you don't!]
Stack theStack;
------------------
[ Reference ]
[ ]
[ Node Pointer ]----> 0
[ Integer ]
[ ]
[ 0 ]
------------------
theStack.push(5);
while(testNode->next !=0)
testNode = testNode->next;
testNode->next = newNode;
testNode = 0----| testNode->next is our reference->next (which currently points at nothing)
| | testNode->next = newNode (now our reference points to our new node!)
------------------ | ------------------
[ Reference ] | [ First Node ]
[ ] v [ ]
[ Node Pointer ]---->[ Node Pointer ]---> 0
[ Integer ] [ Integer ]
[ ] [ ]
[ 0 ] [ 5 ]
------------------ ------------------
theStack.push(10);
while(testNode->next !=0)
testNode = testNode->next;
testNode->next = newNode;
testNode->next ------------------------|
| | |
------------------ ------------------ | ------------------
[ Reference ] [ First Node ] | [ Second Node ]
[ ] [ ] v [ ]
[ Node Pointer ]---->[ Node Pointer ]---->[ Node Pointer ]----> 0
[ Integer ] [ Integer ] [ Integer ]
[ ] [ ] [ ]
[ 0 ] [ 5 ] [ 10 ]
------------------ ------------------ ------------------
Anyway, I hope you get the idea!
Our size() function, in case you're curious, just counts the nodes until it hits the end
Coding our Postfix Calculator:
I don't want to code your calculator for you, but I'd like to go over some key points
to think about and get you started.
Getting the input for the calculator is relatively simple.
It can be done in several ways, using a character array, or using strings.
I personally prefer using strings since they're simple and provide us with some solid functions.
To use strings, make sure you add the include function to the top of your code (#include <string>)
Here is a simple example of how to get input with a string and an example of program flow
Just another note, if you put continue; in a while loop, it goes back to the top :)
I want to leave some code for you to write, but from the flow example you get an idea of what you need to code.
The isvalidInput() function should do some basic error checking (like making sure there aren't letters)
As for the calculateInput() function, just take your input one character at a time and think about what it needs to do.
Another note on strings is that you can use them like arrays.
For example, to get the first character in your input string, you could use input[0]
Another helpful thing to know is you can turn a string into a number using atoi(input.c_str())
atoi() only works with character arrays, but input.c_str() converts the string to a character array :)
Finally, you can get the size of a string using input.size()
The calculateInput() function is a bit of a pain so feel free to let me know if you need more help.
Input Validation
Validating the user input is important.
If they try to slip letters into our calculations it will crash our program.
The initial input validation should make sure that there are no letters in the input.
There are many ways to do this, but we can start our validation by setting up a list of allowed characters.
You can do this with a string or a character array, but here's an example:
string ACCEPTABLE = " -+/*0123456789";
This string contains all the characters that are allowed in our input
To see if our input doesn't contain these characters, we can use a loop:
Just so you understand what this loop does:
x = 0; y = 0;
input = "12345abc"
allowed = " -+/*0123456789"
Compare input[0] to allowed list
input[0] = '1'
allowed[0] = ' ' //check next
allowed[1] = '-' //check next
allowed[2] = '+' //check next
allowed[3] = '/' //check next
allowed[4] = '*' //check next
allowed[5] = '0' //check next
allowed[6] = '1' //Valid character found, next character
input[1] = '2'
allowed[0] = ' ' //check next
allowed[1] = '-' //check next
allowed[2] = '+' //check next
allowed[3] = '/' //check next
allowed[4] = '*' //check next
allowed[5] = '0' //check next
allowed[6] = '1' //check next
allowed[7] = '2' //Valid character found, next character
...
input[5] = 'a'
allowed[0] = ' ' //check next
allowed[1] = '-' //check next
allowed[2] = '+' //check next
allowed[3] = '/' //check next
allowed[4] = '*' //check next
allowed[5] = '0' //check next
allowed[6] = '1' //check next
allowed[7] = '2' //check next
allowed[7] = '3' //check next
allowed[7] = '4' //check next
allowed[7] = '5' //check next
allowed[7] = '6' //check next
allowed[7] = '7' //check next
allowed[7] = '8' //check next
allowed[7] = '9' //We're all out of characters and it wasn't found - return false
This is how we do our initial input checking :)
Creating our Calculator
When writing the actual calculator, there are several approaches you can take.
Depending on how you want it to work, it can become more or less complex.
We can get our numbers in a similar fashion as we did our input checking,
however many numbers contain more than one digit.
If we have the number 100, we don't want to push 1 0 0 to our stack, those are completely different numbers... 3 times as many!
C++ provides us with a function called atoi()
atoi() takes a character array and turns it into a valid number.
We're using strings though!
Fortunately, the string class contains a function to turn itself into a character array.
We can use .c_str() after our string to turn it into a character array.
Here's an example where we take whatever number someone enters and add 5 to it:
string input;
getline(cin,input);
cout << 5 + atoi(input.c_str());
As you can see, all we need to push numbers to our stack is a string holding the digits.
There are 3 types of things we will find in our valid input: Digits, Operators, and Spaces
Our calculate() function should go through our input character by character and do things based on what it finds.
If it finds a digit: add the digit to a string for safekeeping and go to the next character
If it finds a space: turn the temporary string into a number and push it on the stack
If it finds an operator: make sure there are 2 numbers on the stack, pop them off, and push the result back on the stack
Again, I don't want to write all of the code for you, but you can go through each character like we did before.
I recommend using a for loop, although it's also possible to use a while loop.
Here is an example of how we do our calculations and push everything to the stack:
