Case Study: A Reverse-Polish Calculator
The first serious scientific calculators made by Hewlett-Packard had an eccentric way of entering expressions backward. You entered the numbers and then applied the operation. It is a classic use of the stack idea: Two numbers are pushed onto the stack, and then a multiply function operates on these numbers and replaces them with the result. Hewlett-Packard's many fans claimed that they could type in expressions faster than people using good old-fashioned infix notation because they did not need parentheses. Infix notation puts the operator between the operands, like 10 + 20. Reverse Polish Notation (RPN—Polish as in the nationality) writes the operator afterward, like 10 20 +. A surprisingly popular programming language called FORTH (originally developed to point telescopes) used RPN. So we have:
In this case study, you need to write a small program that lets Hewlett-Packard calculator fans do arithmetic. If you give the program a reverse-Polish expression as a command line, it evaluates the expression immediately; otherwise, it assumes that expressions are read from standard input and terminated with a period (.), which means “display the value.”
Using Stacks
A stack module is defined in stack.cpp. If there are already two numbers on the stack, then the stack module will perform the addition, as follows:
;> Stack::push(10); Stack::push(20); ;> Stack::push( Stack::pop() + Stack::pop() ); ;> Stack::tos(); // top of stack (double) 30.
The following example is a first version of the reverse-Polish calculator RP —or at least the first version that worked.
If you write the operations as in the preceding example—for example, push(pop() / pop())—the operands end up in the wrong order. (Try it and see. ) Another surprise with this example is that passing 3 5 * as a command line did not work. When I dumped out the command-line string, it had every file in the directory! By default, as you saw earlier, C++ programs compiled with GCC expand any wildcards, such as *. After some scratching around in the runtime library source, I found a way to switch this off.
The actual calculator is contained in the eval() function. It is basically a while loop that reads in tokens separated by spaces. If the token's first character is a digit, then RP assumes it is a number and converts the string to a number. This number is then pushed onto the stack. If the token is “.”, then it means that the expression is finished and RP returns the top of the stack. (So if you gave it “10 .” it would push 10, pop 10, and then display this value.) Otherwise, if the token is an operator, then RP applies that operation to the top two elements of the stack. Finally, functions like sin() and cos() are implemented.
// RP.CPP – Reverse-Polish Calculator vs 1.0
#include <iostream>
#include <stringstream>
#include <string>
#include <cstdlib>
#include <cmath>
#include <cctype>
using namespace std;
#include "stack.h"
double str2float(string s)
{
return atof(s.c_str());
}
double eval(istream& in)
{
using namespace Stack;
string tok;
while (in >> tok) {
if (isdigit(tok[0])) push(str2float(tok));
else if (tok == ".") return pop();
else {
double val = pop();
if (tok == "+") push(pop() + val);
else if (tok == "-") push(pop() - val);
else if (tok == "*") push(pop() * val);
else if (tok == "/") push(pop() / val);
else if (tok == "sin") push(sin(val));
else if (tok == "cos") push(cos(val));
}
}
return pop();
}
// this prevents 'globbing' of the command line
// in Mingw32. (The other compilers have it off by default)
// (see comment in init.c from the runtime source)
int _CRT_glob = 0;
int main(int argc, char *argv[])
{
if (argc > 1) { // command-line arguments
string exp;
for(int i = 1; i < argc; i++) { // stitch the arguments together as a string
exp += ' ';
exp += argv[i];
}
istringstream ins(exp); // and pass the string to eval() as a stream
cout << eval(ins) << endl;
} else {
for(;;) // pass standard input to eval()
cout << eval(cin) << endl;
}
return 0;
}
To build the reverse-Polish calculator, you need to first build the stack module with -c. Then compile rp.cpp and link it with stack.o, using the following commands:
C:ucwchap4>c++ -c stack.cpp C:ucwchap4>c++ rp.cpp stack.o C:ucwchap4>a 10 5 / 2 C:ucwchap4>a 1.2 sin 1.3 cos + . 1.19954 ^C
In the preceding example, this program is first run with command-line arguments, which main() builds up into a single string by using spaces. Because eval() expects an input stream, you use istringstream to pass it the resulting string.
If there are no command-line arguments, eval() is passed the standard input stream cin. But because you have a loop that goes on forever here (because cin >> tok will always succeed), you have to stop the program by using Ctrl+C. This is not very elegant. (Fortunately, you can nearly always get yourself out of trouble this way.)
Adding Error-checking to RP
To make this program more solid, you need to pick a character, such as 'q' to mean quit, and you need to look out for several error conditions:
Although it's unlikely that the stack will overflow, it's easy for the stack to underflow, which means you are trying to pop an empty stack.
You need to watch for division by floating-point zero, which is not a runtime error by default.
You need to watch for domain errors (for example, trying to calculate the square root of a negative number).
Users would also like to define variables. To set pi to 3.1412, you use 3.1412 pi =, which is consistent with RPN but not convenient. It is tricky because we meet the variable pi before we meet =. You can use a map from strings to doubles to define variables. That is, you can store the value of pi as value_map["pi"]. Fortunately, this map always has a sensible value, so you push the value of any token that begins with a letter (see the line ending with [4] in the following example), and keep track of both the token and the value that was on the stack. Then when you encounter =, these values are available (notice the line ending with [5]).
double non_zero(double d)
{
if (d == 0.0) throw string("must not be zero");
return d;
}
double non_negative(double d)
{
if (d <= 0.0) throw string("must not be negative");
return d;
}
double pops()
{
if (Stack::empty()) throw string("Stack empty!");
return Stack::pop();
}
map<string,double> value_map;
double eval(istream& in)
{
using namespace Stack;
string tok, last_tok;
double last_val=0,val;
while (in >> tok) {
if (isdigit(tok[0])) push(str2float(tok));
else if (tok == ".") return pops(); // end of expr
else if (tok == "q") throw 0; // finished! [1]
else {
val = pops();
if (tok == "+") push(pops() + val);
else if (tok == "-") push(pops() - val);
else if (tok == "*") push(pops() * val);
else if (tok == "/") push(pops() / non_zero(val)); //[2]
else if (tok == "sin") push(sin(val));
else if (tok == "cos") push(cos(val));
else if (tok == "sqrt")
push(sqrt(non_negative(val))); //[3]
else if (tok == "dup") { push(val); push(val); }
else if (tok == "=")
value_map[last_tok] = last_val; //[4]
else if (isalpha(tok[0])) {
push(value_map[tok]); //[5]
last_tok = tok;
last_val = val;
}
}
}
return pop(); // ran out of input...
}
The three value-checking functions are interesting (see the lines that end with [2] and [3]). It is difficult for a function like non_zero() to return a value that means “bad value,” since what floating-point value could you choose to mean an error? So non_zero(), non_negative(), and pops() all throw an appropriate exception. Wherever you would use Stack::pop(), you instead use pops(). I may now say sqrt(non_negative(val)), and sqrt() will never be called with a negative argument. Instead, an exception will always be thrown. The point is that error-checking need not involve lots of ugly if statements.
The function eval() also needs to indicate that the user is tired and has terminated the session by using q, so you throw another kind of exception (an int), which guarantees that normal termination is different from an error. You then call eval() from an error-checked version function called safe_eval():
double safe_eval(istream& in)
{
try {
return eval(in);
} catch(string err) {
cerr << "error: " << err << endl;
return 0.0;
}
}
Notice that safe_eval() does not catch the int that eval() throws if the user types (q). This means that the caller of safe_eval() can catch the int exception and bail out of the loop, as in the following code:
try {
for(;;)
cout << safe_eval(cin) << endl;
} catch(int ierr) {
// jump out of loop!
}
Some people do not think it's a good idea to use exceptions for normal termination of a program. They argue that exceptions must be at least unusual, if not actually errors. But this example demonstrates how using different kinds of exceptions can enable you to specify precisely where you want an error to be handled. The function safe_eval() is only interested in trapping expression errors (and telling the user about them); it passes through the quit message that eval() sends to the main() function.
You can try making several improvements to the reverse-Polish program. For example, you can handle trigonometry with degrees, not radians. It would be useful to save any defined variables to a file (remember that you can iterate over a map). Even if doing arithmetic backward isn't your cup of tea, the idea of a stack machine is very common in computer science. On Intel platforms, the floating-point machine instructions are precisely comprised of push, pop, and operations that act on a stack.