Mathematical expression evaluator (C++)

Question

I'm new to C++ and I decided to experiment with the language, by writing a mathematical expression evaluator, using the Shunting-Yard algorithm. A design choice that may stand out as weird is the fact that the parser creates an abstract syntax tree rather than just converting it to Reverse Polish Notation. The reason for this is that I wanted to experiment with the language by creating a data structure.

Any form of feedback would be appreciated, whether it be about design, code style, performance, memory management (one thing I was concerned about while writing this was whether I was making things get copied unnecessarily), or anything in between.

#include <iostream>
#include <string>

#include "ast_generator.h"
#include "evaluator.h"

int main() {
  std::string expression;

  while (true) {
    std::cout << "Enter expression: ";
    std::getline(std::cin, expression);

    ExpressionEvaluator evaluator;
    std::unordered_map<std::string, double> variable_values = {
      {"x", 2},    
    };

    try {
      std::cout << evaluator.evaluate(expression, std::move(variable_values)) << "\n";
    } catch (const ExpressionEvaluator::evaluator_error& ex) {
      std::cerr << ex.what() << "\n";
    } catch (const AstGenerator::parser_error& ex) {
      std::cerr << ex.what() << "\n";
    }
  }

  return 0;
}

// ast_generator.cpp
#include <iostream>
#include <sstream>

#include "ast_generator.h"

AstGenerator::AstGenerator () {
  add_operator(static_cast<Operator>('+'), OperatorDefinition(1, Associativity::left));
  add_operator(static_cast<Operator>('-'), OperatorDefinition(1, Associativity::left));
  add_operator(static_cast<Operator>('+'), OperatorDefinition(3, Associativity::right, OperatorType::unary));
  add_operator(static_cast<Operator>('-'), OperatorDefinition(3, Associativity::right, OperatorType::unary));
  add_operator(static_cast<Operator>('*'), OperatorDefinition(2, Associativity::left));
  add_operator(static_cast<Operator>('/'), OperatorDefinition(2, Associativity::left));
  add_operator(static_cast<Operator>('^'), OperatorDefinition(4, Associativity::right));
}

OperatorDefinition AstGenerator::get_operator_definition (std::shared_ptr<OperatorToken> operator_token) {
  if (operator_token->operator_type == OperatorType::unary) {
    return _unary_operator_definitions[operator_token->value];
  } else {
    return _binary_operator_definitions[operator_token->value];
  }
}

void AstGenerator::output_operator (AstNodeType node_type, bool force_unary) {
  auto token_as_operator = std::dynamic_pointer_cast<OperatorToken>(_operator_stack.top());
  auto new_node = std::make_shared<AstNode>(node_type, _operator_stack.top());
  int num_arguments = force_unary || token_as_operator->operator_type == OperatorType::unary ? 1 : 2;

  if (_output.size() < num_arguments) {
    throw parser_error("Error: Operator without corresponding operand");
  }

  for (int i = 0; i < num_arguments; i++) {
    new_node->add_child(_output.top());
    _output.pop();
  }

  _output.push(new_node);

  _operator_stack.pop();
}

void AstGenerator::add_operator (Operator oper, const OperatorDefinition& definition) {
  if (definition.type == OperatorType::unary) {
    _unary_operator_definitions[oper] = definition;
  } else {
    _binary_operator_definitions[oper] = definition;
  }
}

void AstGenerator::tokens_from_expression (std::istream& expression) {
  double n;

  while (!expression.eof()) {
    std::streampos old_position = expression.tellg();

    char next_char = expression.peek();
    bool can_be_number = next_char != static_cast<char>(Operator::sub) && next_char != static_cast<char>(Operator::add);

    if (can_be_number) {
      expression >> n;
    }

    // It isn't a number
    if (!can_be_number || expression.fail()) {
      expression.clear();

      expression.seekg(old_position);

      char current_char;
      std::string identifier = "";

      while (true) {
        expression >> current_char;

        if (expression.eof()) {
          if (identifier.length()) {
            _tokens.emplace_back(new IdentifierToken(identifier));
          }
          break;
        }

        Operator char_as_operator = static_cast<Operator>(current_char);

        if (
          _binary_operator_definitions.count(char_as_operator) ||
          _unary_operator_definitions.count(char_as_operator) ||
          char_as_operator == Operator::left_paren ||
          char_as_operator == Operator::right_paren
        ) {
          if (identifier.length()) {
            _tokens.emplace_back(new IdentifierToken(identifier));
            identifier = "";
          }

          _tokens.emplace_back(new OperatorToken(char_as_operator));

          break;
        }
        
        identifier += current_char;
      }
    } else {
      _tokens.emplace_back(new NumToken(n));
    }
  }
}

void AstGenerator::print_tokens (std::ostream& os) {
  os << "Tokens:\n";
  for (const auto& token : _tokens) {
    switch (token->get_type()) {
      case TokenType::number: {
        os << "Type: number, Value: '" << dynamic_cast<NumToken&>(*token).value << "'\n";
        break;
      }

      case TokenType::identifier: {
        os << "Type: identifier, Value: '" << dynamic_cast<IdentifierToken&>(*token).value << "'\n";
        break;
      }

      case TokenType::left_paren:
      case TokenType::right_paren:
      case TokenType::oper: {
        auto value = static_cast<char>(dynamic_cast<OperatorToken&>(*token).value);
        os << "Type: operator, Value: '" << value << "'\n";
        break;
      }
    }
  }
}

std::shared_ptr<AstNode> AstGenerator::ast_from_tokens () {
  bool could_be_unary = true;

  for (auto it = _tokens.begin(); it != _tokens.end(); it++) {
    std::shared_ptr<Token> token = *it;

    switch (token->get_type()) {
      case TokenType::number: {
        _output.emplace(std::make_shared<AstNode>(AstNodeType::number, token));
        could_be_unary = false;
        break;
      }

      case TokenType::identifier: {
        auto next_token = std::next(it, 1);

        if (next_token != _tokens.end() && (*next_token)->get_type() == TokenType::left_paren) {
          // it's a function
          _operator_stack.emplace(token);
        } else {
          // it's a variable
          _output.emplace(std::make_shared<AstNode>(AstNodeType::variable, token));
        }
        could_be_unary = false;
        break;
      }

      case TokenType::oper: {
        auto operator_token = std::dynamic_pointer_cast<OperatorToken>(token);
        if (could_be_unary) {
          operator_token->operator_type = OperatorType::unary;
        }

        OperatorDefinition current_token_definition = get_operator_definition(operator_token);

        while (!_operator_stack.empty() && _operator_stack.top()->get_type() != TokenType::left_paren) {
          auto second_token = std::dynamic_pointer_cast<OperatorToken>(_operator_stack.top());
          OperatorDefinition second_token_definition = get_operator_definition(second_token);

          if (!(
            second_token_definition.precedence > current_token_definition.precedence || (
              second_token_definition.precedence == current_token_definition.precedence &&
              current_token_definition.associativity == Associativity::left
            )
          )) {
            break;
          }

          output_operator(AstNodeType::oper, false);

          could_be_unary = true;
        }

        _operator_stack.emplace(operator_token);
        break;
      }

      case TokenType::left_paren: {
        _operator_stack.emplace(token);
        could_be_unary = true;
        break;
      }

      case TokenType::right_paren: {
        while (true) {
          if (_operator_stack.empty()) {
            throw parser_error("Error: mismatched right parenthesis");
          }

          if (_operator_stack.top()->get_type() == TokenType::left_paren) {
            break;
          }

          output_operator(AstNodeType::oper, false);
        }

        _operator_stack.pop();

        if (!_operator_stack.empty() && _operator_stack.top()->get_type() == TokenType::identifier) {
          output_operator(AstNodeType::function, true);
        }

        could_be_unary = false;

        break;
      }
    }
  }

  while (!_operator_stack.empty()) {
    if (_operator_stack.top()->get_type() == TokenType::left_paren) {
      throw parser_error("Error: mismatched left parenthesis");
    }

    output_operator(AstNodeType::oper, false);
  }
  
  return _output.top();
}

std::shared_ptr<AstNode> AstGenerator::generate_ast (const std::string& expression) {
  auto ss = std::stringstream(expression);
  tokens_from_expression(ss);
  return ast_from_tokens();
}

// ast_generator.h
#pragma once

#include <string>
#include <memory>
#include <vector>
#include <unordered_map>
#include <stack>

#include "common.h"
#include "ast_node.h"

enum class Associativity {
  left,
  right,
};

struct OperatorDefinition {
  unsigned int precedence;
  Associativity associativity;
  OperatorType type;
  OperatorDefinition () {}
  OperatorDefinition (unsigned int precedence, Associativity associativity, OperatorType type = OperatorType::binary) 
    : precedence(precedence), associativity(associativity), type(type) {}
};

class AstGenerator {
private:
  std::vector<std::shared_ptr<Token>> _tokens;
  std::unordered_map<Operator, OperatorDefinition> _unary_operator_definitions;
  std::unordered_map<Operator, OperatorDefinition> _binary_operator_definitions;
  std::stack<std::shared_ptr<Token>> _operator_stack;
  std::stack<std::shared_ptr<AstNode>> _output;

  OperatorDefinition get_operator_definition (std::shared_ptr<OperatorToken> operator_token);

  void output_operator (AstNodeType node_type, bool force_unary);

  void add_operator (Operator oper, const OperatorDefinition& definition);
public:
  struct parser_error: public std::exception{
    const std::string text;
    parser_error (const std::string& text): text(text) {}
    const char* what () const throw () {
      return text.c_str();
    }
  };

  AstGenerator ();

  void tokens_from_expression (std::istream& expression);

  void print_tokens (std::ostream& os);

  std::shared_ptr<AstNode> ast_from_tokens ();

  std::shared_ptr<AstNode> generate_ast (const std::string& expression);
};

// ast_node.cpp
#include "ast_node.h"

void AstNode::print (std::ostream& os, const std::string& prefix, bool is_first_child) {
  os << prefix;
  os << (is_first_child ? "├───" : "└───");

  switch (_type) {
    case AstNodeType::number: {
      os << dynamic_cast<NumToken&>(*_token).value << "\n";
      break;
    }

    case AstNodeType::variable:
    case AstNodeType::function: {
      os << dynamic_cast<IdentifierToken&>(*_token).value << "\n";
      break;
    }

    case AstNodeType::oper: {
      auto value = static_cast<char>(dynamic_cast<OperatorToken&>(*_token).value);
      os << value << "\n";
      break;
    }
  }

  std::string new_prefix = prefix + (is_first_child ? "│   " : "    ");
  bool child_is_first = true;
  for (const auto& child : _children) {
    child->print(os, new_prefix, child_is_first);
    child_is_first = false;
  }
}

std::ostream& operator<< (std::ostream& os, AstNode& ast) {
  ast.print(os, "", false);
  return os;
}

// ast_node.h
#pragma once

#include <memory>
#include <iostream>
#include <vector>

#include "common.h"

enum class AstNodeType {
  number,
  variable,
  function,
  oper,
};

class AstNode {
private:
  AstNodeType _type;
  std::shared_ptr<Token> _token;
  std::vector<std::shared_ptr<AstNode>> _children;

  void print (std::ostream& os, const std::string& prefix, bool is_first_child);
public:
  AstNode () {}
  AstNode (AstNodeType type, std::shared_ptr<Token> token) : _type(type), _token(token) {}
  ~AstNode () = default;

  AstNodeType node_type () {
    return _type;
  }

  std::shared_ptr<Token> token () {
    return _token;
  }

  std::vector<std::shared_ptr<AstNode>> children () {
    return _children;
  }

  void add_child(std::shared_ptr<AstNode> child) {
    _children.emplace_back(child);
  }

  friend std::ostream& operator<< (std::ostream& out, AstNode& ast);
};

// common.h
#pragma once

#include <string>

enum class Operator : char {
  add = '+',
  sub = '-',
  mul = '*',
  div = '/',
  exp = '^',
  left_paren = '(',
  right_paren = ')',
};

enum class TokenType {
  number,
  identifier,
  oper,
  left_paren,
  right_paren,
};

enum class OperatorType {
  unary,
  binary,
};

struct Token {
  virtual TokenType get_type () = 0;
};

struct NumToken : public Token {
  double value;
  NumToken (double n) : value(n) {}
  TokenType get_type () override {
    return TokenType::number;
  }
};

struct IdentifierToken : public Token {
  std::string value;
  IdentifierToken (std::string token) : value(token) {}
  TokenType get_type () override {
    return TokenType::identifier;
  }
};

struct OperatorToken : public Token {
  Operator value;
  OperatorType operator_type = OperatorType::binary;

  OperatorToken (Operator token) : value(token) {}
  TokenType get_type () override {
    if (value == Operator::left_paren) {
      return TokenType::left_paren;
    }
    
    if (value == Operator::right_paren) {
      return TokenType::right_paren;
    }

    return TokenType::oper;
  }
};

// evaluator.cpp
#include <cmath>

#include "evaluator.h"
#include "ast_generator.h"

ExpressionEvaluator::ExpressionEvaluator () {
  define_operator(Operator::add,
    [](const std::vector<double>& args) {
      if (args.size() == 1) {
        return args[0];
      }

      return args[1] + args[0];
    }
  );
  define_operator(Operator::sub,
    [](const std::vector<double>& args) {
      if (args.size() == 1) {
        return -args[0];
      }

      return args[1] - args[0];
    }
  );
  define_operator(Operator::mul,
    [](const std::vector<double>& args) {
      return args[1] * args[0];
    }
  );
  define_operator(Operator::div,
    [](const std::vector<double>& args) {
      return args[1] / args[0];
    }
  );
  define_operator(Operator::exp,
    [](const std::vector<double>& args) {
      return std::pow(args[1], args[0]);
    }
  );

  define_function("sqrt",
    [](const std::vector<double>& args) {
      return std::sqrt(args[0]);
    }
  );
}

double ExpressionEvaluator::evaluate_from_ast (std::shared_ptr<AstNode> node) {
  switch (node->node_type()) {
    case AstNodeType::number: {
      auto number_token = std::dynamic_pointer_cast<NumToken>(node->token());
      return number_token->value;
    }

    case AstNodeType::variable: {
      auto identifier_token = std::dynamic_pointer_cast<IdentifierToken>(node->token());

      try {
        return _variables.at(identifier_token->value);
      } catch (const std::out_of_range& ex) {
        throw evaluator_error("Error: Variable '" + identifier_token->value + "' does not exist");
      }
    }

    case AstNodeType::function: {
      auto identifier_token = std::dynamic_pointer_cast<IdentifierToken>(node->token());
      std::vector<double> args(node->children().size());

      unsigned int i = 0;
      for (const auto& child : node->children()) {
        args[i] = evaluate_from_ast(child);
        i++;
      }

      try {
        return _functions.at(identifier_token->value)(args);
      } catch (const std::out_of_range& ex) {
        throw evaluator_error("Error: Function '" + identifier_token->value + "' does not exist");
      }
    }

    case AstNodeType::oper: {
      auto operator_token = std::dynamic_pointer_cast<OperatorToken>(node->token());
      std::vector<double> args(node->children().size());

      unsigned int i = 0;
      for (const auto& child : node->children()) {
        args[i] = evaluate_from_ast(child);
        i++;
      }

      try {
        return _operators.at(operator_token->value)(args);
      } catch (const std::out_of_range& ex) {
        throw evaluator_error(
          std::string("Error: Operator '") + static_cast<char>(operator_token->value) + "' does not exist"
        );
      }
    }
  }
}

double ExpressionEvaluator::evaluate (const std::string& expression, const std::unordered_map<std::string, double>&& variable_values) {
  AstGenerator generator;

  try {
    std::shared_ptr<AstNode> ast = generator.generate_ast(expression);

    _variables = variable_values;
    return evaluate_from_ast(ast);
  } catch (const AstGenerator::parser_error& ex) {
    throw ex;
  }
}

// evaluator.h
#pragma once

#include <string>
#include <vector>
#include <functional>
#include <unordered_map>

#include "ast_generator.h"

class ExpressionEvaluator {
private:
  std::unordered_map<std::string, double> _variables;
  std::unordered_map<std::string, std::function<double(const std::vector<double>&)>> _functions;
  std::unordered_map<Operator, std::function<double(const std::vector<double>&)>> _operators;

  void define_function (const std::string& name, const std::function<double(const std::vector<double>&)>&& impl) {
    _functions[name] = impl;
  }

  void define_operator (Operator oper, std::function<double(const std::vector<double>&)>&& impl) {
    _operators[oper] = impl;
  }
public:
  struct evaluator_error: public std::exception{
    const std::string text;
    evaluator_error (const std::string& text): text(text) {}
    const char* what () const throw () {
      return text.c_str();
    }
  };

  ExpressionEvaluator ();

  double evaluate_from_ast (std::shared_ptr<AstNode> node);

  double evaluate (const std::string& expression, const std::unordered_map<std::string, double>&& variable_values);
};

Answer 1

For a beginner this already quite advanced and well-written code.

Improving custom exceptions

It's great that you have custom exceptions that derive from std::exception. However, std::exception has the drawback that you have to implement your own what(). Consider deriving from a higher level exception object instead, like std::runtime_error. Apart from providing more information about the nature of the error this way, you can then simplify the definition of your own custom exceptions like so:

struct parser_error: public std::runtime_error {
    parser_error(const std::string& text): std::runtime_error(text) {}
};

When catching errors, make use of the exception class hierarchy to avoid having to write multiple catch-statements:

try {
    std::cout << evaluator.evaluate(expression, std::move(variable_values)) << "\n";
} catch (const std::runtime_error& ex) {
    std::cerr << ex.what() << "\n";
}

When to use a class

If I look at the code in main(), I see:

ExpressionEvaluator evaluator;
std::cout << evaluator.evaluate(expression, variable_values);

What's the point of the evaluator object though? It doesn't seem like it provides any benefit. Why not have a free function, so you would just write:

std::cout << evaluate(expression, variable_values);

The _functions and _operators variables can be made static and put in a namespace.

A reason to do use a class would be if there is some state that you can reuse. For example, it would be really nice if you could create an evaluator for a given expression, and then call it multiple times with different values. For example, it would be really nice if you could write:

ExpressionEvaluator square("x * x");
std::unordered_map<std::string, double> values;
auto& x = values["x"];
for (x = 0; x <= 10; ++x) {
    std::cout << x << "² = " << square(values) << "\n";
}

The same goes for AstGenerator. Make generate_ast() a free function that returns an object of type Ast, the latter just being a container for an abstract syntax tree.

Use static variables

You are initializing a lot of maps at runtime in constructors. If you only ever create on object of a type that does that, it's not a problem, but consider that in larger projects, many of such objects might be created. You could go for a singleton pattern, but in C++ there is a much more straightforward solution, and that is to make these maps static, and initialize them at the same time you declare them. For example:

static std::unordered_map<Operator, OperatorDefinition> _unary_operator_definitions = {
    {Operator::add, {3,  Associativity::right}},
    {Operator::sub, {3,  Associativity::right}},
};
...
static std::unordered_map<Operator, std::function<double(const std::vector<double>&)>> _operators = {
    {Operator::add, [](auto& args) { ... }},
    {Operator::sub, [](auto& args) { ... }},
    ...
};

Unnecessary use of std::shared_ptr<>

You should use std::shared_ptr<> if you need shared ownership semantics. However, in your case that is not needed. The vector _tokens can be the sole owner of the tokens, and thus use std::unique_ptr<Token>. Then _operator_stack can just store raw pointers to the tokens owned by _tokens, since the latter's lifetime will be longer than that of the other containers. So:

std::vector<std::unique_ptr<Token>> _tokens;
st::stack<Token*> _operator_stack;

Consider using std::variant

Using inheritance and pointers is one way to store different types of tokens in a container, however since C++17 there is also std::variant which can be used as an alternative. For example, you could then just write:

using Token = std::variant<double, std::string, Operator>;
std::vector<Token> _tokens;

The main advantage would be that you don't need to use pointers anymore to store tokens. A disadvantage is that for a beginner, you might have to wrap your head around how to deal with variants. For example, see the "type matching visitor" example from the documentation of std::visit().