//http://stackoverflow.com/questions/21638775/tokenizing-an-arithmetic-expression
#include <iostream>
#include <iterator>
#include <string>
#include <stdexcept>
#include <cctype>
#include <sstream>
struct location {
unsigned line;
unsigned col;
location( ) : line( 1 ) , col( 1 ) { }
} ;
enum token_type { token_eof, token_double, token_mul, token_div, token_add, token_sub, token_pow, token_oparam, token_cparam} ;
struct token {
location loc;
std:: string literal;
token_type type;
double value;
token( ) { }
explicit token( location l) : loc( l) , type( token_eof) { }
explicit token( location l, std:: string lit, token_type t) : loc( l) , literal( lit) , type( t) { }
explicit token( location l, std:: string lit, double v) : loc( l) , literal( lit) , type( token_double) , value( v) { }
} ;
std:: ostream & operator<< ( std:: ostream & out, const token& t)
{ return out << t.literal ; }
struct invalid_character : std:: runtime_error {
invalid_character( location loc, char c)
: std:: runtime_error ( "line:" + std:: to_string ( loc.line ) + " col:" + std:: to_string ( c) + " - invalid character " + std:: string ( 1 , c) ) ,
loc( loc) , c( c)
{ }
location loc;
char c;
} ;
struct tokenizer_iterator {
typedef token value_type;
typedef token* pointer;
typedef token& reference;
typedef ptrdiff_t difference_type;
typedef size_t size_type;
typedef std:: output_iterator_tag iterator_category;
tokenizer_iterator( ) : source( nullptr) , loc( ) , cur( ) { }
tokenizer_iterator( std:: istream & source) : source( & source) , loc( ) , cur( ) { load( ) ; }
const token& operator* ( ) const { return cur; }
const token* operator- > ( ) const { return & cur; }
tokenizer_iterator& operator++ ( ) { load( ) ; return * this ; }
tokenizer_iterator operator++ ( int ) { load( ) ; return * this ; }
friend bool operator== ( const tokenizer_iterator& lhs, const tokenizer_iterator& rhs) { return lhs.cur .type == rhs.cur .type ; }
friend bool operator! = ( const tokenizer_iterator& lhs, const tokenizer_iterator& rhs) { return lhs.cur .type ! = rhs.cur .type ; }
private :
void load( ) ;
std:: istream * source;
location loc;
token cur;
} ;
void tokenizer_iterator:: load ( ) {
if ( ! * source)
return ;
char next = source- > peek( ) ;
if ( next== EOF ) {
cur = token( loc) ;
return ;
}
while ( isspace ( next) ) {
if ( next== '\n ' ) {
++ loc.line ;
loc.col = 1 ;
} else
loc.col + = 1 ;
next = source- > get( ) ;
next = source- > peek( ) ;
}
switch ( next) {
case '+' :
next = source- > get( ) ;
loc.col + = 1 ;
cur = token( loc, "+" , token_add) ;
return ;
case '-' :
next = source- > get( ) ;
loc.col + = 1 ;
cur = token( loc, "-" , token_sub) ;
return ;
case '*' :
next = source- > get( ) ;
loc.col + = 1 ;
cur = token( loc, "*" , token_mul) ;
return ;
case '/' :
next = source- > get( ) ;
loc.col + = 1 ;
cur = token( loc, "/" , token_div) ;
return ;
case '^' :
next = source- > get( ) ;
loc.col + = 1 ;
cur = token( loc, "^" , token_pow) ;
return ;
case '(' :
next = source- > get( ) ;
loc.col + = 1 ;
cur = token( loc, "(" , token_oparam) ;
return ;
case ')' :
next = source- > get( ) ;
loc.col + = 1 ;
cur = token( loc, ")" , token_cparam) ;
return ;
case '0' : case '1' : case '2' : case '3' : case '4' : case '5' : case '6' : case '7' : case '8' : case '9' :
{
std:: string num;
location start = loc;
do {
num.push_back ( next) ;
next = source- > get( ) ;
loc.col + = 1 ;
next = source- > peek( ) ;
} while ( isdigit ( next) ) ;
if ( next== '.' ) {
num.push_back ( next) ;
next = source- > get( ) ;
loc.col + = 1 ;
next = source- > peek( ) ;
}
while ( isdigit ( next) ) {
num.push_back ( next) ;
next = source- > get( ) ;
loc.col + = 1 ;
next = source- > peek( ) ;
}
double value = atof ( num.c_str ( ) ) ;
cur = token( start, num, value) ;
return ;
}
default :
throw invalid_character( loc, next) ;
}
}
int main( ) {
std:: istringstream ss;
ss.str ( "3.14 + 3 * (7.7/9.8^32.9 )" ) ;
std:: copy ( tokenizer_iterator( ss) , tokenizer_iterator( ) , std:: ostream_iterator < token> ( std:: cout , "\n " ) ) ;
return 0 ;
}
Ly9odHRwOi8vc3RhY2tvdmVyZmxvdy5jb20vcXVlc3Rpb25zLzIxNjM4Nzc1L3Rva2VuaXppbmctYW4tYXJpdGhtZXRpYy1leHByZXNzaW9uCgojaW5jbHVkZSA8aW9zdHJlYW0+CiNpbmNsdWRlIDxpdGVyYXRvcj4KI2luY2x1ZGUgPHN0cmluZz4KI2luY2x1ZGUgPHN0ZGV4Y2VwdD4KI2luY2x1ZGUgPGNjdHlwZT4KI2luY2x1ZGUgPHNzdHJlYW0+CgpzdHJ1Y3QgbG9jYXRpb24gewogICAgdW5zaWduZWQgbGluZTsKICAgIHVuc2lnbmVkIGNvbDsKICAgIGxvY2F0aW9uKCkgOmxpbmUoMSksIGNvbCgxKSB7fQp9OwoKZW51bSB0b2tlbl90eXBlIHt0b2tlbl9lb2YsIHRva2VuX2RvdWJsZSwgdG9rZW5fbXVsLCB0b2tlbl9kaXYsIHRva2VuX2FkZCwgdG9rZW5fc3ViLCB0b2tlbl9wb3csIHRva2VuX29wYXJhbSwgdG9rZW5fY3BhcmFtfTsKc3RydWN0IHRva2VuIHsKICAgIGxvY2F0aW9uIGxvYzsKICAgIHN0ZDo6c3RyaW5nIGxpdGVyYWw7CiAgICB0b2tlbl90eXBlIHR5cGU7CiAgICBkb3VibGUgdmFsdWU7ICAKCiAgICB0b2tlbigpIHt9CiAgICBleHBsaWNpdCB0b2tlbihsb2NhdGlvbiBsKSA6IGxvYyhsKSwgdHlwZSh0b2tlbl9lb2YpIHt9CiAgICBleHBsaWNpdCB0b2tlbihsb2NhdGlvbiBsLCBzdGQ6OnN0cmluZyBsaXQsIHRva2VuX3R5cGUgdCkgOiBsb2MobCksIGxpdGVyYWwobGl0KSwgdHlwZSh0KSB7fQogICAgZXhwbGljaXQgdG9rZW4obG9jYXRpb24gbCwgc3RkOjpzdHJpbmcgbGl0LCBkb3VibGUgdikgOiBsb2MobCksIGxpdGVyYWwobGl0KSwgdHlwZSh0b2tlbl9kb3VibGUpLCB2YWx1ZSh2KSB7fQp9OwpzdGQ6Om9zdHJlYW0mIG9wZXJhdG9yPDwoc3RkOjpvc3RyZWFtJiBvdXQsIGNvbnN0IHRva2VuJiB0KSAKe3JldHVybiBvdXQgPDwgdC5saXRlcmFsO30KCnN0cnVjdCBpbnZhbGlkX2NoYXJhY3RlciA6IHN0ZDo6cnVudGltZV9lcnJvciB7CiAgICBpbnZhbGlkX2NoYXJhY3Rlcihsb2NhdGlvbiBsb2MsIGNoYXIgYykgCiAgICAgICAgOiBzdGQ6OnJ1bnRpbWVfZXJyb3IoImxpbmU6IitzdGQ6OnRvX3N0cmluZyhsb2MubGluZSkrIiBjb2w6IitzdGQ6OnRvX3N0cmluZyhjKSsiIC0gaW52YWxpZCBjaGFyYWN0ZXIgIiArIHN0ZDo6c3RyaW5nKDEsIGMpKSwKICAgICAgICBsb2MobG9jKSwgYyhjKSAKICAgIHt9CiAgICAKICAgIGxvY2F0aW9uIGxvYzsKICAgIGNoYXIgYzsKfTsKCnN0cnVjdCB0b2tlbml6ZXJfaXRlcmF0b3IgewogICAgdHlwZWRlZiB0b2tlbiB2YWx1ZV90eXBlOwogICAgdHlwZWRlZiB0b2tlbiogcG9pbnRlcjsKICAgIHR5cGVkZWYgdG9rZW4mIHJlZmVyZW5jZTsKICAgIHR5cGVkZWYgcHRyZGlmZl90IGRpZmZlcmVuY2VfdHlwZTsKICAgIHR5cGVkZWYgc2l6ZV90IHNpemVfdHlwZTsKICAgIHR5cGVkZWYgc3RkOjpvdXRwdXRfaXRlcmF0b3JfdGFnIGl0ZXJhdG9yX2NhdGVnb3J5OwogICAgCiAgICB0b2tlbml6ZXJfaXRlcmF0b3IoKSA6IHNvdXJjZShudWxscHRyKSwgbG9jKCksIGN1cigpIHt9CiAgICB0b2tlbml6ZXJfaXRlcmF0b3Ioc3RkOjppc3RyZWFtJiBzb3VyY2UpIDpzb3VyY2UoJnNvdXJjZSksIGxvYygpLCBjdXIoKSB7bG9hZCgpO30KICAgIAogICAgY29uc3QgdG9rZW4mIG9wZXJhdG9yKigpIGNvbnN0IHtyZXR1cm4gY3VyO30KICAgIGNvbnN0IHRva2VuKiBvcGVyYXRvci0+KCkgY29uc3Qge3JldHVybiAmY3VyO30KICAgIHRva2VuaXplcl9pdGVyYXRvciYgb3BlcmF0b3IrKygpIHtsb2FkKCk7IHJldHVybiAqdGhpczt9CiAgICB0b2tlbml6ZXJfaXRlcmF0b3Igb3BlcmF0b3IrKyhpbnQpIHtsb2FkKCk7IHJldHVybiAqdGhpczt9CiAgICBmcmllbmQgYm9vbCBvcGVyYXRvcj09KGNvbnN0IHRva2VuaXplcl9pdGVyYXRvciYgbGhzLCBjb25zdCB0b2tlbml6ZXJfaXRlcmF0b3ImIHJocykge3JldHVybiBsaHMuY3VyLnR5cGU9PXJocy5jdXIudHlwZTt9CiAgICBmcmllbmQgYm9vbCBvcGVyYXRvciE9KGNvbnN0IHRva2VuaXplcl9pdGVyYXRvciYgbGhzLCBjb25zdCB0b2tlbml6ZXJfaXRlcmF0b3ImIHJocykge3JldHVybiBsaHMuY3VyLnR5cGUhPXJocy5jdXIudHlwZTt9CnByaXZhdGU6CiAgICB2b2lkIGxvYWQoKTsKCiAgICBzdGQ6OmlzdHJlYW0qIHNvdXJjZTsKICAgIGxvY2F0aW9uIGxvYzsKICAgIHRva2VuIGN1cjsKfTsKCgoKCgoKCgoKCgoKCgoKCgp2b2lkIHRva2VuaXplcl9pdGVyYXRvcjo6bG9hZCgpIHsKICAgIGlmICghKnNvdXJjZSkKICAgICAgICByZXR1cm47CgogICAgY2hhciBuZXh0ID0gc291cmNlLT5wZWVrKCk7CiAgICBpZiAobmV4dD09RU9GKSB7CiAgICAgICAgY3VyID0gdG9rZW4obG9jKTsKICAgICAgICByZXR1cm47ICAgICAgICAKICAgIH0KICAgIHdoaWxlKGlzc3BhY2UobmV4dCkpIHsKICAgICAgICBpZiAobmV4dD09J1xuJykgewogICAgICAgICAgICArK2xvYy5saW5lOwogICAgICAgICAgICBsb2MuY29sID0gMTsKICAgICAgICB9IGVsc2UgICAgICAgICAgICAKICAgICAgICAgICAgbG9jLmNvbCArPSAxOwogICAgICAgIG5leHQgPSBzb3VyY2UtPmdldCgpOwogICAgICAgIG5leHQgPSBzb3VyY2UtPnBlZWsoKTsKICAgIH0KICAgIHN3aXRjaChuZXh0KSB7CiAgICBjYXNlICcrJzoKICAgICAgICBuZXh0ID0gc291cmNlLT5nZXQoKTsKICAgICAgICBsb2MuY29sICs9IDE7CiAgICAgICAgY3VyID0gdG9rZW4obG9jLCAiKyIsIHRva2VuX2FkZCk7CiAgICAgICAgcmV0dXJuOwogICAgY2FzZSAnLSc6CiAgICAgICAgbmV4dCA9IHNvdXJjZS0+Z2V0KCk7ICAgICAgICAKICAgICAgICBsb2MuY29sICs9IDE7CiAgICAgICAgY3VyID0gdG9rZW4obG9jLCAiLSIsIHRva2VuX3N1Yik7CiAgICAgICAgcmV0dXJuOwogICAgY2FzZSAnKic6CiAgICAgICAgbmV4dCA9IHNvdXJjZS0+Z2V0KCk7CiAgICAgICAgbG9jLmNvbCArPSAxOwogICAgICAgIGN1ciA9IHRva2VuKGxvYywgIioiLCB0b2tlbl9tdWwpOwogICAgICAgIHJldHVybjsKICAgIGNhc2UgJy8nOgogICAgICAgIG5leHQgPSBzb3VyY2UtPmdldCgpOwogICAgICAgIGxvYy5jb2wgKz0gMTsKICAgICAgICBjdXIgPSB0b2tlbihsb2MsICIvIiwgdG9rZW5fZGl2KTsKICAgICAgICByZXR1cm47CiAgICBjYXNlICdeJzoKICAgICAgICBuZXh0ID0gc291cmNlLT5nZXQoKTsKICAgICAgICBsb2MuY29sICs9IDE7CiAgICAgICAgY3VyID0gdG9rZW4obG9jLCAiXiIsIHRva2VuX3Bvdyk7CiAgICAgICAgcmV0dXJuOwogICAgY2FzZSAnKCc6CiAgICAgICAgbmV4dCA9IHNvdXJjZS0+Z2V0KCk7CiAgICAgICAgbG9jLmNvbCArPSAxOwogICAgICAgIGN1ciA9IHRva2VuKGxvYywgIigiLCB0b2tlbl9vcGFyYW0pOwogICAgICAgIHJldHVybjsKICAgIGNhc2UgJyknOgogICAgICAgIG5leHQgPSBzb3VyY2UtPmdldCgpOwogICAgICAgIGxvYy5jb2wgKz0gMTsKICAgICAgICBjdXIgPSB0b2tlbihsb2MsICIpIiwgdG9rZW5fY3BhcmFtKTsKICAgICAgICByZXR1cm47CiAgICBjYXNlICcwJzogY2FzZSAnMSc6IGNhc2UgJzInOiBjYXNlICczJzogY2FzZSAnNCc6IGNhc2UgJzUnOiBjYXNlICc2JzogY2FzZSAnNyc6IGNhc2UgJzgnOiBjYXNlICc5JzoKICAgICAgICB7CiAgICAgICAgICAgIHN0ZDo6c3RyaW5nIG51bTsKICAgICAgICAgICAgbG9jYXRpb24gc3RhcnQgPSBsb2M7CiAgICAKICAgICAgICAgICAgZG8gewogICAgICAgICAgICAgICAgbnVtLnB1c2hfYmFjayhuZXh0KTsKICAgICAgICAgICAgICAgIG5leHQgPSBzb3VyY2UtPmdldCgpOwogICAgICAgICAgICAgICAgbG9jLmNvbCArPSAxOwogICAgICAgICAgICAgICAgbmV4dCA9IHNvdXJjZS0+cGVlaygpOwogICAgICAgICAgICB9IHdoaWxlKGlzZGlnaXQobmV4dCkpOwogICAgICAgICAgICBpZiAobmV4dD09Jy4nKSB7CiAgICAgICAgICAgICAgICBudW0ucHVzaF9iYWNrKG5leHQpOwogICAgICAgICAgICAgICAgbmV4dCA9IHNvdXJjZS0+Z2V0KCk7CiAgICAgICAgICAgICAgICBsb2MuY29sICs9IDE7CiAgICAgICAgICAgICAgICBuZXh0ID0gc291cmNlLT5wZWVrKCk7CiAgICAgICAgICAgIH0KICAgICAgICAgICAgd2hpbGUoaXNkaWdpdChuZXh0KSkgewogICAgICAgICAgICAgICAgbnVtLnB1c2hfYmFjayhuZXh0KTsKICAgICAgICAgICAgICAgIG5leHQgPSBzb3VyY2UtPmdldCgpOwogICAgICAgICAgICAgICAgbG9jLmNvbCArPSAxOwogICAgICAgICAgICAgICAgbmV4dCA9IHNvdXJjZS0+cGVlaygpOwogICAgICAgICAgICB9ICAgICAgICAgICAgIAogICAgCiAgICAgICAgICAgIGRvdWJsZSB2YWx1ZSA9IGF0b2YobnVtLmNfc3RyKCkpOwogICAgICAgICAgICBjdXIgPSB0b2tlbihzdGFydCwgbnVtLCB2YWx1ZSk7CiAgICAgICAgICAgIHJldHVybjsKICAgICAgICB9CiAgICBkZWZhdWx0OgogICAgICAgIHRocm93IGludmFsaWRfY2hhcmFjdGVyKGxvYywgbmV4dCk7CiAgICB9Cn0KCmludCBtYWluKCkgewogICAgc3RkOjppc3RyaW5nc3RyZWFtIHNzOwogICAgc3Muc3RyKCIzLjE0ICsgMyAqICg3LjcvOS44XjMyLjkgICkiKTsKICAgIHN0ZDo6Y29weSh0b2tlbml6ZXJfaXRlcmF0b3Ioc3MpLCB0b2tlbml6ZXJfaXRlcmF0b3IoKSwgc3RkOjpvc3RyZWFtX2l0ZXJhdG9yPHRva2VuPihzdGQ6OmNvdXQsICJcbiIpKTsKICAgIHJldHVybiAwOwp9
compilation info
prog.cpp:45:13: error: ‘ptrdiff_t’ does not name a type
typedef ptrdiff_t difference_type;
^
In file included from /usr/include/c++/4.8/bits/stl_algobase.h:65:0,
from /usr/include/c++/4.8/bits/char_traits.h:39,
from /usr/include/c++/4.8/ios:40,
from /usr/include/c++/4.8/ostream:38,
from /usr/include/c++/4.8/iostream:39,
from prog.cpp:3:
/usr/include/c++/4.8/bits/stl_iterator_base_types.h: In instantiation of ‘struct std::__iterator_traits<tokenizer_iterator, true>’:
/usr/include/c++/4.8/bits/stl_iterator_base_types.h:159:12: required from ‘struct std::iterator_traits<tokenizer_iterator>’
/usr/include/c++/4.8/bits/stl_algobase.h:381:57: required from ‘_OI std::__copy_move_a(_II, _II, _OI) [with bool _IsMove = false; _II = tokenizer_iterator; _OI = std::ostream_iterator<token>]’
/usr/include/c++/4.8/bits/stl_algobase.h:428:38: required from ‘_OI std::__copy_move_a2(_II, _II, _OI) [with bool _IsMove = false; _II = tokenizer_iterator; _OI = std::ostream_iterator<token>]’
/usr/include/c++/4.8/bits/stl_algobase.h:460:17: required from ‘_OI std::copy(_II, _II, _OI) [with _II = tokenizer_iterator; _OI = std::ostream_iterator<token>]’
prog.cpp:172:106: required from here
/usr/include/c++/4.8/bits/stl_iterator_base_types.h:153:53: error: no type named ‘difference_type’ in ‘struct tokenizer_iterator’
typedef typename _Iterator::difference_type difference_type;
^
stdout