We’ve added a number of operators to our postfix evaluator. The basic pattern is always the same: give it a name (that hasn’t already been used), check for that name in the process_token‘s big if-else-if statement, and then perform the appropriate actions.
Now lets add some features that will require more thought: variables and (simple) user-defined functions.
Here’s an example of what we want to be able to do:
--> def square = dup * .
square: [dup *]
--> 8 square .
tos = 64
The first line defines the square function, and the second line shows an example of how to use it.
Here’s a function that calculates the area of a circle assuming the radius is on the top of the stack:
--> def circle_area = square 3.14 * .
circle_area: [square 3.14 *]
--> 1 circle_area .
tos = 3.14
--> 4.22 circle_area .
tos = 55.9184
Notice that we are calling another user-defined function within circle_area.
We can also use def to give values to variables, e.g.:
--> def pi = 3.14 .
pi: [3.14]
--> def circle_area = square pi * .
circle_area: [square pi *]
From the examples above, we can see that function definitions have this general form:
def name : <space-separated list of operands and operators> .
In other words, functions consist of a name and a sequence of strings. So it is natural to represent a function’s name as a string, and its body as a vector<string>.
Every function we define needs its own name string and body vector<string>. The natural way to represent this in C++ is to use an object that stores both a functions name and its body. In C++, we can use struct to define objects:
struct Function {
string name;
vector<string> body;
};
This defines a struct called Function that we can use like this:
Function f; // create a new Function object
f.name = "square"; // set its name
f.body.push_back("*"); // add some strings to the body
f.body.push_back("dup");
We say that f is a variable of type Function. Since we defined Function ourselves, we also say that Function is a user-defined type. You access the name and body of f using the ”.”-notation, i.e. f.name is the name of f, and f.body is its body.
Every time you create a new Function object, C++ reserves new memory locations for that function’s name and body. That means that every Function objects has its own unique name and body:
// ... f defined as above
Function g;
g.name = "twice";
vector<string> vs2;
vs2.push_back("*");
vs2.push_back("2");
g.body = vs2;
g and f are both objects of type Function, and both have their own personal name and body.
We can also create a vector of Function objects like this:
vector<Function> functions;
functions.push_back(f);
functions.push_back(g);
Our postfix evaluator will save user-defined functions as Function objects and store them in a vector<Function>.
Defining your own types using structs (and classes) is one of the major features of C++, and of object-oriented programing (OOP) in general. Object-oriented languages let you create new types of objects.
Now lets add the Function struct to our program. Add the following just before the global variables section:
/////////////////////////////////////////////////////////////
//
// structs and classes
//
/////////////////////////////////////////////////////////////
// represents a postfix function
struct Function {
string name;
vector<string> body;
};
Then, since we will need somewhere to store the user-defined functions, we add the variable functions to our global variables:
// ...
/////////////////////////////////////////////////////////////
//
// Global variables
//
/////////////////////////////////////////////////////////////
string token;
vector<double> stack;
const string prompt = "--> ";
vector<Function> functions;
// ...
Next we need to add some code to process_token to recognize the def operator. Lets use this as an example to work from:
def square = dup * .
Lets agree that a function definition in our postfix evaluator must follow these rules:
Since a function definition always starts with def, we need to check for the token def in process_token:
void process_token() {
// ...
} else if (token == "def") {
// ... code to handle a function definition ...
}
// ...
}
Following the list of rules for a function definition, we can write the code for processing a def:
// ...
} else if (token == "def") {
Function f;
cin >> f.name; // read the name
string eq;
cin >> eq; // read the "="
// read the body, i.e. all the tokens up to "."
string t;
cin >> t;
while (t != ".") {
f.body.push_back(t);
cin >> t;
}
functions.push_back(f);
}
// ...
Assuming the function definition is properly formatted, then this code stores the function as a Function object in the functions vector. For the moment we’ve ignored error-checking.
Lets add a couple of functions for printing the contents of a Function object in a human-readable way:
/////////////////////////////////////////////////////////////
//
// Generic helper functions
//
/////////////////////////////////////////////////////////////
// ...
void print(const vector<string>& v) {
const int n = v.size();
if (n == 0) ; // print nothing for an empty vector
else if (n == 1) cout << v[0];
else { // n >= 2
cout << v[0];
for(int i = 1; i < v.size(); ++i) // note that i starts at 1
cout << " " << v[i];
}
}
// ...
/////////////////////////////////////////////////////////////
//
// Program-specific helper functions
//
/////////////////////////////////////////////////////////////
// ...
void print(Function f) {
cout << f.name << ": [";
print(f.body);
cout << "]";
}
The helper function print(vector<string> v) takes any vector<string> and prints its contents to the screen, separating each string with a space. print(Function f) is specific to this program and prints a function object’s name and body. The body is wrapped in [ and ] to make it easier to recognize.
Notice that we’ve just defined two different functions with the same name, print. Functions can have the same name in C++ as long as they have different parameters, as is the case here. C++ never gets confused about which function to call because it can tell from the type of the input parameters: print(x) is call to print(vector<string> v) if x is an object of type vector<string>, and a call to print(Function f) if x is of type Function.
Now we can use print to give the user some feedback about the function they entered:
} else if (token == "def") {
// ...
// print the function as feedback for the user
print(f);
cout << endl;
cout << prompt;
}
After compiling the program, we can now type function definitions:
--> def square = dup * .
square: [dup *]
--> def pi = 3.14 .
pi: [3.14]
--> def circle_area = square pi * .
circle_area: [square pi *]
The next step is to get functions to execute when called.
Like most other programming languages, our postfix evaluator distinguishes between built-in operators and user-defined functions. Our built-in operators are all encoded directly into the process_token function, while all the user-defined functions are stored in the functions vector.
Think for a moment about how an operator is recognized. Suppose we type some string x into our evaluator:
--> x .
Consider the possibilities for x:
Our program already handles the first two possibilities, and to get it to handle the third will require some re-organization that is more substantial than implementing a new function. We need to take care to ensure that after implementing this change our program still works as expected: often changes to the fundamental structure of a program end up “breaking” code that worked fine before the change. So we will need to thoroughly test our evaluator after getting functions working.
This requires a change to the basic logic of process_token that is more substantial than adding a new built-in function. We need to take care to ensure that after implementing this change our program still works as expected: often changes to the fundamental structure of a program end up “breaking” code that worked fine before the change. So we will need to thoroughly test our evaluator after getting functions working.
Lets sketch out the new logic of the new process_token in pseudocode (i.e. English-like code):
Writing out logic like this is a good way to help clarify our thinking. Plus it acts as a guide for writing the C++ code.
Once we’ve recognized that a token is a user-defined function, then we execute it by processing each token in its body one at time. The body tokens could be numbers, built-in operators, or even other user-defined functions, and so we will need to recursively call process_token() to handle them.
Here is the code:
void process_token() {
if (token == "+") {
double b = pop();
double a = pop();
push(a + b);
}
// ... many else-if statements skipped ...
} else if (token == "def") {
// ... code for defining a function ...
} else {
// check to see if token is the name of a user-defined function
for(int i = 0; i < functions.size(); ++i) {
Function f = functions[i];
if (token == f.name) {
// found a matching user-defined function, so execute it
// by processing each token in its body
for(int j = 0; j < f.body.size(); ++j) {
token = f.body[j];
process_token(); // recursive call!
}
return; // immediately jump out of process_token
}
}
// we only get to this line if token matches nothing in the
// functions vector: we assume token is a number
push(string_to_double(token));
} // if
} // process_token
The new code we’ve added here first scans through the functions vector looking to see if the current token matches the name of any user-defined function. If so, then it execute the body of that function by calling process_token on each token in the body. Notice that we are calling process_token recursively, i.e. process_token is calling itself. When you think about it, this is exactly what we want to do because the tokens in the body of the user-defined function could be built-in operators, user-defined functions, or numbers.
Note
Recursion turns out to be a deep and interesting topic in computer science, and we will have more to say about it later in the course. For now, though, we just use it as a simple and natural way to solve an otherwise difficult problem.
Finally, if no user-defined function matches the token, then we assume token is a double and push it on the stack.
Here’s a sample of what we can now do with our evaluator:
--> def square = dup * .
square: [dup *]
--> 5 square .
tos = 25
--> def pi = 3.14 .
pi: [3.14]
--> pi square .
tos = 9.8596
--> def circle_area = square pi * .
circle_area: [square pi *]
--> 1 circle_area .
tos = 3.14
--> 2 circle_area .
tos = 12.56
-->
If you can live with the fact that the expressions are all in postfix order, then we’ve done something quite impressive: we created a general-purpose calculator that lets you define and use your own functions. And none of the code we used to do it was that complex on its own.
There’s still a lot that can be done to improve this program, but we will stop here and move on to other topics. If you are curious about how to evaluate regular infix expressions, then take a look at chapters 6 and 7 of the textbook.
Note
If you are using Linux, the dc desktop calculator can be run at the command-line. dc is postfix calculator with lots of useful features, including arbitrarily large/small integers. Type man dc to learn more about it.
#include "std_lib_cmpt125.h"
///////////////////////////////////////////////////////////
//
// structs and classes
//
///////////////////////////////////////////////////////////
struct Function {
string name;
vector<string> body;
};
///////////////////////////////////////////////////////////
//
// Global variables
//
///////////////////////////////////////////////////////////
string token; // the token being read in; global
vector<double> stack; // global variable
const string prompt = "--> ";
vector<Function> functions; // user-defined functions
///////////////////////////////////////////////////////////
//
// General-purpose helper function
//
///////////////////////////////////////////////////////////
double string_to_double(const string& s) {
istringstream iss(s);
double x;
if (!(iss >> x))
error("conversion error");
return x;
}
void print(const vector<string>& v) {
const int n = v.size();
if (n == 0) ;
else if (n == 1) cout << v[0];
else {
cout << v[0];
for(int i = 1; i < n; ++i) {
cout << " " << v[i];
}
}
}
///////////////////////////////////////////////////////////
//
// Program-specific helper functions
//
///////////////////////////////////////////////////////////
double peek() {
if (stack.size() == 0) {
error("Can't peek an empty stack.");
}
return stack.back();
}
double pop() {
double tos = peek();
stack.pop_back();
return tos;
}
void push(double x) {
stack.push_back(x);
}
void print_stack() {
const int n = stack.size();
if (n == 0) cout << "<empty stack>";
else if (n == 1) cout << "<tos=" << peek() << ">";
else {
cout << "<tos=" << peek();
for(int i = n - 2; i >= 0; --i) {
cout << ", " << stack[i];
}
cout << ">\n";
}
}
void print(Function f) {
cout << f.name << ": [";
print(f.body);
cout << "]";
}
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() << endl;
cout << prompt;
} else if (token == "inc") {
double b = pop();
push(b + 1);
} else if (token == "dec") {
double b = pop();
push(b - 1);
} else if (token == "dup") {
double b = peek();
push(b);
} else if (token == "pstack") {
print_stack();
} else if (token == "def") {
Function f;
cin >> f.name;
string eq;
cin >> eq;
string t;
cin >> t;
while (t != ".") {
f.body.push_back(t);
cin >> t;
}
functions.push_back(f);
print(f);
cout << endl;
cout << prompt;
} else {
// check if token is a user-defined function
for(int i = 0; i < functions.size(); ++i) {
Function f = functions[i];
if (f.name == token) {
//cout << "user-defined function\n";
for(int j = 0; j < f.body.size(); ++j) {
token = f.body[j];
process_token();
}
return; // jump out of process_token
}
}
// assume token is a number
stack.push_back(string_to_double(token));
}
}
///////////////////////////////////////////////////////////
//
// Main function
//
///////////////////////////////////////////////////////////
int main()
{
cout << "Postfix evaluator\n";
cout << prompt;
while (cin >> token) {
try {
process_token();
} catch (runtime_error e) {
cout << e.what() << endl;
cout << prompt;
}
} // while
} // main
Add a built-in operator called functions that lists all the user-defined functions. For example:
--> functions
square: [dup *]
pi: [3.14]
circle_area: [square pi *]
If there are no user-defined functions, then functions should return a message saying so.
Modify the evaluator so that ";", not ".", is used to terminate a function definition:
--> def square = dup * ;
Add code to the def part of the else-if-else statement in process_token that ensures that def cannot be added to the body of the function being defined (i.e. don’t allow a function to be defined within a function). Throw an error message if def appears in the function body.
Add code to the def part of the else-if-else statement in process_token that ensures that the name of a user-defined function cannot be a number or a built-in operator. Throw a helpful error message if the user tries to create a function with an illegal name.
Add a new built-in operator called help that returns a brief help message and example of how to use a particular operator. For example:
--> help +
+ pops the top two elements of the stack and pushes their sum
--> help dup
dup copies the current TOS and pushes it
--> help .
. prints the current TOS
--> help 3.14
3.14 is a number
--> help
type help X, where X is any one of the following built-in operators:
+ - * / . pstack def [... plus all the other built-in operators ...]