Chapters 6 and 7 of Stroustrup’s textbook develop a very interesting example program of a calculator that can evaluate arithmetic expressions like 43.2 / (100 + 5). Evaluating arithmetic expressions is a notoriously tricky problem, and so he is forced to introduce a number of sophisticated new ideas, such as grammars and recursion.
While Stroustrup does a good job showing how to solve this tough problem, our experience has been that most students are quickly lost and confused by so many new details being introduced all at once. While many get the gist of it, they don’t really understand what’s going on.
So we will modify Stroustrup’s calculator example to evaluate a different style of arithmetic expression: postfix expressions (or reverse Polish notation, i.e. RPN for short). Postfix expressions are much easier to evaluate than regular infix mathematical expressions. Plus, we will be able to implement number of neat extra features, such as function.
The price we pay for this ease of evaluation is a loss in readability. Postfix expressions look positively bizarre the first time you see them. However, with some practice, postfix can be easier to read than infix because you can always evaluate postfix reading left to right and it doesn’t use brackets.
Postfix has practical uses: for example, the Java virtual machine (the simulated computer on which Java programs run) and Python virtual machine uses postfix for its expressions evaluation. Plus there are programming languages, such as Forth, Joy, and Factor, use postfix notation for all their expressions. The Ubuntu Linux command-line comes with a feature-rich postfix calculator called dc.
When we write arithmetic expressions, such as 5 + 2, we write them in what is known as infix form: the operator + goes in between the operands 5 and 2. But there are other ways to write expressions, and here we will look in detail at a form known as postfix. In a postfix expression, operators come after the operands, e.g. 5 2 +.
For example:
Things get trickier when you have more then one operator. For example, lets see how to the infix expression 1 + 2 * 3 in postfix form. Since * is always evaluated before + in infix, we get this postfix expression:
2 3 * 1 +
You would evaluate it in these steps:
2 3 * 1 +
--> 6 1 +
--> 7
You always starting evaluating at the left, and apply an operator to the operands immediately preceding it. After you evaluate an operator you replace the numbers and operands with the new value.
Now lets write the infix expression (1 + 2) * 3 in postfix. This time + is evaluated before * because of the brackets, and so the postfix expression is:
1 2 + 3 *
Postfix looks unusual at first, but after you try a few examples you start to get the hang of it.
Here’s one more example. The formula for the area of a circle is written pi * r * r in infix notation. In postfix, it could be written as pi r * r *, or r r * pi *.
Converting an arbitrary infix expression into an equivalent postfix expression is tricky, and so we will skip this particular problem (see Wikipedia’s entry on postfix notation if you are curious). Once we learn the comparatively simple algorithm for evaluating a postfix expressions, it is not too hard to figure out how to convert most infix expressions to postfix in an ad hoc way.
To evaluate a postfix expression, we need to introduce the idea of a stack, which is a simple data structure that lets us add and remove items at one end only.
It is easiest to understand stacks pictorially. We’ll draw a stack as a box with no top. Here’s an empty stack:
| |
| |
| | empty stack
-----
When we add an element to a stack we imagine dropping it into the stack. Adding an element to a stack is called pushing an element, and we use the function name push. For example, here is what the stack looks like after we push 5 onto it:
| |
| |
| 5 | after pushing 5 onto the stack
-----
Pushing always adds elements on top of any existing elements. So if we push 3 onto the stack, we get this:
| |
| 3 |
| 5 | after pushing 3 onto the stack already containing 5
-----
We say that 3 is on the top of the stack, and the 5 is on the bottom. Whenever you push an element, it becomes the new top. Lets push 4:
| 4 |
| 3 |
| 5 | after pushing 3 onto the stack already containing 3 and 5
-----
Now 4 is the new top of the stack; 5 is still on the bottom.
We can only remove the top element of a stack. This is called popping the stack, and we use the function name pop. If we pop our stack then it looks like this:
| |
| 3 |
| 5 | after popping the stack: 4 is removed
-----
Now 4 is gone from the stack. Calling pop again removes 3:
| |
| |
| 5 | after popping the stack: 3 is removed
-----
And one more time:
| |
| |
| | after popping the stack: 5 is removed
-----
Now the stack is empty. It is usually considered an error to pop an empty stack.
There are a number of different ways to implement a stack, and for our purposes we will implement a stack using a vector. It turns out vector was designed with stacks in mind, and so the vector functions push_back and pop_back that let us easily treat use any vector like a stack. For example:
vector<int> stack; // initially empty
stack.push_back(5); // push 5
stack.push_back(3); // push 3
stack.push_back(4); // push 4
cout << "top of stack is " << stack.back() << endl; // prints 4
stack.pop_back(); // 4 is popped
stack.pop_back(); // 3 is popped
stack.pop_back(); // 5 is popped
stack.pop_back() does not return the popped element: all it does is delete the top of the stack. So before calling pop_back we usually peek at the top of the stack using stack.back().
Of course, you can still treat stack as a vector and use any other vector operation on it. But if you need to do anything more than push, pop, or peek at the top element, then you shouldn’t be using a stack.
Note
A good question is why would we willingly restrict what functions we can use on a vector. The answer is that a stack is much simpler to work with. It has fewer functions, and so you only have to worry about pushing, popping, and peeking. This small set of simple operations reduces the chance of making an error.
To summarize, a stack is a data structure with the following three operations:
In the next section we will see that stacks are the key to evaluating postfix expressions.
How do you evaluate the postfix expression 3 10 + 2 *? Here is the complete algorithm in pseudocode. We assume that stack is initially empty:
for each token in the expression do:
if token is a number then
push it onto the stack
else if token is "+" then
pop the top 2 elements of the stack; call them a and b
push a + b onto the stack
else if token is "*" then
pop the top 2 elements of the stack; call them a and b
push a * b onto the stack
else if token is "-" then
pop the top 2 elements of the stack; call them a and b
push a - b onto the stack
else if token is "/" then
pop the top 2 elements of the stack; call them a and b
push a / b onto the stack
end for
When this loop is done, the value of the expression is the number on the top of the stack.
A token is either a number (e.g. 10) or an operator (e.g. *). For example, the expression 3 10 + 2 * has 5 tokens: three operands and two operators . We will always separate tokens in our postfix expressions by at least one space to make them easy to read using cin.
Lets trace through the evaluation of 3 10 + 2 *:
3 is read: it is pushed onto the stack:
| |
| 3 |
-----
10 is read: it is pushed onto the stack:
|10 |
| 3 |
-----
+ is read, and so 10 and 3 are popped, setting a = 3 and b = 10. Then a + b, which is 13, is pushed onto the stack:
| |
|13 |
-----
2 is read: it is pushed onto the stack:
| 2 |
|13 |
-----
* is read, and so 2 and 13 are popped, so a = 13 and b = 2. Then a * b, which is 26, is pushed onto the stack:
| |
|26 |
-----
And so the value of the postfix expression is 3 10 + 2 * is the number on the top of the stack: 26.
Exercise. What do each of the following postfix expressions evaluate to? Don’t look at the solutions until you try them!
Solutions:
Now that we know how to evaluate postfix expressions, we are ready to write our program. We will begin by writing a first draft where we will not yet worry about every little detail. Our initial focus will be to quickly get a working version of the program up and running. Then we will add features one at time, testing them as we go.
The first thing is to be completely clear about the input to our program. Numbers and operators are called tokens, e.g. -8.886 is a token and / is a token. A postfix expression is thus a sequence of tokens, e.g. the postfix expression 4 3 * 2 + consists of 5 tokens. We will require that there be at least one space between each token, and so an expression like 4 3*2+ is not allowed in our evaluator.
Lets start by writing the basic code for reading tokens and distinguishing between numbers and operators:
// postfix.cpp
#include "std_lib_cmpt125.h"
string token; // global variable
int main() {
cout << "Postfix expression evaluator, version 1\n";
while (cin >> token) {
if (token == "+" || token == "-" || token == "*" || token == "/")
cout << "'" << token << "' is an operator\n";
else
cout << token << " is (perhaps) a number\n";
}
}
Notice a few things:
Next we add a stack, and the ability to evaluate the + operator. Once we get + working it will not be too hard to implement the other operators.
If you look carefully at the postfix algorithm above, you will notice that operators are never stored on the stack: the stack only contains numbers. This tells us that we can use a vector<double> to represent our stack:
vector<double> stack; // global variable
But we run into a tricky problem right away: we read in numbers as strings, but we need them as doubles in order to do arithmetic with them. So we will need to convert strings like "-3.05" into their equivalent double -3.05. This is difficult to do by hand, so we will use a function that takes advantage of the C++ library:
// Converts string s to a double.
double string_to_double(const string& s) {
istringstream iss(s);
double x;
if (!(iss >> x))
error("Error: can't convert \"" + s + "\" to a double\n");
return x;
}
string_to_double takes a string s as input. If s is formatted like a number, e.g. if s is something like “349.03” or “-54”, then string_to_double will return an equivalent double. It does this by using an istringstream object, which lets us treat a string as if it were a stream, which lets us use >> to read values from it (just like we do with cin).
string_to_double works like this:
Using string_to_double is easy, e.g.:
string num = "3.1415926";
double x = string_to_double(num);
cout << x; // prints 3.1415926
Now with string_to_double at our disposal, lets see the next version of our postfix evaluator. This version uses the stack to evaluate postfix expressions that use +:
// Converts string s to a double.
double string_to_double(const string& s) {
istringstream iss(s);
double x;
if (!(iss >> x))
error("Error: can't convert \"" + s + "\" to a double\n");
return x;
}
string token; // global variable
vector<double> stack; // global variable
int main() {
cout << "Postfix expression evaluator, version 1\n";
while (cin >> token) {
if (token == "+") {
// pop the top two elements of the stack
// the top element is b, and the one under the top is a
double b = stack.back();
stack.pop_back();
double a = stack.back();
stack.pop_back();
stack.push_back(a + b);
// print the top of the stack so we can see the result
cout << "tos = " << stack.back() << "\n";
} else {
stack.push_back(string_to_double(token));
}
}
}
Here’s a sample run showing that + seems to be working correctly:
Postfix expression evaluator, version 1
1 2 +
tos = 3
4 +
tos = 7
3 -1 -2 1 +
tos = -1
Notice in the code in main that process + that before popping the stack we save its top element using stack.back(). Lets combine both of these statements into a single function:
// remove and return the element of the stack
double pop() {
double tos = stack.back();
stack.pop_back();
return tos;
}
We may as well also write a simple push function:
// put x on the top of the stack
void push(double x) {
stack.push_back(x);
}
These two functions let us simplify our code:
// Converts string s to a double.
double string_to_double(const string& s) {
istringstream iss(s);
double x;
if (!(iss >> x))
error("Error: can't convert \"" + s + "\" to a double\n");
return x;
}
string token; // global variable
vector<double> stack; // global variable
// remove and return the element of the stack
double pop() {
double tos = stack.back();
stack.pop_back();
return tos;
}
// put x on the top of the stack
void push(double x) {
stack.push_back(x);
}
int main() {
cout << "Postfix expression evaluator, version 1\n";
while (cin >> token) {
if (token == "+") {
// pop the top two elements of the stack
// the top element is b, and the one under the top is a
double b = pop();
double a = pop();
push(a + b);
// print the top of the stack so we can see the result
cout << "tos = " << stack.back() << "\n";
} else {
push(string_to_double(token));
}
}
}
The code for handling + is now much easier to read: hiding details inside a function like this is often a good idea.
Notice also that we must put the push and pop functions after the declarations for token and stack but before main. Functions must be defined before their first use.
With + working, it is little more than cut-and-paste to add code to handle -, *, and /:
while (cin >> token) {
if (token == "+") {
// pop the top two elements of the stack
// the top element is b, and the one under the top is a
double b = pop();
double a = pop();
push(a + b);
// print the top of the stack so we can see the result
cout << "tos = " << stack.back() << "\n";
} else if (token == "-") {
double b = pop();
double a = pop();
push(a - b);
cout << "tos = " << stack.back() << "\n";
} else if (token == "*") {
double b = pop();
double a = pop();
push(a * b);
cout << "tos = " << stack.back() << "\n";
} else if (token == "/") {
double b = pop();
double a = pop();
push(a / b);
cout << "tos = " << stack.back() << "\n";
} else {
push(string_to_double(token));
}
And it seems to work well enough:
Postfix expression evaluator, version 1
3 4 *
tos = 12
1 2 + 3 4 + *
tos = 3
tos = 7
tos = 21
The value of the postfix expression 1 2 + 3 4 + * is indeed 21.
Here’s an example where we calculate the area of a circle of radius 5:
5 5 * 3.14 *
tos = 25
tos = 78.5
It took about 60 lines of code to implement this postfix expression evaluator. The big if-else-if statement in the while-loop makes up the bulk of the program, but the code blocks there are simple and similar.
Now that we have the basic calculator working, lets add some more features.
Right now we print the top of the stack after every operator. While this is useful for debugging, we usually only care about the final tos that shows the answer to our calculation.
So lets remove all the code that prints the top of the stack and add the "." operator. The "." operator immediately prints the top of the stack, e.g.:
5 5 * 3.15 * .
tos = 78.5
.
tos = 78.5
Now the top of the stack is only printed when we type a ".". Here is how we re-write the main if-else-if statement (the only part of the code that we change to add this feature):
if (token == "+") {
double b = pop();
double a = pop();
push(a + b);
} else if (token == "-") {
double b = pop();
double a = pop();
push(a - b);
} else if (token == "*") {
double b = pop();
double a = pop();
push(a * b);
} else if (token == "/") {
double b = pop();
double a = pop();
push(a / b);
} else if (token == ".") {
cout << "tos = " << stack.back() << "\n";
} else {
push(string_to_double(token));
}
Another convenient feature is to display a text prompt so the user knows when the programming is waiting for input. To do this we need to make three small changes throughout the program:
// ...
string token; // global variable
vector<double> stack; // global variable
const string prompt = "--> ";
// ...
int main() {
cout << "Postfix expression evaluator, version 1\n";
cout << prompt;
while (cin >> token) {
if (token == "+") {
double b = pop();
double a = pop();
push(a + b);
}
// ... code for -, *, and / ...
} else if (token == ".") {
cout << "tos = " << stack.back() << "\n";
cout << prompt;
} else {
push(string_to_double(token));
}
}
}
We declare prompt to be a constant string, and then display the prompt before entering the while-loop. We re-display the prompt whenever the top of the stack has been printed:
Postfix expression evaluator, version 1
--> 14 6 + 2 3 + / .
tos = 4
--> 2 3 * 4 * 5 * .
tos = 120
-->
The two changes of adding an input prompt and using "." to print the top of the stack make the evaluator much more user friendly.
It is distressingly easy to crash the current version of our evaluator. For instance:
Postfix expression evaluator, version 1
--> .
Segmentation fault
Postfix expression evaluator, version 1
--> 5 * .
tos = 8.15208e-322
--> Segmentation fault
A segmentation fault is one kind of run-time error that C++ programs can generate in Linux. As you can see, segmentation faults tell you nothing about why or where the error occurred in your program.
The problem with these examples is that we are popping from an empty stack. It makes no sense in our evaluator to ever pop from an empty stack, and so if that happens we should, instead of crashing, print an error message, e.g. something like this:
Postfix expression evaluator, version 1
--> .
Error: . tried to pop an empty stack
-->
This is much better. Not only does it not crash the program, but it gives the user a hint about what went wrong.
Lets try to get this feature working. What we’ll do is add an if-statement to the pop() function that checks if the stack is empty. If it is, it should print an error message; if it’s not, it should go ahead and pop the stack. Here’s a first try:
// remove and return the element of the stack
double pop() {
if (stack.size() == 0) {
error("Error: " << token << " tried to peek at an empty stack\n");
} else {
double tos = stack.back();
stack.pop_back();
return tos;
}
}
Unfortunately it doesn’t work as we would like:
Postfix expression evaluator, version 1
--> .
Segmentation fault
If you look at the code than handles ".", you will see that it does not use the pop() function. Instead, it uses stack.back() to peek at the top of the stack. The problem is that this fails when the stack is empty.
To fix this, lets create a new function called peek() that returns the top of the stack without removing it:
// return top of stack without removing it
double peek() {
if (stack.size() == 0)
error("Error: " + token + " tried to peek at an empty stack\n");
else
return stack.back();
}
Now lets re-write pop to use peek():
// remove and return the element of the stack
double pop() {
double tos = peek();
stack.pop_back();
return tos;
}
We no longer need to check for an empty stack within pop() because that check is done in peek().
Now we can replace stack.back() with peek() in the code block for ".":
// ...
} else if (token == ".") {
cout << "tos = " << peek() << "\n";
cout << prompt;
} else {
// ...
The result is a little bit better:
Postfix expression evaluator, version 1
--> .
terminate called after throwing an instance of 'std::runtime_error'
what(): Error: . tried to peek at an empty stack
Aborted
Postfix expression evaluator, version 1
--> 1 +
terminate called after throwing an instance of 'std::runtime_error'
what(): Error: + tried to peek an empty stack
Aborted
The program still crashes, but at least there is a sensible error message in the debris.
To avoid the program from crashing requires the introduction of a new C++ construct: a try/catch block.
The error function we are using in our program comes from our std_lib_c,[t125.h header file. If you read that file you can see how error is implemented:
inline void error(const string& s)
{
throw runtime_error(s);
}
Look just at the body of this function: it throws a runtime_error object. In general, we only throw objects when an error has occurred, and we refer to objects that can be used with throw has exceptions.
When C++ throws an exception, the program will crash. While that’s often what we want when we are developing a program, we don’t want regular users to have deal with such unfriendly behaviour.
So what we can do is catch an exception. To do this we use a try/catch block. For example:
try {
// ... lots of code before ...
if (overheat()) {
error("sprocket X98-k has over-heated the GA44 (mark 2 spatula");
}
// ... lots of code after ...
} catch (runtime_error e){
cout << "Oops! Shutting down to avoid explosion.\n";
}
When you run this code, it’s possible that it could print the message in the catch block:
$ ./a.out
Oops! Shutting down to avoid explosion.
This is much nicer than the messy error message produce by not catching the exception from error:
$ ./a.out
terminate called after throwing an instance of 'std::runtime_error'
what(): sprocket X98-k has over-heated the GA44 (mark 2) spatula
Aborted
We put whatever code we want into the try and catch blocks. Generally speaking, catch blocks tend to be relatively short and do things like print error messages and close any open resources (such as files or network connections). A try block can may contain much more code, and if any statement in the try block throws an exception, then the flow of control immediately jumps to the catch block, skipping over any unexecuted statements in the try part.
For now, the only error we will catch is the runtime_error exception that error throws. If e is an exception thrown by error, then e.what() will give us the error string passed into it. As you will see in the next section, this is how we can print error messages without stopping the program.
To handle exceptions in our evaluator, we will wrap the if-else-if statement in main inside a try/catch:
int main() {
cout << "Postfix expression evaluator, version 1\n";
cout << prompt;
while (cin >> token) {
try {
if (token == "+") {
double b = pop();
double a = pop();
push(a + b);
} else if (token == "-") {
double b = pop();
double a = pop();
push(a - b);
} else if (token == "*") {
double b = pop();
double a = pop();
push(a * b);
} else if (token == "/") {
double b = pop();
double a = pop();
push(a / b);
} else if (token == ".") {
cout << "tos = " << peek() << "\n";
cout << prompt;
} else {
push(string_to_double(token));
} // if
} catch (runtime_error e) {
cout << e.what(); // print the error message
cout << prompt;
} // catch
} // while
} // main
Now if any call to peek() or pop() triggers an error, the flow of control will immediately jump to the catch block where an error message will be printed.
It is important to understand that when an exception is thrown, the program stops what it is doing and jumps immediately into the catch block. For instance, if double b = pop() in the code block that handles "\" triggers an error, then the remaining statements in that block are not executed. The flow of control jumps straight to the code in catch.
If no exception is thrown in the try block, then the code in the catch block is not executed.
The error-handling is now much better:
Postfix expression evaluator, version 1
--> .
Error: . tried to peek at an empty stack
--> +
Error: + tried to peek at an empty stack
--> 6 * .
Error: * tried to peek at an empty stack
--> Error: . tried to peek at an empty stack
As the rather messy last error shows, the error-handling is still not quite perfect. The * causes an error because it needs at least two items to be on the stack. It pops one item successfully, but then fails to pop the second (because the stack is empty). This failure prints the first error message. Then the program reads in the ".", which tries to peek at the now-empty stack: and so the second error message is printed.
It’s tricky to fix this the way we are doing things. However, the error messages seem good enough for now. If it becomes a big problem later, we can come back and address the issue then. For now lets move on and add some more features.
Keeping source code neat and tidy is important. Well-organized source code makes your programs easier to read, and thus easier to understand. When it comes time to fix a bug or add a new feature, you, or whoever is modifying your code, will be pleased that the code is understandable. Most professional programmers can tell you horror stories of having to work with messy source code they couldn’t understand: it is almost impossible to change anything, and it can take hours, or even days, to understand what it is going on.
We’ll do two things to our source code. First, lets add some comments that divide our program into sections:
// postfix.cpp
#include "std_lib_facilities_ubuntu.h"
/////////////////////////////////////////////////////////////
//
// Generic helper functions
//
/////////////////////////////////////////////////////////////
// ... just string_to_double for now ...
/////////////////////////////////////////////////////////////
//
// Global variables
//
/////////////////////////////////////////////////////////////
string token;
vector<double> stack;
const string prompt = "--> ";
/////////////////////////////////////////////////////////////
//
// Program-specific helper functions
//
/////////////////////////////////////////////////////////////
// .. peek, pop, push, etc. go here ...
/////////////////////////////////////////////////////////////
//
// Main function
//
/////////////////////////////////////////////////////////////
int main() {
cout << "Postfix expression evaluator, version 1\n";
// ...
} // main
This doesn’t change the behaviour of any of the code. All we’ve done is add comments to make it clear what part of the program is what. The order of the sections matters. Generic helper functions are functions that don’t depend upon the global variables of this program. Thus they come before the global variables, but after any #include lines (so they can use included code). In large programs, such helper functions would be moved to their own .h or .cpp file, but for now it is easier to keep everything in one program.
Next come our global variables. These are variables that we want to be available to the code in main and other program-specific function we write. As mentioned earlier, you should try to minimize the use of global variables because it can be difficult to keep track of how they change. Indeed, some programming languages, such as Java, ban global variables altogether, and require that all variables be defined either inside a function or a class (we’ll talk about classes later in the course: a class is essentially a collection of functions and variables).
The program-specific functions are functions designed to work specifically with this program. They may use the global variables defined in the previous section.
And finally, we have the main function. Recall that every C++ program needs exactly one function called main, and main is where C++ always starts executing the program.
For our second bit of source code re-structuring, lets put the big if-statement in the main while-loop inside its own function called process_token():
// ...
// process one token
void process_token() {
if (token == "+") {
double b = pop();
double a = pop();
push(a + b);
} else if (token == "-") {
double b = pop();
double a = pop();
push(a - b);
} else if (token == "*") {
double b = pop();
double a = pop();
push(a * b);
} else if (token == "/") {
double b = pop();
double a = pop();
push(a / b);
} else if (token == ".") {
cout << "tos = " << peek() << "\n";
cout << prompt;
} else {
push(string_to_double(token));
} // if
}
/////////////////////////////////////////////////////////////
//
// Main function
//
/////////////////////////////////////////////////////////////
int main() {
cout << "Postfix expression evaluator, version 1\n";
cout << prompt;
while (cin >> token) {
try {
process_token();
} catch (runtime_error e) {
cout << e.what(); // print the error message
cout << prompt;
} // catch
} // while
} // main
This change makes our main function much easier to read. It also separates token processing from error-handling, which is a useful simplification: when we add new tokens to the evaluator we won’t have to worry about catching the errors they might throw. All we do is add the required code to process_token, and any errors will be caught in the try/catch block in main.
It’s straightforward to add other operators to our postfix evaluator. For instance, the inc operator adds 1 to the number on the top of the stack, while the dec operator subtracts 1:
--> 6 inc inc .
tos = 8
--> dec dec dec .
tos = 5
To implement these we add the following to the big if-statement in process_token:
// ...
} else if (token == "inc") {
double b = pop();
push(b + 1);
} else if (token == "dec") {
double b = pop();
push(b - 1);
}
Another handy operator is dup, which is short for “duplicate”. It pushes a new copy of the current top element onto the stack:
--> 4 dup * .
tos = 16
Here is how to implement it:
// ... process_token() ...
} else if (token == "dup") {
double b = peek();
push(b);
}
Finally, lets implement an operator called pstack that immediately prints the entire contents of the stack, e.g.
--> 1 2 3 4 .
tos = 4
--> pstack .
<tos=4, 3, 2, 1>
tos = 4
The code for printing the stack is a bit messy, and so we will put it in its own function in the “Program-specific helper functions” section:
void print_stack() {
const int n = stack.size();
if (n == 0) cout << "<empty stack>";
else if (n == 1) cout << "<tos=" << peek() << ">";
else { // n >= 2
cout << "<tos=" << peek();
for(int i = n - 2; i >= 0; --i)
cout << ", " << stack[i];
cout << ">";
}
cout << endl;
}
Notice that we print the vector containing the stack in reverse order, so that the top of the stack is printed on the left. We did this so that it will always be easy to see the top of the stack, no matter how many numbers it contains.
In process_token we add this code to the if-statement:
} else if (token == "pstack") {
print_stack();
}
Modify the behaviour of "." so that when the stack is empty it the message <empty stack> is printed:
--> .
<empty stack>
Add the % operator, i.e. the remainder operator, to the evaluator. A postfix expression of the form a b % is equivalent to the infix expression a % b. For example:
--> 15 6 %
tos = 3
--> 36 4 %
tos = 0
Add the ^2 operator that replaces the top element of the stack with its square. For example:
--> 3 ^2 .
tos = 9
--> 7 ^2 .
tos = 49
--> 3 ^2 4 ^2 +
tos = 25
Add sin (sine) and cos (cosine) functions to the evaluator, e.g.:
--> 15 sin ^2 15 cos ^2 + .
tos = 1
Modify the evaluator so that both ";" and "." immediately print the top of the stack. For example:
--> 4 2 / .
tos = 2
--> 4 2 / ;
tos = 2
Add the pop operator to the evaluator: pop simply pops the top element of the stack, e.g.:
--> 1 2 + .
tos = 3
--> pop .
<empty stack>
Of course, pop should cause an error message to be printed if it is run on an empty stack.
Add the popn operator to the evaluator: popn pops the stack n times, where n is the number on the top of the stack when popn is called. For example:
--> 1 2 3 4 .
tos = 4
--> 3 popn .
tos = 1
Note that the argument to popn does not count as one of the numbers that is popped. Here’s another example:
--> 2 1 -4 .
tos = -4
--> 2 popn .
tos = 2
--> 1 popn .
<empty stack>
If the parameter to popn (i.e. number on top of the stack when popn runs) is not an integer, then the digits after the decimal. For example:
--> 1 9 8 2 .
tos = 2
--> 3.9 popn .
tos = 1
As with pop, an error message should be printed if popn runs on an empty stack.
Add the dupn operator to the evaluator: dupn duplicates the top n elements of the stack, where n is the number on the top of the stack when dupn is called. For example:
--> 1 2 3 .
tos = 3
--> 2 dupn .
tos = 3
--> pstack
<tos=3, 2, 3, 2, 1>
Throw an error if n is less than 0. If n = 0, then do nothing, e.g.:
--> 5 4 2 .
tos = 2
--> 0 dup .
tos = 2
--> pstack
<tos=2, 4, 5>
Add the swap operator to the evaluator: swap switches the position of the first element of the stack with the second element, i.e.:
| | swap | |
| b | -----> | a |
| a | | b |
----- -----
For example:
--> 3 4 - .
tos = -1
--> 3 4 swap - .
tos = 1
Add the size operator that counts the number of items currently on the stack, and then pushes that number on the top of the stack. For example, if the stack is initially empty then:
--> size .
tos = 0
--> size .
tos = 1
--> 1 2 + .
tos = 3
--> size .
tos = 3
Keep in mind that because size pushes the size onto the stack, the stack will have one more element on it than before size was called.
Add the clear operator that empties the stack by removing all the elements from it, e.g.:
--> .
<empty stack>
--> 1 2 .
tos = 2
--> clear .
<empty stack>
--> size .
tos = 0
Hint: Read the documentation for the vector class (e.g. in your textbook, or search online), and you will find it has a function that helps quite a bit for this question!
Add a special operator called prompt s that changes the current command-line prompt to be whatever s is, e.g.:
--> prompt >>>
>>> 1 2 + .
tos = 3
>>>
Make sure that s is not empty and not a number.
In C++, 1 / 2 is 0, because when you divide two integers the calculation uses integer division. If instead you wrote 1.0 / 2, or 1 / 2.0, or 1.0 / 2.0, then C++ does floating-point division and returns 0.5.
Add this behaviour to the postfix evaluator. When it’s finished, it should work like this:
--> 1 2 / .
tos = 0
--> 1.0 2 / .
tos = 0.5
--> 1 2.0 / .
tos = 0.5
--> 1.0 2.0 / .
tos = 0.5