Computer Science II -- Week 5
Introduction
Note that the links from this page are to handouts that will be distributed the night of class. Only print out those handouts if you could not attend class.
Main topics this week:
This week we'll take a look at some of the uses of the stack data structure. In general, stacks are quite useful when you want to remember the last something you found, but still want to keep track of all the somethings you found. Let's look at some examples.
Matching
Stacks are good for making sure that beginning and ending symbols match properly. For example, in a C++ program, you always have to have a closing parenthesis for every open parenthesis. Same thing with the curly braces. Stacks can be used to do this checking.
When you find a beginning symbol, push it onto the stack.
When you find an ending symbol, see if the top of the stack is the right kind of beginning symbol. If so, pop the stack. If not, there's an error.
Show actual stack for as the following code is parsed:
void main ()
{
int a[3];getInt (a[0];
}
You could also use the same sort of logic for matching beginning and ending comments (/* and */), beginning and ending quotes (" and "), etc.
Function Calls
We've talked about passing arguments to functions by value having a copy made, but we really haven't talked about where that copy is made. C++ has a stack it uses for keeping track of function calls, function arguments, and local variables.
When a function call is made, the first thing that gets pushed onto the stack is where the function is being called from (so when the function is done, C++ knows where to return to).
Next, function arguments and local variables get pushed onto the stack. What would the stack look like for:
void main ()
{
function1 (6, 7);
}void function1 (int x, int y)
{
int z = 5;
}
What happens if a function calls itself? What would the stack look like for:
void main ()
{
function1 (6, 7);
}void function1 (int x, int y)
{
int z = 5;if (x < 50)
function1 (x + 1, y + 1);
}
When does the stack get popped?
What happens with return values?
Calculator
A little background: infix and postfix expressions
Infix Postfix
1 + 2 1 2 +
(1 + 1) * 2 1 1 + 2 *
1 + 1 * 2 1 1 2 * +
Stacks can be used to evaluate a postfix expression. So you could type in 1 1 + and get back the answer 2. How?
Work through postfix evaluation algorithm.
Try this out on these examples:
1 1 +
1 1 + 2 *
1 1 2 * +
So you could write a calculator program that would allow the user to type in postfix expressions. Some models of scientific calculators do this, and now you know why. It's pretty easy to evaluate postfix expressions. But if you were going to really write a calculator program, you would want your users to be able to type in normal infix expressions.
Luckily, stacks can be used to convert an infix expression to a postfix expression (then you'd use the above algorithm to evaluate the postfix expression). In this algorithm, we use a stack and an output string.
Work through infix to postfix algorithm:
Try this out on these examples:
1 + 1
1 + 10 * 2
(1 + 10) * 2
(1 + 1) * 2 + 3
(1 + 1) * (2 + 3)
Show swap example for multiple data types.
void swap (int &first, int &second)
{
int &temp = first;
first = second;
second = temp;
}void swap (string &first, string &second)
{
string &temp = first;
first = second;
second = temp;
}
Templates provide a way to write code that can be used for multiple data types, so our swap can be rewritten without knowing what data type will be used.
template <class T>
void swap (T &first, T &second)
{
T temp = first;
first = second;
second = temp;
}
Now we can swap any data type just by calling the function:
int x, y;
string a, b;
Foo d, e;swap (x, y);
swap (a, b);
swap (d, e);
What does the swap function assume about the datatype that is passed into it?
We have a similar problem with classes:
class Set
{
public:
void insert (int);
void remove (int);
int getFirst () const;
int getNext () const;
};
What if we want a Set of strings?
We can have template classes, too:
template <class T>
class Set
{
public:
void insert (const T &);
void remove (const T &);
T getFirst () const;
T getNext () const;
};
Note passing T by const reference instead of by value. We don't know what data type will actually be used, so pass by reference so we won't make copies of a big data type.
Using template classes is a bit different from using template functions. We need to tell C++ the type of data we want the class to use when we declare the variable:
void main ()
{
Set<int> aSet;
Set<Foo> anotherSet;
}
What if we want a Set of Sets?
void main ()
{
Set<Set <int> > aSet;
}
Note the space between the two angle brackets (>). Why is this needed?
Write code to use a stack to evaluate a postfix expression. Your code should input the postfix expression from the user. The postfix expression will be a series of numbers and operators, all separated by spaces. Numbers can be any positive integer. Operators can be:
+ Addition
- Subtraction
/ Division
* Multiplication
Some examples of valid input and the output your code would generate:
Input: 20 2 + Output: 22
Input: 21 2 3 * + Output: 27
You should hand-test your code with several sample inputs.
To use the stack class from the Standard Template Library, you must:
1) #include <stack>
2) Declare your stack variable like this: stack<int> aStack;
You will have to use string tokenizing to break apart the string into the individual numbers and operators.