Click here to Skip to main content
15,867,704 members
Articles / Web Development / HTML

Expression Evaluator Example Using a Variadic Visitor Pattern in C++

Rate me:
Please Sign up or sign in to vote.
4.94/5 (13 votes)
20 Jul 2015CPOL4 min read 23.9K   286   24   8
Illustrates the idea of a variadic visitor pattern in C++ by way of an example expression calculator

Introduction

This article illustrates the use of dispatch mechanism similar to the visitor pattern described by the gang of four to apply operations to polymorphic data structures in C++.

Background

The Design Patterns book by Gamma et. al. describes an object pattern used to perform a double dispatch operation on two polymorphic types. The concrete object nodes dispatch their concrete types to a visiting node type.

Often the visiting object type is known in the client code, and an implementer might prefer not to pay the performance penalty of the second virtual method invocation, especially given this method of dispatch is often used to interpret nested polymorphic data types like the one used in the example.

The code presented uses a switch mechanism to dispatch to method calls on a visiting object, however the presented code avoids the proliferation of switch statements throughout a program's source code by isolating the dispatch to a template function that can call into the visitor object's methods using the concrete types of the polymorphic data type.

Another feature of the code presented is the ability to pass various types of parameters and results through the visitor objects method by way of a variadic function template.

Expression Calculator Overview

The expression calculator presented involves a command line interpreter REPL. The calculator supports 4 basic infix arithmetic operations + - * / and assignment, and supports integer variables and constants. The parser also supports bracketing of expressions to influence the order that operations are evaluated, however this information does not get stored in the syntax tree. The REPL will present a prompt, and parse a line containing an arithmetic expression. Before evaluating the expression, the REPL will format the parsed expression including brackets to describe the tree structure of the expression. The expression will then be evaluated and the result will be reported back to the prompt.

Example Interaction

The following demonstration shows an interaction inspired by Pythagoras' theorem. The user enters 3 variables, a, b, and c, then calculates the sum of the squares of the short sides, and shows that it is equal to the sum of the squares of the hypotenuse. Finally, the user enters an empty line and the REPL exits.

Expression> a = 3
Evaluating:(a = 3)
Result: 3

Expression> b = 4
Evaluating:(b = 4)
Result: 4

Expression> c = 5
Evaluating:(c = 5)
Result: 5

Expression> a * a + b * b
Evaluating:((a * a) + (b * b))
Result: 25

Expression> c * c
Evaluating:(c * c)
Result: 25

Expression> 
Bye

Points of Interest

visit_expression Function

The visit expression function provides the main dispatching capabilities of the expression calculator. By isolating the switch statement to the template method, the potential proliferation of switch statements throughout an entire system can be avoided, and when adding new types of node to the system, the implementer will receive errors if they have not provided all implementations. Note the static pointer cast, which is a cast implementation for shared_ptr, which maintains the reference count on the smart pointer, and also note the std::forward of each of the variadic arguments. New visitors are also easy to author, and only require that a method per node type is implemented.

//
//  expression_visitor.h
//

#ifndef VariadicVisitor_expression_visitor_h
#define VariadicVisitor_expression_visitor_h

#include "expression.h"
#include "expression_implementations.h"

#include <utility>

// this method is used to extract the concrete type from the expression,
// the method then forwards the expression and it's arguments to a supplied
// visitor object. The visitor object is expected to implement the operator()
// method, and return type result. For untyped results, std::nullptr_t is
// recommended over void.
template<typename result, typename visitor, typename...arguments>
static result visit_expression(const visitor& v,
                               const std::shared_ptr<expression>& e,
                               arguments&& ... args)
{
    switch (e->type()) {
    case ADD_EXPRESSION:
        return v(std::static_pointer_cast<add_expression>(e),
                 std::forward<arguments>(args)...);
    case SUBTRACT_EXPRESSION:
        return v(std::static_pointer_cast<subtract_expression>(e),
                 std::forward<arguments>(args)...);
    case MULTIPLY_EXPRESSION:
        return v(std::static_pointer_cast<multiply_expression>(e),
                 std::forward<arguments>(args)...);
    case DIVIDE_EXPRESSION:
        return v(std::static_pointer_cast<divide_expression>(e),
                 std::forward<arguments>(args)...);
    case VARIABLE_EXPRESSION:
        return v(std::static_pointer_cast<variable_expression>(e),
                 std::forward<arguments>(args)...);
    case CONSTANT_EXPRESSION:
        return v(std::static_pointer_cast<constant_expression>(e),
                 std::forward<arguments>(args)...);
    case ASSIGN_EXPRESSION:
        return v(std::static_pointer_cast<assign_expression>(e),
                 std::forward<arguments>(args)...);
    }
}

#endif

print_expression Function and print_visitor Class

The print expression illustrates a client of the visitor pattern. The visitor class must supply a method call operator overload for each type that derives from the expression base class. Each method returns the stream that was supplied.

Note that in the stream insertion operator at the end of the file, I've only supplied the result type to the function template, as the types of the other arguments can be deduced by the compiler. I also want to indicate that the visitor methods are constant so that the visitor can be constructed and passed as a constant reference.

//
//  print_expression.cpp
//

#include "expression_visitor.h"

std::ostream& operator<<(std::ostream& stream,
                         const std::shared_ptr<expression>& e);

// the print visitor class implements the visitor pattern, each method taking
// a shared pointer to a concrete class derived from expression, and a stream
// and return the supplied stream.
class print_visitor
{
public:
    std::ostream& operator()(const std::shared_ptr<add_expression>& e,
	                         std::ostream& stream) const
    {
        return stream << "(" << e->arguend << " + " << e->addend << ")";
    }
	
    std::ostream& operator()(const std::shared_ptr<subtract_expression>& e,
                                 std::ostream& stream) const
    {
        return stream << "(" << e->minuend << " - " << e->subtrahend << ")";
    }
	
    std::ostream& operator()(const std::shared_ptr<multiply_expression>& e,
	                         std::ostream& stream) const
    {
        return stream << "(" << e->multiplicand << " * " << e->multiplier << ")";
    }
	
    std::ostream& operator()(const std::shared_ptr<divide_expression>& e,
	                         std::ostream& stream) const
    {
        return stream << "(" << e->dividend << " / " << e->divisor << ")";
    }
	
    std::ostream& operator()(const std::shared_ptr<variable_expression>& e,
	                         std::ostream& stream) const
    {
        return stream << e->name;
    }
	
    std::ostream& operator()(const std::shared_ptr<constant_expression>& e,
	                         std::ostream& stream) const
    {
        return stream << e->value;
    }
	
    std::ostream& operator()(const std::shared_ptr<assign_expression>& e,
                                 std::ostream& stream) const
    {
        return stream << "(" << e->name << " = " << e->value << ")";
    }
};

// the insertion operator formats the expression to the stream
std::ostream& operator<<(std::ostream& stream, const std::shared_ptr<expression>& e)
{
    return visit_expression<std::ostream&>(print_visitor(), e, stream);
}

interpret Function and interpret_visitor Class

The listing below shows the implementation of another visitor, with different behaviour. This object is supplied a map of values, and it will return the result of evaluating an expression. Assignments affect the values stored inside the map, and any missing variables will default to 0 but values will only be added to the map when the expression is an assignment.

//
//  interpret_expression.cpp
//

#include "expression_visitor.h"
#include <map>
#include "interpret_expression.h"

// this class implements the visitor pattern. Each method takes a concrete
// shared_ptr of a derived expression class, and a map of variables and values
// and return the result of the evaluated expression.
class interpret_visitor
{
public:
    int operator()(const std::shared_ptr<add_expression>& e,
                   std::map<std::string, int>& values) const
    {
        return interpret(e->arguend, values)
             + interpret(e->addend, values);
    }
	
    int operator()(const std::shared_ptr<subtract_expression>& e,
                   std::map<std::string, int>& values) const
    {
        return interpret(e->minuend, values)
             - interpret(e->subtrahend, values);
    }
	
    int operator()(const std::shared_ptr<multiply_expression>& e,
                   std::map<std::string, int>& values) const
    {
        return interpret(e->multiplicand, values)
             * interpret(e->multiplier, values);
    }
	
    int operator()(const std::shared_ptr<divide_expression>& e,
                   std::map<std::string, int>& values) const
    {
        return interpret(e->dividend, values)
             / interpret(e->divisor, values);
    }
	
    int operator()(const std::shared_ptr<variable_expression>& e,
                   std::map<std::string, int>& values) const
    {
        auto it = values.find(e->name);
        if(it == values.end())
        {
            return 0;
        }
        return it->second;
    }
	
    int operator()(const std::shared_ptr<constant_expression>& e,
                   std::map<std::string, int>& values) const
    {
        return e->value;
    }
	
    int operator()(const std::shared_ptr<assign_expression>& e,
                   std::map<std::string, int>& values) const
    {
        int result = interpret(e->value, values);
        values[e->name] = result;
        return result;
    }
};

// the interpret function constructs an interpret visitor, and bootstraps the visiting
// process
int interpret(const std::shared_ptr<expression>& e,
              std::map<std::string,int>& values)
{
    return visit_expression<int>(interpret_visitor(), e, values);
}

Summary

This article has presented a method of performing a multiple dispatch operation on a polymorphic object type that can be used when a consuming type is known at compile time. The method used maintains some of the benefits of using the visitor pattern described by the gang of four in the design patterns book.

References

History

  • 2015-Apr-12 - Initial authoring, parser, formatter, evaluator and REPL

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


Written By
Software Developer (Senior)
New Zealand New Zealand
I've spent time programming for the security industry, video games, and telephony. I live in New Zealand, and have a Bachelor of Computing and Mathematical Sciences specializing in Computer Technology, from the University of Waikato in Hamilton, New Zealand.

Comments and Discussions

 
Suggestioncompilation in VisualStudio Pin
Igi???14-Oct-15 21:53
Igi???14-Oct-15 21:53 
AnswerRe: compilation in VisualStudio Pin
phillipvoyle26-Oct-15 22:32
phillipvoyle26-Oct-15 22:32 
General[My vote of 1] compiling failed Pin
Taulie20-Jul-15 22:02
Taulie20-Jul-15 22:02 
AnswerRe: [My vote of 1] compiling failed Pin
phillipvoyle20-Jul-15 23:46
phillipvoyle20-Jul-15 23:46 
GeneralMy vote of 3 Pin
SeattleC++13-Apr-15 11:18
SeattleC++13-Apr-15 11:18 
GeneralRe: My vote of 3 Pin
phillipvoyle13-Apr-15 11:44
phillipvoyle13-Apr-15 11:44 
GeneralRe: My vote of 3 Pin
SeattleC++13-Apr-15 12:26
SeattleC++13-Apr-15 12:26 
GeneralRe: My vote of 3 Pin
phillipvoyle13-Apr-15 22:07
phillipvoyle13-Apr-15 22:07 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.