/*
* This example code shows how to use a class hierarchy to implement a
* simple calculator. For simplicity, we've put all the code in one file.
*
* The design is as follows:
* We have an abstract class called Expression, which has two subclasses:
* Number and BinaryExpression. Number is a simple number, and BinaryExpression
* is an expression that has two subexpressions and an operator.
*
* In this version, we have added printing to the Expression hierarchy, and
* a parser to create expressions from strings. This means we can write
* a little interactive calculator program.
*/
#include <iostream>
#include <string>
#include <type_traits>
#include <regex>
#include <iterator>
#include <stdexcept>
#include <sstream>
#include <cmath>
#include <cstddef>
#include <cctype>
// Abstract base class
class Expression {
public:
virtual ~Expression() = default;
virtual double evaluate() const = 0;
virtual void printToStream(std::ostream& os) const = 0;
};
std::ostream& operator<<(std::ostream& os, const Expression& e) {
e.printToStream(os);
return os;
}
// Derived class #1: Number
class Number : public Expression {
public:
explicit Number(double value);
~Number() override = default;
double evaluate() const override;
void printToStream(std::ostream& os) const override;
private:
double value_;
};
Number::Number(double value) : value_{value} {
// Nothing (else) to do
}
double Number::evaluate() const {
return value_;
}
void Number::printToStream(std::ostream& os) const {
os << value_;
}
// Derived class #2: BinaryExpression
enum Operator { PLUS, MINUS, TIMES, DIVIDE };
class BinaryExpression : public Expression {
public:
BinaryExpression(Operator op, Expression* left, Expression* right);
~BinaryExpression() override;
// disallow copying and assignment
BinaryExpression(const BinaryExpression&) = delete;
BinaryExpression& operator=(const BinaryExpression&) = delete;
double evaluate() const override;
void printToStream(std::ostream& os) const override;
private:
Operator op_;
Expression* left_;
Expression* right_;
};
BinaryExpression::BinaryExpression(Operator op, Expression* left,
Expression* right)
: op_{op}, left_{left}, right_{right} {
// Nothing (else) to do
}
BinaryExpression::~BinaryExpression() {
delete left_;
delete right_;
}
double BinaryExpression::evaluate() const {
double leftValue = left_->evaluate();
double rightValue = right_->evaluate();
switch (op_) {
case PLUS:
return leftValue + rightValue;
case MINUS:
return leftValue - rightValue;
case TIMES:
return leftValue * rightValue;
case DIVIDE:
return leftValue / rightValue;
default:
// should never get here
throw std::logic_error("Unknown operator");
}
}
void BinaryExpression::printToStream(std::ostream& os) const {
os << "(";
left_->printToStream(os);
switch (op_) {
case PLUS:
os << " + ";
break;
case MINUS:
os << " - ";
break;
case TIMES:
os << " * ";
break;
case DIVIDE:
os << " / ";
break;
default:
// should never get here
throw std::logic_error("Unknown operator");
}
right_->printToStream(os);
os << ")";
}
/*
* Expressions can be parsed using the following EBNF grammar:
*
* expr ::= term { ('+' | '-') term }
* term ::= factor { ('*' | '/') factor }
* factor ::= number | '(' expr ')'
* number ::= [+-]?[0-9]+(.[0-9]+)?([eE][+-]?[0-9]+)?
*
* Our parser is implemented as a class, where the constructor takes a
* string and the parse() method returns an Expression* (which the caller
* then owns).
*
* Internally, it uses recursive descent parsing, with a number of helper
* functions based on the grammar above.
*/
class Parser {
public:
explicit Parser(const std::string& input);
Expression* parse();
private:
Expression* parseExpr();
Expression* parseTerm();
Expression* parseFactor();
Expression* parseNumber();
void skipWhitespace();
bool match(char c);
std::string input_;
size_t pos_;
};
Parser::Parser(const std::string& input) : input_{input}, pos_{0} {
// Nothing (else) to do
}
Expression* Parser::parse() {
pos_ = 0;
Expression* result = parseExpr();
skipWhitespace();
if (pos_ != input_.length()) {
throw std::invalid_argument("Unexpected character: "
+ input_.substr(pos_));
}
return result;
}
Expression* Parser::parseExpr() {
Expression* result = parseTerm();
while (true) {
skipWhitespace();
if (match('+')) {
Expression* right = parseTerm();
result = new BinaryExpression(PLUS, result, right);
} else if (match('-')) {
Expression* right = parseTerm();
result = new BinaryExpression(MINUS, result, right);
} else {
break;
}
}
return result;
}
Expression* Parser::parseTerm() {
Expression* result = parseFactor();
while (true) {
skipWhitespace();
if (match('*')) {
Expression* right = parseFactor();
result = new BinaryExpression(TIMES, result, right);
} else if (match('/')) {
Expression* right = parseFactor();
result = new BinaryExpression(DIVIDE, result, right);
} else {
break;
}
}
return result;
}
Expression* Parser::parseFactor() {
skipWhitespace();
if (match('(')) {
Expression* result = parseExpr();
skipWhitespace();
if (!match(')')) {
throw std::invalid_argument("Expected ')'");
}
return result;
} else {
return parseNumber();
}
}
Expression* Parser::parseNumber() {
skipWhitespace();
// We use std::regex here to check if the next characters are a number.
// We allow numbers to start with a '+' or '-' sign, and full floating
// point notation is allowed.
static const std::regex numberRegex(
"^[+-]?[0-9]+(\\.[0-9]+)?([eE][+-]?[0-9]+)?");
std::smatch results;
auto startIter = input_.cbegin() + pos_;
auto endIter = input_.cend();
if (std::regex_search(startIter, endIter, results, numberRegex)) {
pos_ += results[0].length();
return new Number(std::stod(results[0]));
} else {
throw std::invalid_argument("Expected number, instead saw: "
+ input_.substr(pos_));
}
}
void Parser::skipWhitespace() {
while (pos_ < input_.length() && std::isspace(input_[pos_])) {
++pos_;
}
}
bool Parser::match(char c) {
if (pos_ < input_.length() && input_[pos_] == c) {
++pos_;
return true;
}
return false;
}
int main() {
std::string input;
std::cout << "(enter a blank line to quit)" << std::endl;
while (std::cin.good()) {
try {
std::cout << "Enter an expression: ";
std::getline(std::cin, input);
if (input.empty()) {
break;
}
Parser parser{input};
Expression* expr = parser.parse();
std::cout << "Will evaluate: " << *expr << std::endl;
double result = expr->evaluate();
std::cout << "Result: " << result << std::endl;
delete expr;
} catch (const std::invalid_argument& e) {
std::cerr << "Error: " << e.what() << std::endl;
}
}
return 0;
}
