# Evaluating expressions using Reverse Polish Notation (2)

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() {
next();
}
else if (lookahead.sym == Op::left) {
next();
expression();
cerr << "missing )\n";
}
next();
}
else {
cerr << "\nunknown operator: "
}
}
```

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) {
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() {
target.push_number(Number{});
next();
index();
target.apply_operator(Op::uminus);
}
else {
index();
}
}

void ExpressionEvaluator::index() {
factor();
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.