Last time we developed a program that converted infix expressions with positive numbers to postfix, supporting the addition, subtraction, multiplication and division operators. We’re going to finish this program so that it handles unary-minus (therefore negative numbers), exponentiation and parentheses, as well as actually performing the evaluation through a new class called StackCalculator, inherited from our existing StackMachine. Small parts of example code follow, which indicate additions to the previous version, and the complete, new, working program is listed at the end of this article.
Due to the way the program was designed, with a recursive descent algorithm, adding support for (nested) parentheses is surprisingly straightforward, only requiring changes to function factor(). Here is the new version:
left = '(',
right = ')',
//...
void ExpressionEvaluator::factor() {
if (lookahead.sym == Op::number) {
target.push_number(lookahead.num);
next();
}
else if (lookahead.sym == Op::left) {
next();
expression();
if (lookahead.sym != Op::right) {
cerr << "missing )\n";
}
next();
}
else {
cerr << "\nunknown operator: "
<< static_cast<char>(lookahead.sym) << '\n';
}
}
Assuming that tokens left and right have been defined, the new code at lines 9-16 can be written, and follows a similar pattern for that in expression() and term(). In simple terms, finding Op::left indicates “start of expression”, so we start the process of parsing by calling next() once and then (recursively) calling expression(). Finally, as expression() can’t “eat” a closing parentheses we check for Op::right and call next() one more time.
Moving on to the StackCalculator class, the implementation is fairly straightforward as is the modified main() program, which carries on using StackPrinter too. Here is the code for both:
#include <stack>
#include <string>
#include <sstream>
//...
class StackCalculator final : public StackMachine {
stack<Number> stk;
ostream& out;
public:
StackCalculator(ostream& os = cout) : out{os} {}
virtual ~StackCalculator() {
out << "=> " << stk.top() << '\n';
}
virtual void apply_operator(Op op) override {
if (stk.size() < 2) {
cerr << "number expected\n";
return;
}
Number b = stk.top();
stk.pop();
Number a = stk.top();
stk.pop();
switch (op) {
case Op::add:
stk.push(a + b);
break;
case Op::subtract:
stk.push(a - b);
break;
case Op::multiply:
stk.push(a * b);
break;
case Op::divide:
if (b) {
stk.push(a / b);
}
else {
cerr << "divide by zero\n";
}
break;
default:
cerr << "unknown operator: "
<< static_cast<char>(op) << '\n';
break;
}
}
virtual void push_number(Number n) override {
stk.push(n);
}
};
//...
int main() {
for (;;) {
string input;
getline(cin, input);
if (input.empty()) {
break;
}
{
istringstream strm{ input };
StackPrinter sp;
ExpressionEvaluator eval1(sp, strm);
eval1.expression();
}
{
istringstream strm{ input };
StackCalculator sc;
ExpressionEvaluator eval2(sc, strm);
eval2.expression();
}
}
}
A few more Standard Library headers are needed, as well as suitable using statements (not shown). The new class StackCalculator at lines 5-49 has a std::stack<Number> member called stk, which is initially empty. The destructor (lines 10-12) simply prints out the top element of this stack; a one-element stack is the result of a well-formed expression parse. Member function push_number() at lines 46-48 pushed a single Number onto the top of this stack.
The only involved part of writing StackCalculator is the member function apply_operator() at lines 13-45 which is designed to pop two values off the stack, apply the correct operator, and then push the result back onto the top. Firstly we check that there are at least two values available, if not an error message is printed. Then we pop two operands called a and b, importantly the second one is fetched first. (Function stack::pop() does not return the element removed, so we need the result of stack::top() immediately beforehand.) Then a switch statement with a separate case for all of the operands seen so far handles the Math. The result is pushed back onto the stack straightaway.
The main() program at lines 51-71 now reads a std::string in a loop and sets up a suitable std::istringstream twice (this is used instead of std::cin). Careful use of object lifetimes defined by sub-scopes allows the “result” to be printed by eval2‘s destructor after the “working” from eval1.
Handling negative numbers and the exponent operator involves relatively few changes to the code as the functions for handling them (which we’ve called negative() and index()) fit into the call hierarchy between term() and factor(). Function term() needs both references to factor() changed to negative(); perhaps surprisingly this is the only code alteration needed, other than the new code.
Here are the new functions and other supporting code additions needed:
#include <cmath>
//...
exponent = '^',
uminus = '_',
//...
case Op::exponent:
stk.push(pow(a, b));
break;
case Op::uminus:
stk.push(-b);
break;
//...
void ExpressionEvaluator::negative() {
if (lookahead.sym == Op::uminus) {
target.push_number(Number{});
next();
index();
target.apply_operator(Op::uminus);
}
else {
index();
}
}
void ExpressionEvaluator::index() {
factor();
if (lookahead.sym == Op::exponent) {
next();
negative();
target.apply_operator(Op::exponent);
}
}
Lines 1-11 are the required additions to Op and StackCalculator::apply_operator(). Notice that a new operator is needed for uminus, we’ve chosen underscore. In Mathematics, unary-minus only takes one operand, but our StackCalculator class is hard-wired to always pop two. Thus we need to push a dummy value (line 15) which is guaranteed to never be used (line 10).
Member function negative() (lines 13-23) is very different from expression() and term() as we’ve decided that the unary-minus operator should be non-associative (instead of right-associative) therefore a loop is not necessary. Fixing this is left as an exercise (so the expression __2 would become valid). Member function index() (lines 25-32) uses head recursion instead of a loop (actually calling negative() not index() itself) in order provide right-associativity, which is correct. (The addition, subtraction, multiplication and divide operators are of course all left-associative.) The complete listing for the second version of the program is here.
In summary, we have extended an infix to postfix demonstrator into a fully blown calculator program, doubling its length in the process. This demonstrates the writing of a hand-written top-down (recursive-descent) expression parser compared to the table-driven (bottom-up) version described in the previous articles about flex and bison. Hopefully the reader will agree that even hand-written code is manageably complex and can in some ways be seen as a superior method to using a parser-generator. Have fun experimenting with (more complex) expressions and comparing the Reverse Polish Notation output with the expected result!
Note: If you really object to underscore representing unary-minus, change line 185 to:
if (lookahead.sym == Op::subtract) {
The context is still preserved and the StackPrinter will still show an underscore.
Resources: Download and browse the source code
Learn Modern C++ 