// Copyright (c) 2014-2018 Dr. Colin Hirsch and Daniel Frey
// Please see LICENSE for license or visit https://github.com/taocpp/PEGTL/
#include <cassert>
#include <functional>
#include <iostream>
#include <map>
#include <sstream>
#include <vector>
#include <tao/pegtl.hpp>
// Include the analyze function that checks
// a grammar for possible infinite cycles.
#include <tao/pegtl/analyze.hpp>
namespace pegtl = tao::TAO_PEGTL_NAMESPACE;
namespace calculator
{
// This enum is used for the order in which the operators are
// evaluated, i.e. the priority of the operators; a higher
// number indicates a lower priority.
enum class order : int
{
};
// For each binary operator known to the calculator we need an
// instance of the following data structure with the priority,
// and a function that performs the calculation. All operators
// are left-associative.
struct op
{
order p;
std::function< long( long, long ) > f;
};
// Class that takes care of an operand and an operator stack for
// shift-reduce style handling of operator priority; in a
// reduce-step it calls on the functions contained in the op
// instances to perform the calculation.
struct stack
{
void push( const op& b )
{
while( ( !m_o.empty() ) && ( m_o.back().p <= b.p ) ) {
reduce();
}
m_o.push_back( b );
}
void push( const long l )
{
m_l.push_back( l );
}
long finish()
{
while( !m_o.empty() ) {
reduce();
}
assert( m_l.size() == 1 );
const auto r = m_l.back();
m_l.clear();
return r;
}
private:
std::vector< op > m_o;
std::vector< long > m_l;
void reduce()
{
assert( !m_o.empty() );
assert( m_l.size() > 1 );
const auto r = m_l.back();
m_l.pop_back();
const auto l = m_l.back();
m_l.pop_back();
const auto o = m_o.back();
m_o.pop_back();
m_l.push_back( o.f( l, r ) );
}
};
// Additional layer, a "stack of stacks", to clearly show how bracketed
// sub-expressions can be easily processed by giving them a stack of
// their own. Once a bracketed sub-expression has finished evaluation on
// its stack, the result is pushed onto the next higher stack, and the
// sub-expression's temporary stack is discarded. The top-level calculation
// is handled just like a bracketed sub-expression, on the first stack pushed
// by the constructor.
struct stacks
{
stacks()
{
open();
}
void open()
{
m_v.emplace_back();
}
template< typename T >
void push( const T& t )
{
assert( !m_v.empty() );
m_v.back().push( t );
}
void close()
{
assert( m_v.size() > 1 );
const auto r = m_v.back().finish();
m_v.pop_back();
m_v.back().push( r );
}
long finish()
{
assert( m_v.size() == 1 );
return m_v.back().finish();
}
private:
std::vector< stack > m_v;
};
// A wrapper around the data structures that contain the binary
// operators for the calculator.
struct operators
{
operators()
{
// By default we initialise with all binary operators from the C language that can be
// used on integers, all with their usual priority.
insert( "*", order( 5 ), []( const long l, const long r ) { return l * r; } );
insert( "/", order( 5 ), []( const long l, const long r ) { return l / r; } );
insert( "%", order( 5 ), []( const long l, const long r ) { return l % r; } );
insert( "+", order( 6 ), []( const long l, const long r ) { return l + r; } );
insert( "-", order( 6 ), []( const long l, const long r ) { return l - r; } );
insert( "<<", order( 7 ), []( const long l, const long r ) { return l << r; } );
insert( ">>", order( 7 ), []( const long l, const long r ) { return l >> r; } );
insert( "<", order( 8 ), []( const long l, const long r ) { return l < r; } );
insert( ">", order( 8 ), []( const long l, const long r ) { return l > r; } );
insert( "<=", order( 8 ), []( const long l, const long r ) { return l <= r; } );
insert( ">=", order( 8 ), []( const long l, const long r ) { return l >= r; } );
insert( "==", order( 9 ), []( const long l, const long r ) { return l == r; } );
insert( "!=", order( 9 ), []( const long l, const long r ) { return l != r; } );
insert( "&", order( 10 ), []( const long l, const long r ) { return l & r; } );
insert( "^", order( 11 ), []( const long l, const long r ) { return l ^ r; } );
insert( "|", order( 12 ), []( const long l, const long r ) { return l | r; } );
insert( "&&", order( 13 ), []( const long l, const long r ) { return ( ( l != 0 ) && ( r != 0 ) ) ? 1 : 0; } );
insert( "||", order( 14 ), []( const long l, const long r ) { return ( ( l != 0 ) || ( r != 0 ) ) ? 1 : 0; } );
}
// Arbitrary user-defined operators can be added at runtime.
void insert( const std::string& name, const order p, const std::function< long( long, long ) >& f )
{
assert( !name.empty() );
m_ops.insert( { name, { p, f } } );
}
const std::map< std::string, op >& ops() const
{
return m_ops;
}
private:
std::map< std::string, op > m_ops;
};
// Here the actual grammar starts.
using namespace tao::pegtl; // NOLINT
// Comments are introduced by a '#' and proceed to the end-of-line/file.
struct comment
: if_must< one< '#' >, until< eolf > >
{
};
// The calculator ignores all spaces and comments; space is a pegtl rule
// that matches the usual ascii characters ' ', '\t', '\n' etc. In other
// words, everything that is space or a comment is ignored.
struct ignored
: sor< space, comment >
{
};
// Since the binary operators are taken from a runtime data structure
// (rather than hard-coding them into the grammar), we need a custom
// rule that attempts to match the input against the current map of
// operators.
struct infix
{
using analyze_t = analysis::generic< analysis::rule_type::ANY >;
template< apply_mode,
rewind_mode,
template< typename... > class Action,
template< typename... > class Control,
typename Input >
static bool match( Input& in, const operators& b, stacks& s )
{
// Look for the longest match of the input against the operators in the operator map.
return match( in, b, s, std::string() );
}
private:
template< typename Input >
static bool match( Input& in, const operators& b, stacks& s, std::string t )
{
if( in.size( t.size() + 1 ) > t.size() ) {
t += in.peek_char( t.size() );
const auto i = b.ops().lower_bound( t );
if( i != b.ops().end() ) {
if( match( in, b, s, t ) ) {
return true;
}
if( i->first == t ) {
// While we are at it, this rule also performs the task of what would
// usually be an associated action: To push the matched operator onto
// the operator stack.
s.push( i->second );
in.bump( t.size() );
return true;
}
}
}
return false;
}
};
// A number is a non-empty sequence of digits preceeded by an optional sign.
struct number
: seq< opt< one< '+', '-' > >, plus< digit > >
{
};
struct expression;
// A bracketed expression is introduced by a '(' and, in this grammar, must
// proceed with an expression and a ')'.
struct bracket
: if_must< one< '(' >, expression, one< ')' > >
{
};
// An atomic expression, i.e. one without operators, is either a number or
// a bracketed expression.
struct atomic
: sor< number, bracket >
{
};
// An expression is a non-empty list of atomic expressions where each pair
// of atomic expressions is separated by an infix operator and we allow
// the rule ignored as padding (before and after every singlar expression).
struct expression
: list< atomic, infix, ignored >
{
};
// The top-level grammar allows one expression and then expects eof.
struct grammar
: must< expression, eof >
{
};
// After the grammar we proceed with the additional actions that are
// required to let our calculator actually do something.
// The base-case of the class template for the actions must derive from
// pegtl::nothing (or, alternatively, define an action that does something
// sensible for all rules for which no specialisation exists).
template< typename Rule >
struct action
: pegtl::nothing< Rule >
{
};
// This action will be called when the number rule matches; it converts the
// matched portion of the input to a long and pushes it onto the operand
// stack.
template<>
struct action< number >
{
template< typename Input >
static void apply( const Input& in, const operators& /*unused*/, stacks& s )
{
std::stringstream ss;
ss.str( in.string() );
long v;
ss >> v;
s.push( v );
}
};
// The actions for the brackets call functions that create, and collect
// a temporary additional stack for evaluating the bracketed expression.
template<>
struct action< one< '(' > >
{
static void apply0( const operators& /*unused*/, stacks& s )
{
s.open();
}
};
template<>
struct action< one< ')' > >
{
static void apply0( const operators& /*unused*/, stacks& s )
{
s.close();
}
};
} // namespace calculator
int main( int argc, char** argv )
{
// Check the grammar for some possible issues.
pegtl::analyze< calculator::grammar >();
// The objects required as state by the actions.
calculator::stacks s;
calculator::operators b;
for( int i = 1; i < argc; ++i ) {
// Parse and process the command-line arguments as calculator expressions...
pegtl::argv_input<> in( argv, i );
pegtl::parse< calculator::grammar, calculator::action >( in, b, s );
// ...and print the respective results to std::cout.
std::cout << s.finish() << std::endl;
}
return 0;
}