A simple expression library for building and parsing simple mathematical expressions

expressions.hpp

#ifndef EXPRESSIONS_H_INCLUDED
#define EXPRESSIONS_H_INCLUDED

#include <memory>
#include <cassert>
#include <cmath>

namespace Expression
{
    
    enum expression_type
    {
        None,
        Constant ,
        Variable ,
        Plus ,
        Minus ,
        Divides ,
        Multiplies ,
        UnaryFunc
    };
    
    class expr
    {
    public:
        
        using expr_ptr = std::shared_ptr< expr >;
        using const_expr_ptr = std::shared_ptr< expr const >;
        
        virtual size_t num_children( void ) const = 0;
        virtual const_expr_ptr get_children( size_t i ) const = 0;
        virtual expr_ptr get_children( size_t i ) = 0;
        virtual void set_children( size_t , expr_ptr e ) = 0;
        virtual expression_type get_type( void ) const = 0;
        virtual std::string to_string( void ) const = 0;
        virtual double eval() const = 0;
    };
    
    using expr_ptr = expr::expr_ptr;
    using const_expr_ptr = expr::const_expr_ptr;
    
    class terminal_expr : public expr
    {
    public:

        size_t num_children( void ) const override { return 0; }
        const_expr_ptr get_children( size_t i ) const override { assert( false ); return nullptr; }
        expr_ptr get_children( size_t i ) override { assert( false ); return nullptr; }
        void set_children( size_t i , expr_ptr e ) override { assert( false ); }
    };
    
    class unary_expr : public expr
    {
    public:
        
        unary_expr( expr_ptr child )
        : m_child{ child } {}

        virtual double eval() const { return 0.0; }
        size_t num_children( void ) const override { return 1; }
        const_expr_ptr get_children( size_t i ) const override { assert( i == 0 ) ;return m_child; }
        expr_ptr get_children( size_t i ) override { assert( i == 0 ) ;return m_child; }
        void set_children( size_t i , expr_ptr e ) override { assert( i == 0 ); m_child = e; }
        
    protected:
    
        expr_ptr m_child;
    };
    
    class binary_expr : public expr
    {
    public:
        
        binary_expr( expr_ptr left , expr_ptr right )
        : m_children{} { m_children[0] = left; m_children[1] = right; }

        double eval() const override { return 0.0; }
        size_t num_children( void ) const override { return 2; }
        const_expr_ptr get_children( size_t i ) const override { assert( i < 2 ); return m_children[i]; }
        expr_ptr get_children( size_t i ) override { assert( i < 2 ); return m_children[i]; }        
        void set_children( size_t i , expr_ptr e ) override { assert( i < 2 ); m_children[i] = e; }
        
    protected:
       
        expr_ptr m_children[2];
    };
    
    class constant : public terminal_expr
    {
    public:
        
        constant( double c ) : m_c( c ) {}
        double eval( ) const { return m_c; }
        expression_type get_type( void ) const final { return Constant; }
        std::string to_string( void ) const final
        {
            return std::to_string( m_c );
        }
        
    private:
        
        double m_c;
    };
    
    struct context_expr_eval
    {
        double get ( int const & index) const noexcept
        {
            assert( index < 20 );
            return elements[index];
        }
        virtual ~context_expr_eval() { }

    private:
        std::array<double, 20> elements { { 11.8, 15,9, 11.9, 1, 12, 12, 24, 6, 45, 45, 6 } };
    };
    
    template< size_t I >
    class variable : public terminal_expr, context_expr_eval
    {
        int m_index;
    public:
        variable( int const & index = I ): terminal_expr {}, context_expr_eval {}, m_index { index } { }
        double eval() const override { return context_expr_eval::get( m_index ); }
        expression_type get_type( void ) const override { return Variable; }
        std::string to_string( void ) const override {
            return std::string { "var" + std::to_string( m_index ) };
        }
    };
    
    class sin_node : public unary_expr
    {
    public:
        sin_node( expr_ptr ptr ) : unary_expr{ ptr } { }
        expression_type get_type( void ) const override { return UnaryFunc; }
        std::string to_string( void ) const override { return "sin"; }
    };
    
    class cos_node : public unary_expr
    {
    public:
        cos_node( expr_ptr child ) : unary_expr{ child } { }
        expression_type get_type( void ) const override { return UnaryFunc; }
        std::string to_string( void ) const override { return "cos"; }
    };
    
    class plus_node : public binary_expr
    {
    public:
        plus_node( expr_ptr left , expr_ptr right ) : binary_expr{ left , right } { }
        expression_type get_type( void ) const override { return Plus; }
        std::string to_string( void ) const override { return "+"; }
    };
    
    class multiplies_node : public binary_expr
    {
    public:
        
        multiplies_node( expr_ptr left , expr_ptr right ) : binary_expr{ left , right } { }
        expression_type get_type( void ) const override { return Multiplies; }
        std::string to_string( void ) const override { return "*"; }
    };
    
    class minus_node : public binary_expr
    {
    public:
        
        minus_node( expr_ptr left , expr_ptr right ) : binary_expr{ left , right } { }
        expression_type get_type( void ) const override { return Minus; }
        std::string to_string( void ) const override { return "-"; }
    };
    
    class divides_node : public binary_expr
    {
    public:
        
        divides_node( expr_ptr left , expr_ptr right ) : binary_expr{ left , right } { }
        expression_type get_type( void ) const override { return Divides; }
        std::string to_string( void ) const override { return "/"; }
    };
    
    expr_ptr make_constant( double c ) { return std::make_shared< constant >( c ); }
    
    template< size_t I>
    expr_ptr make_variable( ) { return std::make_shared< variable< I > >( ); }

    template< size_t I = 0>
    expr_ptr make_variable_with_index( int const & index ) { return std::make_shared< variable< I > >( index ); }
    
    expr_ptr make_sin( expr_ptr child ) { return std::make_shared< sin_node >( child ); }
    expr_ptr make_cos( expr_ptr child ) { return std::make_shared< cos_node >( child ); }
    expr_ptr make_plus( expr_ptr left , expr_ptr right ) { return std::make_shared< plus_node >( left , right ); }
    expr_ptr make_minus( expr_ptr left , expr_ptr right ) { return std::make_shared< minus_node >( left , right ); }
    expr_ptr make_multiplies( expr_ptr left , expr_ptr right ) { return std::make_shared< multiplies_node >( left , right ); }
    expr_ptr make_divided( expr_ptr left , expr_ptr right ) { return std::make_shared< divides_node >( left , right ); }
}
#endif // EXPRESSIONS_H_INCLUDED

expressions_io.hpp

#ifndef EXPRESSION_IO_H_INCLUDED
#define EXPRESSION_IO_H_INCLUDED

#include "lexer.hpp"
#include <sstream>
#include <deque>

using namespace EditedExpression;

namespace Expression
{
    
    inline expr_ptr build_tree_for( expression_type const & expr_constant )
    {
        switch( expr_constant ){
            case expression_type::Plus: default: return make_plus( nullptr, nullptr );
        }
    }
    
    void attach( expr_ptr const &a, std::deque<expression_type> &operator_deq, std::deque<expr_ptr> &children_deq )
    {
        for( size_t i = 0; i != a->num_children(); ++i ){
            expression_type type_of_expr = a->get_children( i )->get_type();
            if( type_of_expr == expression_type::Plus ){
                operator_deq.push_back( type_of_expr );
                attach( a->get_children( i ), operator_deq, children_deq );
            } else {
                children_deq.push_back( a->get_children( i ) );
            }
        }
    }
    
    expr_ptr build_rightmost_tree( expr_ptr const &a, expr_ptr &node, expression_type in )
    {
        expr_ptr right_tree = build_tree_for( in );
        right_tree->set_children( 1, a );
    
        right_tree.swap( node );
    
        node->set_children( 0, right_tree );
        return node->get_children( 1 );
    }
    
    expr_ptr linearize( expr_ptr const & expression )
    {
        std::deque<expr_ptr> child_deq {};
        std::deque<expression_type> op_deq { expression->get_type() };
        
        expr_ptr tree_to_build = nullptr, ptr = nullptr;
        expr *x = tree_to_build.get();
    
        attach( expression, op_deq, child_deq );
        while( !op_deq.empty() ){
            if( !tree_to_build ){
                tree_to_build = build_tree_for( op_deq.front() ); op_deq.pop_front();
                tree_to_build->set_children( 0, child_deq.front() );
                child_deq.pop_front();
                
                tree_to_build->set_children( 1, child_deq.front() );
                child_deq.pop_front();
                
                ptr = tree_to_build->get_children( 1 );
                x = tree_to_build.get();
            } else {
                auto foo = build_rightmost_tree( child_deq.front(), ptr, op_deq.front() );
                op_deq.pop_front();
                child_deq.pop_front();
                x->set_children( 1, ptr );
    
                x = x->get_children( 1 ).get();
    
                ptr = foo;
            }
        }
        return tree_to_build;
    }
    inline double to_double ( std::string const & str )
    {
        return std::stod( str );
    }
    
    inline void update_current_token( Lexer &lex, Lexer::token_type &token )
    {
        if( !lex.eof() ){
            token = lex.get_token();
        } else {
            token.first.get_lexeme().clear();
            token.second = expression_type::None;
        }
    }
    
/*
 * 
 * name: get_index_from
 * @param: string
 * @return: integer
 * This function is an hack, why? Making variable requires a compile-time template parameter constant I, extracting the index from a
 * polish notation, such as var0, requires a runtime calculation in order to get the last digit 0 or 10 in case it is var10, this is
 * why I created this function and an accompanying function make_variable_with_index( int ), which will serve as an index.
 */
    inline int get_index_from( std::string const & str )
    {
        std::string::size_type found = str.find_first_of( "1234567890" );
        return std::stoi( std::string { str.begin() + found, str.end() } );
    }
    expr_ptr build_unary_operator_or_variable_from( Lexer::token_type const & token )
    {
        if( token.first.lexeme() == std::string { "cos" } ){
            return make_cos( nullptr );
        } else if( token.first.lexeme() == std::string { "sin" } ){
            return make_sin( nullptr );
        } else {
            unsigned int const index = get_index_from( token.first.lexeme() );
            return make_variable_with_index<>( index );
        }
    }
    
    expr_ptr convert_token_to_expression( Lexer::token_type const & token )
    {
        switch( token.second ){
            case expression_type::None: default:        return nullptr;
            case expression_type::Constant:             return make_constant( to_double( token.first.lexeme() ) );
            case expression_type::Variable:
            case expression_type::UnaryFunc:            return build_unary_operator_or_variable_from( token );
            case expression_type::Plus:                 return make_plus( nullptr, nullptr );
            case expression_type::Minus:                return make_minus( nullptr, nullptr );
            case expression_type::Divides:              return make_divided( nullptr, nullptr );
            case expression_type::Multiplies:           return make_multiplies( nullptr, nullptr );
        }
    }
    inline expr_ptr get_root_node( Lexer & lex )
    {
        return convert_token_to_expression( lex.get_token() );
    }
    
    expr_ptr insert_child( expr_ptr node_to_insert, Lexer & lex, Lexer::token_type & token )
    {
        auto curr_ptr = node_to_insert;
        if( curr_ptr ){
            for( size_t i = 0; i != curr_ptr->num_children(); ++i ){
                update_current_token( lex, token );
                node_to_insert = convert_token_to_expression( token );
                curr_ptr->set_children( i, insert_child( node_to_insert, lex, token ) );
            }
        }
        return curr_ptr;
    }
    expr_ptr from_polish( std::string const & str, std::string const & separator = "|" )
    {
        Lexer lex ( str );
        Lexer::token_type token;
        
        expr_ptr root = get_root_node( lex );
        
        if( !lex.eof() ){
            for( size_t i = 0; i != root->num_children(); ++i ){
                update_current_token( lex, token );
                auto what_to_insert = convert_token_to_expression( token );
                root->set_children( i, insert_child( what_to_insert, lex, token ) );
            }
        }
        return root;
    }
    inline void to_polish( std::ostream& out , const_expr_ptr e , std::string const& separator = "|" )
    {
        assert( e );
        out << e->to_string();
        for( size_t i=0 ; i<e->num_children() ; ++i )
        {
            out << separator;
            to_polish( out , e->get_children(i) , separator );
        }
    }
    
    inline double process_unary_function( const_expr_ptr e );

    inline double evaluate_expr( double const & c )
    {
        return c;
    }
    inline double evaluate_expr( const_expr_ptr e )
    {
        switch ( e->get_type() ) {
            case Constant:
                return e->eval();
            case Variable:
                return e->eval();
            case Plus:
                return evaluate_expr( e->get_children( 0 ) ) + evaluate_expr( e->get_children( 1 ) );
            case Minus:
                return evaluate_expr( e->get_children( 0 ) ) - evaluate_expr( e->get_children( 1 ) );
            case Divides:
                return evaluate_expr( e->get_children( 0 ) ) / evaluate_expr( e->get_children( 1 ) );
            case Multiplies:
                return evaluate_expr( e->get_children( 0 ) ) * evaluate_expr( e->get_children( 1 ) );
            case UnaryFunc: default:
                return process_unary_function( e );
        }
    }
    
    inline double process_unary_function( const_expr_ptr e )
    {
        if( e->to_string() == std::string { "cos" } ){
            return std::cos( evaluate_expr( e->get_children( 0 ) ) );
        } else {
            return std::sin( evaluate_expr( e->get_children( 0 ) ) );
        }
    }
    inline std::string to_polish( const_expr_ptr e , std::string const& separator = "|" )
    {
        std::ostringstream str;
        to_polish( str , e , separator );
        return str.str();
    }
    
    namespace detail {
    
    inline void to_graphviz_impl( std::ostream& out , const_expr_ptr e , size_t& index )
    {
        assert( e );
        
        size_t current_index = index;
        out << "NODE" << current_index << " [ label = \"" << e->to_string() << "\" ]\n";
            
        for( size_t i=0 ; i<e->num_children() ; ++i )
        {
            ++index;
            out << "NODE" << current_index << " -> " << "NODE" << index << "\n";
            to_graphviz_impl( out , e->get_children(i) , index );
        }
    }
    
    } // namespace detail
    
    inline void to_graphviz( std::ostream& out , const_expr_ptr e )
    {
        out << "digraph G\n";
        out << "{\n";
        size_t index = 0;
        if( e ) detail::to_graphviz_impl( out , e , index );
        out << "}\n";
    }
    
    inline std::string to_graphviz( const_expr_ptr e )
    {
        std::ostringstream str;
        to_graphviz( str , e );
        return str.str();
    }
}
#endif // EXPRESSION_IO_H_INCLUDED

lexer.hpp

#ifndef LEXER_H_INCLUDED
#define LEXER_H_INCLUDED

#include "expressions.hpp"

namespace EditedExpression
{
    inline namespace Functions
    {
        struct is_alphabet
        {
            inline bool operator() ( int const & ch ) {
                return ( ch >= 'a' && ch <= 'z' ) || ( ch >= 'A' && ch <= 'Z' ) || ch == '_';
            }
        };
        struct is_numeric_constant
        {
            inline bool operator ()( int const & ch ){
                return ( ch >= '0' && ch <= '9') || ( ch == '.' );
            }
        };
        struct is_alphanumeric
        {
            inline bool operator ()( int const & ch ){
                return ( is_alphabet{}( ch ) || is_numeric_constant{}( ch ) );
            }
        };
        [[noreturn]] void panic( std::string const & str, int const & column ){
            std::string space ( column - 1, ' ' );
            printf( "Invalid expression near column: %d\n", column );
            puts( str.c_str() );
            printf( "%s^\n", space.c_str() );

            std::exit( -1 );
        }
    } // Functions

    constexpr size_t EOF_F = -1;
    using Expression::expression_type;


    struct Symbol
    {
        Symbol( std::string && lex ): m_lexeme( std::move( lex ) ) { }
        Symbol( char const *lex ): m_lexeme( lex ) { }
        Symbol( std::string const & lex = "None" ): m_lexeme( lex ) { }

        std::string &get_lexeme() { return m_lexeme; }
        const std::string lexeme() const { return m_lexeme; }
    private:
        std::string m_lexeme;
    };
    
    struct Lexer
    {
    private:
        std::string str_lex; //since we're dealing with a very small string, using a std::ostream would be an overkill
        std::string::size_type current_index;
        size_t current_character, end_of_file;

        inline void update_current_token() {
            if( current_index >= end_of_file ){
                current_character = EOF_F;
                return;
            }
            current_character = str_lex[current_index];
            ++current_index;
        }

    public:
        using token_type = std::pair<Symbol, expression_type>;
        
        Lexer() = delete;
        explicit Lexer( std::string const & lex_str ): str_lex( lex_str ),
            current_index { 0 }, current_character { }, end_of_file{ str_lex.size() }
        {
            assert( end_of_file > 0 );
            update_current_token();
        }
        explicit Lexer( char const *lex_str ): str_lex( lex_str ), current_index { 0 },
            current_character { }, end_of_file{ str_lex.size() }
        {
            assert( end_of_file > 0 );
            update_current_token();
        }
        inline void reset(){
            current_index = 0;
            current_character = ' ';
        }
        inline void set_string( char const *str )
        {
            reset();
            str_lex = std::string { str };
            end_of_file = str_lex.size();
        }

        inline bool eof() {
            return current_character == EOF_F;
        }
        token_type get_negated_constant_or_unary_minus()
        {
            std::string str_buf( 1, current_character );
            update_current_token();
            bool dot_found = false;
            
            if( is_numeric_constant{} ( current_character ) ){
                while( is_numeric_constant{}( current_character ) ){
                    if( current_character == '.' && !dot_found ){
                        dot_found = true;
                    } else if ( current_character == '.' ){
                        panic( str_lex, current_index );
                    }
                    str_buf.push_back( current_character );
                    update_current_token();
                }
                return { Symbol( str_buf ), expression_type::Constant };
            } else {
                return { Symbol( str_buf ), expression_type::Minus };
            }
        }

        token_type get_constant_token()
        {
            std::string str_buf( 1, current_character );
            update_current_token();
            bool dot_found = false;

            while( is_numeric_constant{} ( current_character ) ){
                if( current_character == '.' && !dot_found ){
                    dot_found = true;
                } else if ( current_character == '.' ){
                    update_current_token();
                    continue;
                }
                str_buf.push_back( current_character );
                update_current_token();
            }
            return { Symbol { str_buf }, expression_type::Constant };
        }
        
        token_type get_variable_token()
        {
            std::string str_buf { };
            is_alphabet is_alpha {};
            if( is_alpha ( current_character ) ){
                str_buf.push_back( current_character );
                update_current_token();
                
                while( is_alphanumeric{} ( current_character ) ){
                    str_buf.push_back( current_character );
                    update_current_token();
                }
            }
            update_current_token();
            return { Symbol { str_buf }, expression_type::Variable };
        }
        
        token_type get_token()
        {
            for( ; ; ){
                switch( current_character ){
                    case EOF_F:
                        update_current_token();
                        return { Symbol {}, expression_type::None };
                    case '|': case ' ':
                        update_current_token();
                        break;
                    case '*':
                        update_current_token();
                        return { Symbol { "*" }, expression_type::Multiplies };
                    case '/':
                        update_current_token();
                        return { Symbol { "/" }, expression_type::Divides };
                    case '+':
                        update_current_token();
                        return { Symbol { "+" }, expression_type::Plus };
                    case '-':
                        return get_negated_constant_or_unary_minus();
                    case '1': case '2': case '3': case '4': case '5': case '6': case '7': case '8': case '9': case '0':
                        return get_constant_token();
                    default:
                        return get_variable_token();
                }
            }
        }
    };
} // namespace BuildExpression

#endif

main.cpp

#include "expression_io.hpp"

#include <iostream>
#include <fstream>

using namespace Expression;

int main( int argc , char *argv[] )
{
    expr_ptr root1 =  make_plus( make_sin( make_variable<0>( ) ) ,  make_constant( 2.0 ) );
    std::ofstream fout( "expr1.dot" );
    fout << to_graphviz( root1 );

    std::cout << "Expr1 : " << to_polish( root1 ) << "\n";
    std::cout << "Evaluation yields: " << evaluate_expr( root1 ) << std::endl;
    
    expr_ptr root2 =
        make_multiplies(
            make_plus( make_variable<10>(), make_constant( 1.0 ) ) ,
            make_plus(
                make_plus( make_constant( 11 ) , make_variable<1>( ) ) ,
                make_sin( make_variable<10>( ) )
            ) );
    
    std::ofstream fout2( "expr2.dot" );
    fout2 << to_graphviz( root2 );
    std::cout << "Expr2 : " << to_polish( root2 ) << "\n";
    std::cout << "Evaluation of Expr2: " << evaluate_expr( root2 ) << std::endl;

    auto root3 = from_polish( to_polish( root2 ) );
    
    std::cout << "Evaluation of Expr3: " << evaluate_expr( root3 ) << std::endl;
    std::cout << to_polish( root3 ) << std::endl;

    auto root4 = make_plus( make_plus( make_variable<0>(), make_constant( 1 ) ), make_plus( make_plus( make_constant( -2 ), make_variable<1>() ), make_sin( make_variable<2>() )) ) ;
    
    std::cout << evaluate_expr( linearize( root4 ) )<< std::endl;
    return 0;
}