what does 43.2 / (100 + 5) evaluate to?
in general, evaluating arithmetic expressions like this is a very tricky problem!
yet it is very useful and important
we call a program that evaluates an expression like this an expression evaluator
the input to an expression evaluator is a string representation of an arithmetic expression, and the output is the value of the expression, or an error if the expression is somehow invalid (e.g. missing a bracket, divide by 0, ...)
expression evaluators are often implemented using formal grammars and recursion, both of which are relatively advanced concepts
we are going to implement an expression evaluator, but one that mostly avoids such advanced techniques
we’ll implement a Reverse Polish Notation (RPN), or postfix expression evaluator
it will look strange at first, but it is useful and you can understand all of the details
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 that use postfix notation for their expressions, e,g, Forth, Joy, and Factor
also, the Ubuntu Linux command-line comes with a feature-rich postfix calculator called dc
an ordinary arithmetic expression like 5 + 2 is in infix form
that means the operator, + in this case, goes in between the operands
but there are two other ways we could have written 5 + 2
+ 5 2 is a prefix expression, because the + goes in the front
5 2 + is a postfix expression, because the + goes at the end
our expression evaluator is going to evaluate expression that are in postfix form
here are a few examples
1 2 + is 3, because it means 1 + 2
4 7 - is -3, because it means 4 - 7
3 4 * is 12, because it means 1 * 2
10 5 / is 2, because it means 10 / 5
things get a bit trickier when you have more then one operator
consider how we could write the infix expression 1 + 2 * 3 in postfix
since * is always evaluated before + in infix, we get this postfix expression:
2 3 * 1 +
you 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 *
you evaluate it in these steps:
1 2 + 3 *
--> 3 3 *
--> 9
postfix looks unusual at first, but after you try a few examples you start to get the hang of it
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 algorithm for evaluating a postfix expressions, it is not too hard to work directly in postfix
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 a 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 a 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
we’ll treat popping an empty stack as an error
there are many different ways to implement a stack
for our purposes we will implement a stack using a vector
it turns out vector was designed with stacks in mind
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()
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: you only have to worry about pushing, popping, and peeking it. 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:
how do you evaluate the postfix expression 3 10 + 2 *?
here is the complete algorithm in pseudocode:
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
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 first try to get a simple working version of the algorithm up and running so we can start using it right away
we will add features one at a 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 1 or more 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
so an expression like 4 3*2+ will cause an error in our evaluator
lets start by writing the basic code for reading tokens and distinguishing between numbers and operators:
#include "error.h"
#include <iostream>
#include <string>
using namespace std;
string token; // global variable
int main() {
cout << "Postfix expression evaluator\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
the variable token is a string because it must hold both operators and numbers
token is declared outside of main
token is thus a global variable, and so it can be accessed by any code in the file
as a general rule of thumb you should avoid global variables
but for this program making token global is quite helpful since many different functions will need to know the current token.
in the while loop body, we assume that if token is not an operator, then it is a number
of course, token could be some other string, such as x or a7, but we will ignore that possibility in this draft.
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 read the postfix evaluation algorithm above, you will notice that operators are never stored on the stack: the stack only contains numbers
so we can use a vector<double> to represent our stack:
vector<double> stack; // global variable
but we immediately run into a tricky problem: 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
the easiest way to do this is to use the C++11 function stod, e.g.:
#include <string>
string s = " -5.026 ";
double x = stod(s);
cout << "\"" << s << "\"" << "\n"
<< x << "\n";
this prints:
" -5.026 "
-5.026
according to the documentation for stod, it could throw an invalid_argument exception, or an out_of_range exception
it’s important to know that for later in the program when we need to handle errors
to be consistent with the code below, we will wrap the call to stod in its own function
// Converts string s to a double.
double string_to_double(const string& s) {
return stod(x);
}
if you are using a version of C++ before C++11, you could do it this way:
#include <sstream>
// Converts string s to a double.
double string_to_double(const string& s) {
istringstream iss(s);
double x;
if (!(iss >> x))
cmpt::error("Error: can't convert \"" + s + "\" to a double\n");
return x;
}
string_to_double takes a string s as input
it then converts s to an istringstream object called iss
now we can use the >> on iss, just like we use >> on cin
if s is formatted like a number like “349.03” or “-54”, then string_to_double will return an equivalent double
if s is not formatted like a number, e.g. it is some string like "x" or "3-2", then string_to_double will throw an error
using string_to_double is easy, e.g.:
string num = "3.1415926";
double x = string_to_double(num);
cout << 2 * x; // prints 6.2831852
now we can evaluate postfix expressions that use +:
#include "error.h"
#include <iostream>
#include <string>
#include <sstream>
#include <vector>
using namespace std;
// Converts string s to a double.
double string_to_double(const string& s) {
return stod(x);
}
string token; // global variable
vector<double> stack; // global variable
int main() {
cout << "Postfix expression evaluator\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
1 2 +
tos = 3
4 +
tos = 7
3 -1 -2 1 +
tos = -1
in this program, we are always going to be calling stack.back() and stack.pop_back() together, so lets write a helper function to simplify things a bit:
// 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:
#include "error.h"
#include <iostream>
#include <string>
#include <sstream>
#include <vector>
using namespace std;
// Converts string s to a double.
double string_to_double(const string& s) {
return stod(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\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 {
stack.push_back(string_to_double(token));
}
}
}
the code for handling + is now a little shorter and easier to read
with + working, it is to add similar 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
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 — that’s pretty good!
and it is useful (once you get used to postfix, at least)
lets add more features to our calculator
right now we print the top of the stack after every operator
that’s useful for debugging
but most of the time we usually only care about the final value of our calculation
so lets replace the top-of-stack printing code with 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 "."
to implement "." we re-write the main if-else-if statement:
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));
}
notice that the code has become even simpler!
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\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
it’s re-displayed the prompt whenever the top of the stack is printed:
Postfix expression evaluator
--> 14 6 + 2 3 + / .
tos = 4
--> 2 3 * 4 * 5 * .
tos = 120
-->
it’s distressingly easy to crash the current version of our evaluator
one wrong character and the program crashes:
Postfix expression evaluator
--> .
Segmentation fault (core dumped)
or:
Postfix expression evaluator
--> +
Segmentation fault (core dumped)
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
Note
On Linux, you can run your program with gdb (the GNU debugger) to get more information about a crash, e.g.:
$ run gdb
GNU gdb (Ubuntu 7.7.1-0ubuntu5~14.04.2) 7.7.1
# ... lots of info about GDB deleted
(gdb) run
Starting program: /home/tjd/postfix
Postfix expression evaluator
--> +
Program received signal SIGSEGV, Segmentation fault.
0x08049195 in pop () at postfix.cpp:26
26 double tos = stack.back();
This tells us that the segmentation fault occurred at line 26 of the program.
the problem with these examples is that our code assumes the stack is non- empty
right now our program crashes when we try to pop from an empty stack
but instead of crashing, it would be much more useful to print an error message like this:
Postfix expression evaluator
--> +
Error: + tried to pop an empty stack
-->
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) {
cmpt::error("Error: " << token << " tried to peek at an empty stack\n");
} else {
double tos = stack.back();
stack.pop_back();
return tos;
}
}
this doesn’t compile!
$ make postfix6
g++ -std=c++11 -Wall -Wextra -Werror -Wfatal-errors -Wno-sign-compare -Wnon-virtual-dtor -g postfix6.cpp -o postfix6
postfix6.cpp: In function ‘double pop()’:
postfix6.cpp:33:1: error: control reaches end of non-void function [-Werror=return-type]
}
^
compilation terminated due to -Wfatal-errors.
cc1plus: all warnings being treated as errors
make: *** [postfix6] Error 1
our C++ compiler options require that any function with a non-void return type must return a value
put in pop(), nothing is returned in the case when the stack is empty
so to get it to compile we must return a double
but which double should be returned in the error case?
the double that we return in the error case will be used as a signal to the calling code that pop() has failed
so that mean’s we can’t use any double value that might appear in a non- error calculation
but there is no such double!
so we are stuck: we must signal the error in some other way
error-handling is one of those unglamorous but extremely important topics
in real-world programs we always try to avoid, catch, or fix any errors that occur
one strategy to error handling is to simple ignore errors and let the program continue, e.g. the program might (eventually) crash, or it could just start producing wrong answers — almost anything could happen when things go wrong!
the main value of this strategy is that it is simple for the programmer to implement
but otherwise it is a terrible strategy
a better approach is to use a global error_code variable that functions like pop() can set when an error occurs
for example:
// ...
int error_code = 0; // global variable
// 0 means everything is okay
// ...
// remove and return the element of the stack
double pop() {
if (stack.size() == 0) {
cout << "Error: " << token << " tried to pop an empty stack\n";
error_code = 1; // set error flag
return 0;
} else {
double tos = stack.back();
stack.pop_back();
return tos;
}
}
now it’s up to the code that calls pop() to check if error_code has been set, e.g.:
// ...
if (token == "+") {
double b = pop();
if (error_code == 0) {
double a = pop();
if (error_code == 0) {
push(a + b);
} else {
error_code = 0; // reset error_code
}
} else {
error_code = 0; // reset error_code
}
}
// ...
unfortunately, as you can see, this approach tends to make your code messier
because of the error-handling code, it’s hard to see the main logic of the code
to deal with errors like this, C++ provides a special feature called exceptions
in general, an exception is an object that indicates an error
exception objects can be thrown and caught
when an error occurs, we throw an exception using throw
the exception will cause the program to crash unless it is caught somewhere using try/catch
the error function we are using in our program comes from our error.h header file
if you read that file you can see how error is implemented:
inline void error(const string& s)
{
throw std::runtime_error(s);
}
error uses a throw statement to throw a runtime_error exception object
when C++ throws an exception, the program will crash unless the exception is caught somewhere
we can use a try/catch block to catch an exception, e.g.:
try {
// ... code that might throw a runtime_error exception
} catch (runtime_error e) {
// ... code to do something when the exception occurs
}
we put whatever code we want into the try and catch blocks
generally, 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)
here’s how we can catch a call to error in our program:
if (token == "+") {
try {
double b = pop();
double a = pop();
push(a + b);
} catch (runtime_error e) {
cout << "Error: stack is empty\n";
cout << prompt;
}
}
either one of the calls to pop() could potentially throw a runtime_error exception
because it’s inside a try block, if either call to pop() throws an exception, then the flow of control immediately jumps to the catch part of the block — thus skipping over any statements in the try block that haven’t been executed yet
the source code is much simpler than the previous example that used a global error_code variable
no global variables or messy if-statements are needed
we can now re-write our program like this:
#include "error.h"
#include <iostream>
#include <string>
#include <sstream>
#include <vector>
using namespace std;
// Converts string s to a double.
double string_to_double(const string& s) {
return stod(x);
}
string token; // global variable
vector<double> stack; // global variable
const string prompt = "--> ";
// remove and return the element of the stack
double pop() {
if (stack.size() == 0) {
error("tried to pop an empty stack"); // throws an exception
return 0; // never called: only needed to satisfy the compiler
} else {
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 7\n";
cout << prompt;
while (cin >> token) {
if (token == "+") {
try {
double b = pop();
double a = pop();
push(a + b);
} catch (runtime_error e) {
cout << "Error: stack is empty\n";
cout << prompt;
}
} else if (token == "-") {
try {
double b = pop();
double a = pop();
push(a - b);
} catch (runtime_error e) {
cout << "Error: stack is empty\n";
cout << prompt;
}
} else if (token == "*") {
try {
double b = pop();
double a = pop();
push(a * b);
} catch (runtime_error e) {
cout << "Error: stack is empty\n";
cout << prompt;
}
} else if (token == "/") {
try {
double b = pop();
double a = pop();
push(a / b);
} catch (runtime_error e) {
cout << "Error: stack is empty\n";
cout << prompt;
}
} else if (token == ".") {
cout << "tos = " << stack.back() << "\n";
cout << prompt;
} else {
push(string_to_double(token));
}
}
}
unfortunately, our program does still not yet catch all errors
for example:
Postfix expression evaluator, version 7
--> .
Segmentation fault (core dumped)
look at the code for handling ".":
// ...
} else if (token == ".") {
cout << "tos = " << stack.back() << "\n";
cout << prompt;
} else {
// ...
we can see that stack.back() is called here
but our error-checking is only done in the pop() function
one way to fix this is to add a new stack function called peek() that returns a copy of the top of the stack without popping it
// return top of stack without removing it
double peek() {
if (stack.size() == 0) {
error("tried to peek at an empty stack");
return 0; // never called: needed to satisfy compiler
} else {
return stack.back();
}
}
// remove and return the element of the stack
double pop() {
double tos = peek();
stack.pop_back();
return tos;
}
in the main loop we can now re-write the code for handling ”.” like this:
// ...
} else if (token == ".") {
try {
cout << "tos = " << peek() << "\n";
} catch (runtime_error e) {
cout << "Error: stack is empty\n";
}
cout << prompt;
} else {
// ...
we’ve used try/catch blocks throughout the code
but it turns out, in this case, we only need one try/catch block where the entire large if-else-if statement goes inside the try block
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 << "Error: stack is empty\n";
cout << prompt;
} // catch
} // while
this really simplifies the code!
it nicely separates error-handling code from the main code of the application
it is not quite perfect, e.g. sometimes multiple error messages occur, e.g.:
Postfix expression evaluator
--> 6 * .
Error: stack is empty
--> Error: stack is empty
-->
we won’t fix this particular problem, but it is something you might want to think about
there’s one more kind of error that would be useful to recognize in our program
for example:
--> a b + .
Error: stack is empty
--> Error: stack is empty
--> Error: stack is empty
--> Error: stack is empty
a and b are unknown tokens — they are ignored by our program and not pushed on the stack
the stod function we’re using in string_to_double throws the special exception invalid_argument when it tries to convert a string that is not a number
for example, calling stod("a") throws an invalid_argument exception
stod can also throw an out_of_range exception in the case where the string is a number that is out of the range of a C++ double
so we’ll add two more catch clause in the main program to print specific error messages for different exceptions
#include "error.h"
#include <iostream>
#include <string>
#include <sstream>
#include <vector>
using namespace std;
// Converts string s to a double.
double string_to_double(const string& s) {
return stod(s);
}
string token; // global variable
vector<double> stack; // global variable
const string prompt = "--> ";
// return top of stack without removing it
double peek() {
if (stack.size() == 0) {
error("tried to peek at an empty stack");
return 0; // never called: needed to satisfy compiler
} else {
return stack.back();
}
}
// remove and return the element of the stack
double pop() {
double tos = peek();
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 10\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 << "Error: stack is empty\n";
cout << prompt;
} catch (invalid_argument e) {
cout << "Unknown token: \"" << token << "\"\n";
cout << prompt;
} catch (out_of_range e) {
cout << "Error: number out of range: \"" << token << "\"\n";
} // catch
} // while
} // main
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
let’s make two organizational changes to our program
first, we’ll add some comments to document the different parts of the program
////////////////////////////////////////////////
//
// This implements a postfix calculator.
//
////////////////////////////////////////////////
#include "error.h"
#include <iostream>
#include <string>
#include <sstream>
#include <vector>
using namespace std;
////////////////////////////////////////////////
//
// Global variables.
//
////////////////////////////////////////////////
string token; // global variable
vector<double> stack; // global variable
const string prompt = "--> ";
////////////////////////////////////////////////
//
// Helper functions.
//
////////////////////////////////////////////////
// ... just string_to_double for now ...
////////////////////////////////////////////////
//
// Stack functions.
//
////////////////////////////////////////////////
// ... peek, pop, push ...
////////////////////////////////////////////////
//
// Main function.
//
////////////////////////////////////////////////
int main() {
cout << "Postfix expression evaluator\n";
// ...
} // main
naming sections of code like this makes the program easier to understand
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():
// ...
////////////////////////////////////////////////
//
// Token processing functions.
//
////////////////////////////////////////////////
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 11\n";
cout << prompt;
while (cin >> token) {
try {
process_token();
} catch (runtime_error e) {
cout << "Error: stack is empty\n";
cout << prompt;
} catch (invalid_argument e) {
cout << "Unknown token: \"" << token << "\"\n";
cout << prompt;
} catch (out_of_range e) {
cout << "Error: number out of range: \"" << token << "\"\n";
} // catch
} // while
} // main
this change makes our main function much easier to read
it makes the logical structure of the error-handling easier to understand
lets add some more operators to our postfix evaluator
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”
dup 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 prints the 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
so we’ll put it in its own function:
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 << "\n";
}
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
Modify the behaviour of "." so that when the stack is empty 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,i.e. the square operator, to the evaluator. ^2 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. sin replaces the top element of the stack with its sine, and cos replaces the top element of the stack with its cosine. For example:
--> 2 sin .
tos = 0.909297
--> 3 cos .
tos = -0.989992
--> 15 sin ^2 15 cos ^2 + .
tos = 1
Modify the evaluator so that ";" works exactly the same thing as ".". 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 3 4 .
tos = 4
--> pop pop .
tos = 2
--> pstack
<tos=2, 1>
pop should cause an error message to be printed if it is called 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 0, or negative, then nothing happens. For example:
--> 1 2 3 .
tos = 3
--> -3 popn .
tos = 3
--> pstack
<tos=3, 2, 1>
If the parameter to popn is not an integer, then the digits after the decimal should be ignored. For example:
--> 1 9 8 2 .
tos = 2
--> 3.9 popn .
tos = 1
An error message should be printed if popn is called on an empty stack.
Add the copyn operator to the evaluator. copyn duplicates the top n elements of the stack, where n is the number on the top of the stack when copyn is called. For example:
--> 1 2 3 .
tos = 3
--> 2 copyn .
tos = 3
--> pstack
<tos=3, 2, 3, 2, 1>
If n is 0, or negative, then there nothing happens, 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
If there are fewer than two items on the stack, then print a helpful error message.
Add the size operator to the evaluator. size pushes the current size of the stack onto 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 to the evaluator. clear removes all the elements from the stack, thus making it empty. For example:
--> .
<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.