// Leave input empty for a help message #include #include #include #include #include #include #include #include #include #include //#define DEBUG_MODE #define INPUT_MODE // INPUT_MODE can't be on when DEBUG_MODE is on, so disable it again if it is #if defined(DEBUG_MODE) && defined(INPUT_MODE) #undef INPUT_MODE #endif // Enable COMMAND_LINE_MODE if neither modes are defined so that I can do something like // Math "5 * 3" in the console #if !defined(DEBUG_MODE) && !defined(INPUT_MODE) #define COMMAND_LINE_MODE #endif namespace Dennis { namespace ExpressionParser { namespace Constants { using Integer = long long; using Float = long double; // The decimal point used in floating points, e.g. 123.456 or 123,456 constexpr char DecimalPoint = '.'; class numpunct : public std::numpunct { protected: char do_decimal_point() const { return Constants::DecimalPoint; } }; } // A floating point has a bunch of bits that can accurately hold an integer before losing precision, this finds that max integer. // Because the function only returns usable info with floating point, disable the function for non floating points, using std::enable_if template::value>::type* = nullptr> constexpr auto maxFloatIntegralPart() { return ( 1ull << std::numeric_limits::digits ) - 1; } std::string roundFloat( Constants::Float value, int precision = 10 ) { std::ostringstream ss; std::locale loc( std::locale(), new Constants::numpunct ); // std::locale takes ownership ss.imbue( loc ); ss << std::fixed << std::setprecision( precision ) << value; std::string s = ss.str(); std::string rounded; if( auto decimal = s.find( Constants::DecimalPoint ); decimal != std::string::npos ) // C++17, if( init; compare ) { std::string integerPart = s.substr( 0, decimal ); std::string decimalPart = s.substr( decimal + 1 ); // Construct the float, the last finds the position of the last non 0 and cuts of the rest, e.g. 140.1384000000 -> 140.1384 rounded = integerPart + Constants::DecimalPoint + decimalPart.substr( 0, decimalPart.find_last_not_of( '0' ) + 1 ); // If the last character in the rounded string is a decimal point, add a 0 ( 5. -> 5.0 ) if( rounded.back() == Constants::DecimalPoint ) rounded += '0'; } return rounded; } // Custom exception class so that I can only catch ParserErrors and not have other std::exceptions mixed in them class ParserError : public std::runtime_error { public: explicit ParserError( const char* e ) : std::runtime_error(e) {} explicit ParserError( const std::string& e ) : std::runtime_error(e) {} const char* what() const noexcept override { return std::runtime_error::what(); } }; // Utility class so that I don't have to deal with float and integer conversions. class Number { using Float = Constants::Float; using Integer = Constants::Integer; public: Number() = default; // std::enable_if to prevent ambiguity errors // Only call this constructor with floating points template Number( T n, typename std::enable_if::value>::type* = nullptr ) : m_isFloat( true ), m_float( n ), m_integer( n ) {} // Only call this constructor with integrals template Number( T n, typename std::enable_if::value>::type* = nullptr ) : m_isFloat( false ), m_integer( n ), m_float( n ) {} // Copy constructor Number( const Number& other ) : m_isFloat( other.m_isFloat ), m_integer( other.m_integer ), m_float( other.m_float ) {} // Function pointer stuff template Number unaryOperation( UnaryFunction op ) const { Number r; if( m_isFloat ) r = op( m_float ); else r = op( m_integer ); return r; } // More function pointer stuff template Number binaryOperation( const Number& other, BinaryFunction op ) const { Number r; if( m_isFloat || other.m_isFloat ) r = op( m_float, other.m_float ); else r = op( m_integer, other.m_integer ); return r; } // prints the Number using std::cout << N; friend std::ostream& operator<<( std::ostream& os, const Number& n ) { if( n.m_isFloat ) os << roundFloat( n.m_float ); else os << n.m_integer; return os; } void makeInteger() { // Gotta convert the float to an integer as well, might as well chain them m_float = m_integer = m_float; m_isFloat = false; } void makeFloat() { // m_integer is not updated while isFloat is set, so prevent resetting the float to an old integer if makeFloat is called more than once if( !m_isFloat ) m_float = m_integer; m_isFloat = true; } bool isNeg() const noexcept { return isFloat() ? m_float < 0 : m_integer < 0; } bool isFloat() const noexcept { return m_isFloat; } Integer asInteger() const noexcept { return m_integer; } Float asFloat() const noexcept { return m_float; } private: bool m_isFloat = false; Integer m_integer = 0; Float m_float = 0.0; }; enum class Token : unsigned char { None, Add, Subtract, Multiply, Divide, FloorDivide, Integer, Float, Power, Xor, And, Or, Mod, LeftParenthesis, RightParenthesis, ToInt, ToFloat, Symbol, Sqrt, Pie, E, Phi, Sin, Cos, Asin, Acos, Round, Ceil, Floor, Neg, Equal, NotEqual, Less, Bigger, LessOrEqual, BiggerOrEqual, LeftShift, RightShift, Log10, Ln, }; // Maps each symbol to a string const std::map TokenSymbols { { Token::ToInt, "int" }, { Token::ToFloat, "float" }, { Token::Sqrt, "sqrt" }, { Token::Sin, "sin" }, { Token::Cos, "cos" }, { Token::Asin, "asin" }, { Token::Acos, "acos" }, { Token::Round, "round" }, { Token::Ceil, "ceil" }, { Token::Floor, "floor" }, { Token::Log10, "log10" }, { Token::Ln, "ln" }, }; // Maps each constant to a string const std::map TokenConstants { { Token::Pie, "pi" }, { Token::E, "e" }, { Token::Phi, "phi" }, }; // Data for all tokens // Token: TokenName // int32_t: First 4 bits from the left represent operator precedence, 0 means it doesn't matter ( max 15 ) // 5th bit marks if the token is a function // 6th bit marks if the token is a constant // 7th bit marks if the token is a unary operator ( operator that operates on 1 value ) e.g. -5 // 8th bit marks if the token is an operator // 9th bit marks if the token represents a number. e.g. an integer or the constant Pi // 10th bit marks whether the operator is right associative constexpr int BITS = 6; const std::map TokenTable { { Token::None, 0 << BITS | 0b000000 }, { Token::Add, 7 << BITS | 0b000100 }, { Token::Subtract, 7 << BITS | 0b000100 }, { Token::Multiply, 8 << BITS | 0b000100 }, { Token::Divide, 8 << BITS | 0b000100 }, { Token::FloorDivide, 8 << BITS | 0b000100 }, { Token::Integer, 0 << BITS | 0b000010 }, { Token::Float, 0 << BITS | 0b000010 }, { Token::Power, 10 << BITS | 0b000101 }, { Token::Xor, 2 << BITS | 0b000100 }, { Token::And, 3 << BITS | 0b000100 }, { Token::Or, 1 << BITS | 0b000100 }, { Token::Mod, 8 << BITS | 0b000100 }, { Token::LeftParenthesis, 0 << BITS | 0b000000 }, { Token::RightParenthesis, 0 << BITS | 0b000000 }, { Token::ToInt, 15 << BITS | 0b101100 }, { Token::ToFloat, 15 << BITS | 0b101100 }, { Token::Symbol, 0 << BITS | 0b000000 }, { Token::Sqrt, 15 << BITS | 0b101100 }, { Token::Pie, 0 << BITS | 0b010010 }, { Token::E, 0 << BITS | 0b010010 }, { Token::Phi, 0 << BITS | 0b010010 }, { Token::Sin, 15 << BITS | 0b101100 }, { Token::Cos, 15 << BITS | 0b101100 }, { Token::Asin, 15 << BITS | 0b101100 }, { Token::Acos, 15 << BITS | 0b101100 }, { Token::Round, 15 << BITS | 0b101100 }, { Token::Ceil, 15 << BITS | 0b101100 }, { Token::Floor, 15 << BITS | 0b101100 }, { Token::Neg, 14 << BITS | 0b001101 }, { Token::Equal, 4 << BITS | 0b000100 }, { Token::NotEqual, 4 << BITS | 0b000100 }, { Token::Less, 5 << BITS | 0b000100 }, { Token::Bigger, 5 << BITS | 0b000100 }, { Token::LessOrEqual, 5 << BITS | 0b000100 }, { Token::BiggerOrEqual, 5 << BITS | 0b000100 }, { Token::LeftShift, 6 << BITS | 0b000100 }, { Token::RightShift, 6 << BITS | 0b000100 }, { Token::Log10, 15 << BITS | 0b101100 }, { Token::Ln, 15 << BITS | 0b101100 }, }; // Functions that read the bits bool isRightAssociative( Token token ) noexcept { const auto& __tmp = TokenTable.find( token ); if( __tmp == TokenTable.end() ) return false; return __tmp->second & 0x01; } bool isNum( Token token ) noexcept { const auto& __tmp = TokenTable.find( token ); if( __tmp == TokenTable.end() ) return false; return __tmp->second & 0x02; } bool isOp( Token token ) noexcept { const auto& __tmp = TokenTable.find( token ); if( __tmp == TokenTable.end() ) return false; return __tmp->second & 0x04; } bool isUnaryOp( Token token ) noexcept { const auto& __tmp = TokenTable.find( token ); if( __tmp == TokenTable.end() ) return false; return __tmp->second & 0x08; } bool isConst( Token token ) noexcept { const auto& __tmp = TokenTable.find( token ); if( __tmp == TokenTable.end() ) return false; return __tmp->second & 0x10; } bool isFunction( Token token ) noexcept { const auto& __tmp = TokenTable.find( token ); if( __tmp == TokenTable.end() ) return false; return __tmp->second & 0x20; } int8_t opVal( Token token ) noexcept { const auto& __tmp = TokenTable.find( token ); if( __tmp == TokenTable.end() ) return false; return (__tmp->second & 0x3C0) >> BITS; } // Using this instead of std::pair so I can use .token and .number instead of .first and .second struct Pair { Token token; Number number; Pair( Token _token, const Number& _number ) : token( _token ), number( _number ){} }; class Parser { public: // Parses an expression and returns a vector of tokens static std::vector parse( const std::string& expression ); // Transforms a vector of tokens into postfix ( this makes it easier to process later, postfix and prefix has no parenthesis ) static std::vector convertToPostFix( const std::vector& tokens ); // Calculates the final value static Number evaluate( const std::vector& postfix ); // Overload which does all 3 functions above static Number evaluate( const std::string& expression ); private: // Reads out a number. template static Pair scanNumber( Iter& begin, Iter end ); // Reads out a symbol ( names ) template static Token scanSymbol( Iter& begin, Iter end ); // The actual math behind each token static Number doOperation( Token operation, const std::vector& parameters ); // Returns the value associated to a constant token static Number convertConstant( Token token ); }; // Returns the next value of the iterator "it" without accessing out-of-bounds template char next( Iter it, Iter end ) { std::advance( it, 1 ); return it != end ? *it : '\0'; } std::vector Parser::parse( const std::string& expression ) { // No expression means no work :) if( expression.empty() ) return {}; // Allows me to do "string"s instead of std::string( "string" ) using namespace std::literals::string_literals; std::vector tokens; // Gotta keep track of the previous token because some tokens rely on it. e.g. the unary - operator Token prev = Token::None; const auto end = expression.cend(); for( auto it = expression.cbegin(); it != end; ) { // The number of steps the iterator has to move int steps = 0; char c = *it; // Ignore spaces... or anything like a space. e.g. tabs and newlines if( std::isspace( c ) ) { steps = 1; } // Check for symbols, anything that starts with a-zA-Z or an _ else if( std::isalpha( c ) || c == '_' ) { Token token = scanSymbol( it, end ); tokens.push_back( Pair( token, 0 ) ); // No need to update steps because scanSymbol takes it by ref } // Start with operators that require the most characters. e.g. If *- doesn't match anything then we can be sure that * is a seperate token // operator != else if( c == '!' && next( it, end ) == '=' ) { tokens.push_back( Pair( Token::NotEqual, 0 ) ); steps = 2; } // operator == else if( c == '=' && next( it, end ) == '=' ) { tokens.push_back( Pair( Token::Equal, 0 ) ); steps = 2; } // operator << else if( c == '<' && next( it, end ) == '<' ) { tokens.push_back( Pair( Token::LeftShift, 0 ) ); steps = 2; } // operator >> else if( c == '>' && next( it, end ) == '>' ) { tokens.push_back( Pair( Token::RightShift, 0 ) ); steps = 2; } // operator <= else if( c == '<' && next( it, end ) == '=' ) { tokens.push_back( Pair( Token::LessOrEqual, 0 ) ); steps = 2; } // operator >= else if( c == '>' && next( it, end ) == '=' ) { tokens.push_back( Pair( Token::BiggerOrEqual, 0 ) ); steps = 2; } // operator ** else if( c == '*' && next( it, end ) == '*' ) { tokens.push_back( Pair( Token::Power, 0 ) ); steps = 2; } // operator // else if( c == '/' && next( it, end ) == '/' ) { tokens.push_back( Pair( Token::FloorDivide, 0 ) ); steps = 2; } // operator < else if( c == '<' ) { tokens.push_back( Pair( Token::Less, 0 ) ); steps = 1; } // operator > else if( c == '>' ) { tokens.push_back( Pair( Token::Bigger, 0 ) ); steps = 1; } // operator ^ else if( c == '^' ) { tokens.push_back( Pair( Token::Xor, 0 ) ); steps = 1; } // operator & else if( c == '&' ) { tokens.push_back( Pair( Token::And, 0 ) ); steps = 1; } // operator | else if( c == '|' ) { tokens.push_back( Pair( Token::Or, 0 ) ); steps = 1; } // operator % else if( c == '%' ) { tokens.push_back( Pair( Token::Mod, 0 ) ); steps = 1; } // operator unary - else if( c == '-' && ( !isNum( prev ) || prev == Token::None ) ) { tokens.push_back( Pair( Token::Neg, 0 ) ); steps = 1; } // operator + else if( c == '+' && !isOp( prev ) && prev != Token::None ) { tokens.push_back( Pair( Token::Add, 0 ) ); steps = 1; } // operator - else if( c == '-' && !isOp( prev ) && prev != Token::None ) { tokens.push_back( Pair( Token::Subtract, 0 ) ); steps = 1; } // operator * else if( c == '*' ) { tokens.push_back( Pair( Token::Multiply, 0 ) ); steps = 1; } // operator / else if( c == '/' ) { tokens.push_back( Pair( Token::Divide, 0 ) ); steps = 1; } // token ( else if( c == '(' ) { tokens.push_back( Pair( Token::LeftParenthesis, 0 ) ); steps = 1; } // token ) else if( c == ')' ) { tokens.push_back( Pair( Token::RightParenthesis, 0 ) ); steps = 1; } // if c begins with an integer then find out the last digit else if( std::isdigit( c ) || c == '+' || c == Constants::DecimalPoint ) { auto result = scanNumber( it, end ); tokens.push_back( result ); } else { throw ParserError( "parse: Unknown character: "s + c ); } // Don't need to remember left or right parenthesis, because it messes with stuff like (-(5)). if( !tokens.empty() && tokens.back().token != Token::LeftParenthesis && tokens.back().token != Token::RightParenthesis ) prev = tokens.back().token; // Increment it by n steps std::advance( it, steps ); } return tokens; } template Pair Parser::scanNumber( Iter& begin, Iter end ) { using namespace std::literals::string_literals; Token token = Token::None; std::string number; // stores the scanned number bool foundDecimalPoint = false; // marked if a decimal point is found, can't have more than 1 bool scientificNotation = false; // marked if the letter e is found ( 34e4 ) bool f_char = false; // marked if a floating point ends on f. (423.3f) char prev = 0; Iter it = begin; while( it != end ) { char c = *it; // if a space is found, then we reached the end if( std::isspace( c ) ) break; // Found a decimal point if( c == Constants::DecimalPoint ) { // Can't have more than 1 if( foundDecimalPoint ) { throw ParserError( "scanNumber: Encountered a second decimal point." ); } // A decimal point means a floating point token = Token::Float; foundDecimalPoint = true; } else if( std::isdigit( c ) ) { // Mark token as integer unless already marked as a float if( token != Token::Float ) token = Token::Integer; } else if( ( c == '-' || c == '+' ) && ( it == begin || prev == 'e' ) ) { // First character can be a - or a + unless that - or + appears after an e. ( 5e-2 ) } else if( c == 'f' ) { // Can't have more than 1 f's if( f_char ) throw ParserError( "scanNumber: Encountered a second f." ); f_char = true; // f marks the integer as a float, because why not token = Token::Float; } else if( c == 'e' ) { // Can't have more than 1 e's if( scientificNotation ) throw ParserError( "scanNumber: Encountered a second e." ); scientificNotation = true; // e marks the integer as a float token = Token::Float; } else // if anything else is found we also reach the end { break; } // Invalid characters don't reach this point // so just add to the string number += c; prev = c; ++it; } // Update the iterator so that it is reflected outside the function begin = it; // Some error handling for the f character to check if it is the last character and behind a decimal point if( f_char && prev != 'f' ) throw ParserError( "scanNumber: f can only appear last." ); if( f_char && (!foundDecimalPoint && !scientificNotation) ) throw ParserError( "scanNumber: f must appear after a \'"s + Constants::DecimalPoint + "\'."s ); // Handler if token is a floating point if( token == Token::Float ) { // In goes the string std::istringstream iss( number ); std::locale loc( std::locale(), new Constants::numpunct ); // No worries, std::locale takes ownership iss.imbue( loc ); Constants::Float d = 0; // Out comes the float iss >> d; return Pair ( token, d ); } try { // At this point the only remaining token should be an Integer if( token == Token::Integer ) { // stoll can throw if number is not actually a number or is too big return Pair ( token, stoll( number) ); } else { // In case it is not for some reason throw ParserError( "scanNumber: Ended on invalid token." ); } } catch( std::invalid_argument& e ) { // Invalid characters entered throw ParserError( "scanNumber: Ended on invalid token." ); } // Number doesn't fit inside an integer, fall back to a floating point catch( std::out_of_range& e ) { // Convert string to a float Constants::Float result = stold( number ); // Check if result causes a precision loss if( std::abs( result ) >= maxFloatIntegralPart() ) { const std::string roundedNumber = number.substr( 0, std::min( 38ull, number.size() ) ); std::cerr << "Warning: " << roundedNumber << ( roundedNumber.size() == number.size() ? "" : "..." ) << " does not fit inside an integer.\n"; std::cerr << "Falling back to a floating point, the result may be inaccurate." << std::endl; } // Token is no longer an integer token = Token::Float; return Pair ( token, result ); } // Shouldn't reach this point, but who knows throw ParserError( "scanNumber: Reached end of function, unknown error occurred." ); } template Token Parser::scanSymbol( Iter& begin, Iter end ) { using namespace std::literals::string_literals; bool first = true; // Marks the first character std::string symbolName; // Stores symbol name Iter it = begin; while( it != end ) { char c = *it; // First character cannot be a digit, 2nd and after can be a digit if( std::isalpha( c ) || c == '_' || ( !first && std::isdigit( c ) ) ) { symbolName += c; } else // Break at any invalid character { break; } first = false; ++it; } // Update the iterator so that it is reflected outside the function begin = it; // Make the string case incensitive by converting the entire string to lower case std::transform( symbolName.begin(), symbolName.end(), symbolName.begin(), []( char c ){ return std::tolower( c ); } ); // Check constants, these don't require a '(' to follow them for( const auto& i : TokenConstants ) if( i.second == symbolName ) return i.first; bool validFunction = false; // If it is a function then check if there is a '(' following while( it != end ) { char c = *it; // ignore spaces if( std::isspace( c ) ) { ++it; // goto next character continue; } // The very next character that is not a space must be a '(' if( c == '(' ) validFunction = true; break; } // No '(' found if( !validFunction ) throw ParserError( "scanSymbol: a function must follow with a \'(\'!" ); // Update the iterator outside again begin = it; // Check if symbol exists for( const auto& i : TokenSymbols ) if( i.second == symbolName ) return i.first; // Doesn't exist, throw throw ParserError( "Unknown symbol: "s + symbolName ); } std::vector Parser::convertToPostFix( const std::vector& tokens ) { // Check out https://en.wikipedia.org/wiki/Reverse_Polish_notation // and https://en.wikipedia.org/wiki/Shunting-yard_algorithm using namespace std::literals::string_literals; std::vector postfix; std::stack s; for( const auto& i : tokens ) { Token token = i.token; if( isNum( token ) ) { postfix.push_back( i ); } else if( token == Token::LeftParenthesis ) { s.push( token ); } else if( token == Token::RightParenthesis ) { while( !s.empty() && s.top() != Token::LeftParenthesis ) { postfix.push_back( { s.top(), 0 } ); s.pop(); } if( s.empty() ) throw ParserError( "convertToPostFix: Found a \')\' without a \'(\'" ); if( s.top() == Token::LeftParenthesis ) s.pop(); } else if( isOp( token ) ) { if( s.empty() || s.top() == Token::LeftParenthesis ) { s.push( token ); } else { while( ( !s.empty() ) && ( isFunction( s.top() ) || ( opVal( token ) < opVal( s.top() ) ) || ( opVal( token ) == opVal( s.top() ) && !isRightAssociative( s.top() ) ) && ( s.top() != Token::LeftParenthesis )) ) { postfix.push_back( { s.top(), 0 } ); s.pop(); } s.push( token ); } } else { throw ParserError( "convertToPostFix: None of the cases matched." ); } } while( !s.empty() ) { if( s.top() == Token::LeftParenthesis ) throw ParserError( "convertToPostFix: \'(\' left in stack."s ); postfix.push_back( { s.top(), 0 } ); s.pop(); } return postfix; } // The actual math :) // std::vector so that I hopefully extend the function to allow for more than 2 parameters later... If need be. Number Parser::doOperation( Token operation, const std::vector& parameters ) { Number result; // Pointers cause they can point to null // lhs = left hand side // rhs = right " " const Number* rhs = parameters.size() > 1 ? ¶meters[1] : nullptr; const Number* lhs = parameters.size() > 0 ? ¶meters[0] : nullptr; if( isUnaryOp( operation ) && !lhs ) throw ParserError( "doOperation: lhs is null in a unary op" ); if( !isUnaryOp( operation ) && isOp( operation ) && !lhs && !rhs ) throw ParserError( "doOperation: lhs and rhs are null in a binary op" ); if( !isUnaryOp( operation ) && isOp( operation ) && !lhs ) throw ParserError( "doOperation: lhs is null in a binary op" ); if( !isUnaryOp( operation ) && isOp( operation ) && !rhs ) throw ParserError( "doOperation: rhs is null in a binary op" ); // Tell GCC to ignore floating point comparisons because I don't care here #ifdef __GNUC__ #pragma GCC diagnostic push #pragma GCC diagnostic ignored "-Wfloat-equal" #endif switch( operation ) { // Obvious stuff // -- Just a load of lambdas case Token::ToInt: result = *lhs; result.makeInteger(); break; case Token::ToFloat: result = *lhs; result.makeFloat(); break; case Token::Sqrt: if( lhs->isNeg() ) throw ParserError( "Error: Cannot apply sqrt on a negative value." ); result = lhs->unaryOperation( []( Constants::Float a ){ return std::sqrt( a ); } ); break; case Token::Sin: result = lhs->unaryOperation( []( Constants::Float a ){ return std::sin( a ); } ); break; case Token::Cos: result = lhs->unaryOperation( []( Constants::Float a ){ return std::cos( a ); } ); break; case Token::Asin: result = lhs->unaryOperation( []( Constants::Float a ){ return std::asin( a ); } ); break; case Token::Acos: result = lhs->unaryOperation( []( Constants::Float a ){ return std::acos( a ); } ); break; case Token::Round: result = lhs->unaryOperation( []( Constants::Float a ){ return std::round( a ); } ); break; case Token::Ceil: result = lhs->unaryOperation( []( Constants::Float a ){ return std::ceil( a ); } ); break; case Token::Floor: result = lhs->unaryOperation( []( Constants::Float a ){ return std::floor( a ); } ); break; case Token::Log10: result = lhs->unaryOperation( []( Constants::Float a ){ return std::log10( a ); } ); break; case Token::Ln: result = lhs->unaryOperation( []( Constants::Float a ){ return std::log( a ); } ); break; case Token::Neg: result = lhs->unaryOperation( []( auto a ){ return -a; } ); break; case Token::Power: { result = lhs->binaryOperation( *rhs, []( auto a, auto b ){ return std::pow( a, b ); } ); Constants::Float tmp = result.asFloat(); if( (Constants::Integer)tmp == tmp ) { // Convert to Integer if result doesn't contain decimals result.makeInteger(); } break; } case Token::Xor: if( lhs->isFloat() || rhs->isFloat() ) throw ParserError("Error: Cannot use \'xor\' on a floating point."); result = lhs->binaryOperation( *rhs, []( Constants::Integer a, Constants::Integer b ){ return a ^ b; } ); break; case Token::And: if( lhs->isFloat() || rhs->isFloat() ) throw ParserError("Error: Cannot use \'and\' on a floating point."); result = lhs->binaryOperation( *rhs, []( Constants::Integer a, Constants::Integer b ){ return a & b; } ); break; case Token::Or: if( lhs->isFloat() || rhs->isFloat() ) throw ParserError("Error: Cannot use \'or\' on a floating point."); result = lhs->binaryOperation( *rhs, []( Constants::Integer a, Constants::Integer b ){ return a | b; } ); break; case Token::LeftShift: if( lhs->isFloat() || rhs->isFloat() ) throw ParserError("Error: Cannot use \'<<\' on a floating point."); result = lhs->binaryOperation( *rhs, []( Constants::Integer a, Constants::Integer b ){ return a << b; } ); break; case Token::RightShift: if( lhs->isFloat() || rhs->isFloat() ) throw ParserError("Error: Cannot use \'>>\' on a floating point."); result = lhs->binaryOperation( *rhs, []( Constants::Integer a, Constants::Integer b ){ return a >> b; } ); break; case Token::Mod: if( lhs->isFloat() || rhs->isFloat() ) result = lhs->binaryOperation( *rhs, []( Constants::Float a, Constants::Float b ){ return std::fmod( a, b ); } ); else result = lhs->binaryOperation( *rhs, []( Constants::Integer a, Constants::Integer b ){ return a % b; } ); break; case Token::Add: result = lhs->binaryOperation( *rhs, []( auto a, auto b ){ return a + b; } ); break; case Token::Subtract: result = lhs->binaryOperation( *rhs, []( auto a, auto b ){ return a - b; } ); break; case Token::Multiply: result = lhs->binaryOperation( *rhs, []( auto a, auto b ){ return a * b; } ); break; case Token::Divide: result = lhs->binaryOperation( *rhs, []( auto a, auto b ){ return (Constants::Float)a / b; } ); break; case Token::FloorDivide:result = lhs->binaryOperation( *rhs, []( auto a, auto b ){ return Constants::Integer( a / b ); } ); break; case Token::Equal: if( lhs->isFloat() || rhs->isFloat() ) { std::cerr << "Warning: comparing floating point with == is unsafe!" << std::endl; } result = lhs->binaryOperation( *rhs, []( auto a, auto b ){ return a == b; } ); break; case Token::NotEqual: if( lhs->isFloat() || rhs->isFloat() ) { std::cerr << "Warning: comparing floating point with != is unsafe!" << std::endl; } result = lhs->binaryOperation( *rhs, []( auto a, auto b ){ return a != b; } ); break; case Token::Less: result = lhs->binaryOperation( *rhs, []( auto a, auto b ){ return a < b; } ); break; case Token::Bigger: result = lhs->binaryOperation( *rhs, []( auto a, auto b ){ return a > b; } ); break; case Token::LessOrEqual: result = lhs->binaryOperation( *rhs, []( auto a, auto b ){ return a <= b; } ); break; case Token::BiggerOrEqual: result = lhs->binaryOperation( *rhs, []( auto a, auto b ){ return a >= b; } ); break; default: throw ParserError( "doOperation: Unknown token encountered." ); } #ifdef __GNUC__ #pragma GCC diagnostic pop #endif // Restore old settings return result; } Number Parser::convertConstant( Token token ) { Number result; // The values for Constants switch( token ) { case Token::Pie: result = 3.1415926535897932384626433832795L; break; case Token::E: result = 2.7182818284590452353602874713526L; break; case Token::Phi: result = 1.6180339887498948482045868343656L; break; default: throw ParserError( "convertConstant: token is not a constant." ); } return result; } Number Parser::evaluate( const std::string& expression ) { return evaluate( convertToPostFix( parse( expression ) ) ); } Number Parser::evaluate( const std::vector& postfix ) { // See link at convertToPostFix std::stack s; for( const auto& i : postfix ) { Token token = i.token; if( isNum( token ) ) { s.push( isConst( token ) ? convertConstant( token ) : i.number ); } else if( isOp( token ) ) { std::vector parameters; // Unary operators only require, as the name implies, 1 parameter, binary operator, in-the-name, need 2 int n = isUnaryOp( token ) ? 1 : 2; while( n-- > 0 ) { if( s.empty() ) throw ParserError( "evaluate: stack empty." ); parameters.push_back( s.top() ); s.pop(); } // Reverse because parameters are removed in reverse order, I want them the normal way. std::reverse( parameters.begin(), parameters.end() ); s.push( doOperation( token, parameters ) ); } } if( s.empty() ) throw ParserError( "evaluate: stack empty." ); if( s.size() > 1 ) throw ParserError( "evaluate: more than 1 token left in the stack." ); // Value left on top is the result of the expression Number returnValue = s.top(); // Check for inaccuracy if( returnValue.isFloat() ) { Constants::Float value = returnValue.asFloat(); if( std::abs( value ) >= maxFloatIntegralPart() ) { const std::string number = roundFloat( value ); const std::string roundedNumber = number.substr( 0, std::min( 38ull, number.size() ) ); std::cerr << "Warning: " << roundedNumber << ( roundedNumber.size() == number.size() ? "" : "..." ) << " may be inaccurate." << std::endl; } } return s.top(); } } } void help() { std::cout << "Usage: Enter a math expression e.g. pi - (5.2e2 + -5.3)*log10(200)\n" << "______________________\n\n" << "Available operators are:\n" << "Add: \'+\'\n" << "Subtract: \'-\'\n" << "Multiply: \'*\'\n" << "Divide: \'/\'\n" << "Floor divide: \'//\'\n" << "Power: \'**\'\n" << "Xor: \'^\'\n" << "And: \'&\'\n" << "Or: \'|\'\n" << "Mod: \'%\'\n" << "Equal: \'==\'\n" << "Not Equal: \'!=\'\n" << "Less than: \'<\'\n" << "Bigger than: \'>\'\n" << "Less or Equal: \'<=\'\n" << "Bigger or Equal: \'>=\'\n" << "Left shift: \'<<\'\n" << "Right shift: \'>>\'\n" << "______________________\n\n" << "Available functions are:\n" << "int( n ) // Converts n to an integral\n" << "float( n ) // Converts n to a floating point\n" << "round( n )\n" << "ceil( n )\n" << "floor( n )\n" << "sqrt( n )\n" << "sin( n )\n" << "cos( n )\n" << "asin( n )\n" << "acos( n )\n" << "log10( n )\n" << "ln( n )\n" << "______________________\n\n" << "Available constants are:\n" << "pi \'3.1415926535897932384626433832795\'\n" << "e \'2.7182818284590452353602874713526\'\n" << "phi \'1.6180339887498948482045868343656\'\n" << "______________________" << std::endl; } #ifdef DEBUG_MODE #include #include // Just some function that reads a bunch of expressions from a file and checks 'em void unitTests() { using namespace Dennis::ExpressionParser; std::fstream file( "txt/unitTests.txt" ); if( !file ) { std::cerr << "Cannot load file" << std::endl; return; } std::vector v; std::string tmp; while( std::getline( file, tmp ) ) { if( !tmp.empty() && !( tmp.size() > 2 && tmp[0] == '/' && tmp[1] == '/' ) ) // This skips empty lines and comments { v.push_back( tmp ); } } assert( v.size() % 2 == 0 ); int success = 0; for( int i = 0; i < v.size(); i += 2 ) { try { Number n = Parser::evaluate( Parser::convertToPostFix( Parser::parse( v[i] ) ) ); std::string s = n.isFloat() ? roundFloat( n.asFloat() ) : std::to_string( n.asInteger() ); if( s != v[i+1] ) { std::cerr << "Expression:\t\t" << v[i] << "\nExpected answer:\t" << v[i+1] << "\nGot:\t\t\t" << s << "\n" << std::endl; } else ++success; } catch( ParserError& e ) { if( v[i+1] == "error" ) ++success; else std::cerr << "Expression:\t\t" << v[i] << "\nExpected answer:\t" << v[i+1] << "\nGot:\t\t\t" << e.what() << "\n" << std::endl; } } std::cout << "Total unit tests passed: " << success << " out of " << v.size() / 2 << ". (" << 100 * static_cast(success) / (v.size() / 2) << "%)\n" << std::endl; } #endif int main( int argc, char** argv ) { using namespace Dennis::ExpressionParser; #ifdef DEBUG_MODE try { // Only unit test in DEBUG mode std::cout << "DEBUG BUILD\n"; unitTests(); auto v = Parser::parse( "round( sqrt( -(-4|2+(372*-13&52)>>8%3)**23 - 21144037427 ) )" ); // Prints each token's name in DEBUG mode so that I can see if they are evaluated correctly for( const auto& i : v ) { std::string token = "None"; switch( i.token ) { case Token::None: break; case Token::Add: token = "Add"; break; case Token::Subtract: token = "Subtract"; break; case Token::Multiply: token = "Multiply"; break; case Token::Divide: token = "Divide"; break; case Token::FloorDivide: token = "FloorDivide"; break; case Token::Integer: token = "Integer"; break; case Token::Float: token = "Floating_point"; break; case Token::Power: token = "Power"; break; case Token::Mod: token = "Mod"; break; case Token::Xor: token = "Xor"; break; case Token::And: token = "And"; break; case Token::Or: token = "Or"; break; case Token::LeftParenthesis: token = "LeftParenthesis"; break; case Token::RightParenthesis: token = "RightParenthesis"; break; case Token::ToInt: token = "ToInt"; break; case Token::ToFloat: token = "ToFloat"; break; case Token::Sqrt: token = "sqrt"; break; case Token::Pie: token = "pie"; break; case Token::Sin: token = "sin"; break; case Token::Cos: token = "cos"; break; case Token::Asin: token = "asin"; break; case Token::Acos: token = "acos"; break; case Token::Neg: token = "Neg"; break; case Token::Equal: token = "Equal"; break; case Token::NotEqual: token = "Not Equal"; break; case Token::Less: token = "Less"; break; case Token::Bigger: token = "Bigger"; break; case Token::LessOrEqual: token = "LessOrEqual"; break; case Token::BiggerOrEqual: token = "BiggerOrEqual"; break; case Token::LeftShift: token = "LeftShift"; break; case Token::RightShift: token = "Rightshift"; break; case Token::Log10: token = "Log10"; break; case Token::Ln: token = "Ln"; break; case Token::Round: token = "Round"; break; case Token::Ceil: token = "Ceil"; break; case Token::Floor: token = "Floor"; break; default: token = "Unknown"; } std::cout << token; if( isNum( i.token ) ) { std::cout << ' ' << i.number; } std::cout << '\n'; } std::cout << "\n"; Number result = Parser::evaluate( Parser::convertToPostFix( v ) ); std::cout << "\n= "; std::cout << result << '\n'; } catch( ParserError& e ) { // Woops std::cerr << e.what() << "\n" << std::endl; return -1; } return 0; #endif #ifdef INPUT_MODE // Only get input when in INPUT mode std::string input; std::getline( std::cin, input ); if( input.empty() ) { help(); return 1; } #elif defined(COMMAND_LINE_MODE) // Get input from command line if( argc != 2 ) { std::cerr << "Expecting 1 argument from command line" << std::endl; return -2; } if( argc > 1 && argv[1][0] == '/' || argv[1][0] == '-' ) { if( std::strcmp( argv[1] + 1, "?" ) == 0 ) // /? or -? option displays help message help(); else std::cerr << "Unrecognized command" << std::endl; return 1; } #endif #ifndef DEBUG_MODE try { #ifdef INPUT_MODE auto v = Parser::evaluate( input ); #elif defined(COMMAND_LINE_MODE) auto v = Parser::evaluate( std::string( argv[1] ) ); #endif Number result = v; #ifdef INPUT_MODE std::cout << "Expression: \"" << input << "\"\n"; #endif std::cout << "\n= "; std::cout << result << std::endl; } catch( ParserError& e ) { // Woops std::cerr << e.what() << std::endl; #ifdef INPUT_MODE help(); #endif return -1; } #endif return 0; } #ifdef INPUT #define x(n) std::cin >> n; #endif

Math Expression Parser