let’s add some more features to our postfix evaluator
specifically, lets add user-defined variables and user-defined functions
to do this, lets first write out how we want our program to work when it’s done — a very useful design technique!
here’s an example of what we want to be able to do:
--> def square = dup * .
square: [dup *]
--> 8 square .
tos = 64
the line beginning with def indicates a function definition
it creates a function named square whose body consists of dup and *
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 the square function is being called inside 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> .
this suggests that we define a function as follows:
struct Function {
string name;
vector<string> body;
};
we can use Function 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
we defined Function ourselves, so it is an example of 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
we can also create a vector of Function objects like this:
vector<Function> functions;
functions.push_back(f); // assumes f and g are already defined
functions.push_back(g); // variables of type Function
this is how our postfix evaluator will save user-defined functions
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 we add a new global variable called functions to store all the user- defined functions:
// ...
/////////////////////////////////////////////////////////////
//
// 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);
}
// ...
please note that we are purposely ignoring error-checking to keep the code simple
in a real language, it would be important to check for errors and issue helpful messages
that turns out to be tricky to do, and the result is that code is usually more complicated
so, in the name of learning, we will skip the error handling
lets add a couple of functions for printing the contents of a Function object in a human-readable way:
void print(const vector<string>& v) {
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];
}
}
void print(const Function& f) {
cout << f.name << ": [";
print(f.body);
cout << "]";
}
notice these functions are both named print
it’s okay to have two functions with the same name in C++, as long as they take different types of input (so that C++ can figure out which one should be called)
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;
}
now our calculator lets us define functions!
--> def square = dup * .
square: [dup *]
--> def pi = 3.14 .
pi: [3.14]
--> def circle_area = square pi * .
circle_area: [square pi *]
of course, we can’t use them yet
but they are there in the functions vector
our postfix evaluator distinguishes between built-in functions and user- defined functions
the built-in functions are all encoded directly into the process_token function
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
to get it to handle the third will require some re-organization
re-organizing code can often cause working code to stop working
so we will need to test the program carefully after our changes
lets sketch out the new logic of process_token in pseudocode (i.e. English-like code):
here’s the code:
void process_token() {
if (token == "+") {
double b = pop();
double a = pop();
push(a + b);
}
// ... many else-if statements checking for tokens 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 for-loop inside the else-part searches the functions vector for a function that matches the name of the token
if it makes a match, then it executes the body of the function
the execution works by setting the global token variable to be the next token in the body, and then recursively calling process_token
a function is said to be recursive when it calls itself, i.e. process_token is recursive because it contains a call to itself
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.
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
-->
// postfix.cpp
////////////////////////////////////////////////
//
// A postfix calculator.
//
////////////////////////////////////////////////
#include "error.h"
#include <iostream>
#include <string>
#include <vector>
using namespace std;
////////////////////////////////////////////////
//
// structs and classes
//
////////////////////////////////////////////////
// represents a postfix function
struct Function {
string name;
vector<string> body;
};
////////////////////////////////////////////////
//
// Global variables.
//
////////////////////////////////////////////////
string token; // global variable
vector<double> stack; // global variable
const string prompt = "--> ";
vector<Function> functions;
////////////////////////////////////////////////
//
// Helper functions.
//
////////////////////////////////////////////////
// Converts string s to a double.
double string_to_double(const string& s) {
return stod(s);
}
void print(const vector<string>& v) {
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];
}
}
void print(const Function& f) {
cout << f.name << ": [";
print(f.body);
cout << "]";
}
////////////////////////////////////////////////
//
// Stack functions.
//
////////////////////////////////////////////////
// return top of stack without removing it
double peek() {
if (stack.size() == 0) {
cmpt::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);
}
////////////////////////////////////////////////
//
// Token processing functions.
//
////////////////////////////////////////////////
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";
}
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 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") {
// define a new function
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);
// print the function as feedback for the user
print(f);
cout << "\n";
cout << prompt;
} 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
} // if
} // for
// we only get to this part if the token is not either a built-in
// function, or a user-defined function
push(string_to_double(token));
} // if
}
////////////////////////////////////////////////
//
// Main function.
//
////////////////////////////////////////////////
int main() {
cout << "Postfix expression evaluator\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
} // 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 ...]