ParseExp.cpp

Go to the documentation of this file.
00001 // -*- c-basic-offset: 4 -*-
00002 
00011 /*  This program is free software; you can redistribute it and/or
00012  *  modify it under the terms of the GNU General Public
00013  *  License as published by the Free Software Foundation; either
00014  *  version 2 of the License, or (at your option) any later version.
00015  *
00016  *  This software is distributed in the hope that it will be useful,
00017  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
00018  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00019  *  General Public License for more details.
00020  *
00021  *  You should have received a copy of the GNU General Public
00022  *  License along with this software. If not, see
00023  *  <http://www.gnu.org/licenses/>.
00024  *
00025  */
00026 
00027 #include "ParseExp.h"
00028 
00029 // parser using shunting yard algorithm using C++11 features
00030 
00031 #include <exception>
00032 #include <stack>
00033 #include <queue>
00034 #include <functional>
00035 #define _USE_MATH_DEFINES
00036 #include <math.h>
00037 #include <cstdlib>
00038 
00039 namespace Parser
00040 {
00042 class ParseException : public std::runtime_error
00043 {
00044 public:
00045     explicit ParseException(const char *message) : std::runtime_error(message) {};
00046 };
00047 
00049 namespace RPNTokens
00050 {
00052 class TokenBase
00053 {
00054 public:
00055     virtual void evaluate(std::stack<double>&) = 0;
00056     virtual ~TokenBase() {};
00057 };
00058 
00060 class NumericToken :public TokenBase
00061 {
00062 public:
00063     explicit NumericToken(double val) : m_value(val) {};
00064     void evaluate(std::stack<double>& rpnStack) { rpnStack.push(m_value); };
00065 private:
00066     double m_value;
00067 };
00068 
00070 class FunctionToken : public TokenBase
00071 {
00072 public:
00073     explicit FunctionToken(std::function<double(double)> func) : TokenBase(), m_function(func) {};
00074     void evaluate(std::stack<double>& rpnStack)
00075     {
00076         if (rpnStack.empty())
00077         {
00078             throw ParseException("Unary operator expects one item on stack.");
00079         }
00080         const double val = rpnStack.top();
00081         rpnStack.pop();
00082         const double newVal = m_function(val);
00083         if (!isinf(newVal) && !isnan(newVal))
00084         {
00085             rpnStack.push(newVal);
00086         }
00087         else
00088         {
00089             throw ParseException("Invalid operation");
00090         };
00091     };
00092 private:
00093     std::function<double(double)> m_function;
00094 };
00095 
00097 class BinaryToken : public TokenBase
00098 {
00099 public:
00100     explicit BinaryToken(std::function<double(double, double)> func) : TokenBase(), m_function(func) {};
00101     void evaluate(std::stack<double>& rpnStack)
00102     {
00103         if (rpnStack.size() < 2)
00104         {
00105             throw ParseException("BinaryOperator expects 2 items on stack.");
00106         };
00107         const double right = rpnStack.top();
00108         rpnStack.pop();
00109         const double left = rpnStack.top();
00110         rpnStack.pop();
00111         const double newVal = m_function(left, right);
00112         if (!isinf(newVal) && !isnan(newVal))
00113         {
00114             rpnStack.push(newVal);
00115         }
00116         else
00117         {
00118             throw ParseException("Invalid operation");
00119         };
00120     };
00121 private:
00122     std::function<double(double, double)> m_function;
00123 };
00124 
00126 class IfToken : public TokenBase
00127 {
00128 public:
00129     void evaluate(std::stack<double>& rpnStack)
00130     {
00131         if (rpnStack.size() < 3)
00132         {
00133             throw ParseException("IfOperator expects 3 items on stack.");
00134         };
00135         const double elseVal = rpnStack.top();
00136         rpnStack.pop();
00137         const double ifVal = rpnStack.top();
00138         rpnStack.pop();
00139         const double compareVal = rpnStack.top();
00140         rpnStack.pop();
00141         if (fabs(compareVal) > 1e-8)
00142         {
00143             rpnStack.push(ifVal);
00144         }
00145         else
00146         {
00147             rpnStack.push(elseVal);
00148         };
00149     };
00150 };
00151 } // namespace RPNTokens
00152 
00154 namespace Operators
00155 {
00157 class OperatorBase
00158 {
00159 public:
00160     OperatorBase(int prec, bool rightAssoc = false) : m_precedence(prec), m_rightAssoc(rightAssoc) {};
00161     virtual ~OperatorBase() {};
00162     const int GetPrecedence() const { return m_precedence; };
00163     const bool IsRightAssociative() const { return m_rightAssoc; };
00164     bool ComparePrecedence(const OperatorBase* other)
00165     {
00166         if (IsRightAssociative())
00167         {
00168             return GetPrecedence() < other->GetPrecedence();
00169         }
00170         else
00171         {
00172             return GetPrecedence() <= other->GetPrecedence();
00173         };
00174     };
00175     virtual RPNTokens::TokenBase* GetTokenBase() { return nullptr; };
00176 private:
00177     int m_precedence;
00178     bool m_rightAssoc;
00179 };
00180 
00182 class FunctionOperator : public OperatorBase
00183 {
00184 public:
00185     FunctionOperator(std::function<double(double)> func, int prec = -2, bool rightAssoc = false) : OperatorBase(prec, rightAssoc), m_function(func) {};
00186     RPNTokens::TokenBase* GetTokenBase() { return new RPNTokens::FunctionToken(m_function); };
00187 private:
00188     std::function<double(double)> m_function;
00189 };
00190 
00192 class BinaryOperator : public OperatorBase
00193 {
00194 public:
00195     BinaryOperator(std::function<double(double, double)> func, int prec, bool rightAssoc = false) : OperatorBase(prec, rightAssoc), m_function(func) {};
00196     RPNTokens::TokenBase* GetTokenBase() { return new RPNTokens::BinaryToken(m_function); };
00197 private:
00198     std::function<double(double, double)> m_function;
00199 };
00200 
00202 class IfOperator : public OperatorBase
00203 {
00204 public:
00205     IfOperator() : OperatorBase(0, true) {};
00206     RPNTokens::TokenBase* GetTokenBase() { return new RPNTokens::IfToken(); }
00207 };
00208 }; // namespace Operators
00209 
00211 void ClearQueue(std::queue<RPNTokens::TokenBase*>& input)
00212 {
00213     while (!input.empty())
00214     {
00215         delete input.front();
00216         input.pop();
00217     }
00218 }
00219 
00221 std::string RemoveWhiteSpaces(const std::string& text)
00222 {
00223     std::string output;
00224     output.reserve(text.size());
00225     for (auto c : text)
00226     {
00227         if (!isspace(c))
00228         {
00229             output.push_back(tolower(c));
00230         };
00231     };
00232     return output;
00233 };
00234 
00235 static std::map<std::string, Operators::OperatorBase*> supportedBinaryOperations;
00236 static Operators::OperatorBase* parenthesesOperator = nullptr;
00237 static Operators::OperatorBase* ifOperator = nullptr;
00238 static Operators::OperatorBase* ifOperatorClose = nullptr;
00239 static std::map<std::string, Operators::FunctionOperator*> supportedFunctions;
00240 
00242 void InitParser()
00243 {
00244     if (supportedBinaryOperations.empty())
00245     {
00246         supportedBinaryOperations["||"] = new Operators::BinaryOperator(std::logical_or<double>(), 2);
00247         supportedBinaryOperations["&&"] = new Operators::BinaryOperator(std::logical_and<double>(), 3);
00248         supportedBinaryOperations["=="] = new Operators::BinaryOperator(std::equal_to<double>(), 4);
00249         supportedBinaryOperations["!="] = new Operators::BinaryOperator(std::not_equal_to<double>(), 4);
00250         supportedBinaryOperations["<"] = new Operators::BinaryOperator(std::less<double>(), 5);
00251         supportedBinaryOperations["<="] = new Operators::BinaryOperator(std::less_equal<double>(), 5);
00252         supportedBinaryOperations[">"] = new Operators::BinaryOperator(std::greater<double>(), 5);
00253         supportedBinaryOperations[">="] = new Operators::BinaryOperator(std::greater_equal<double>(), 5);
00254         supportedBinaryOperations["+"] = new Operators::BinaryOperator(std::plus<double>(), 6);
00255         supportedBinaryOperations["-"] = new Operators::BinaryOperator(std::minus<double>(), 6);
00256         supportedBinaryOperations["*"] = new Operators::BinaryOperator(std::multiplies<double>(), 7);
00257         supportedBinaryOperations["/"] = new Operators::BinaryOperator(std::divides<double>(), 7);
00258         supportedBinaryOperations["%"] = new Operators::BinaryOperator((double(*)(double, double))fmod, 7);
00259         supportedBinaryOperations["^"] = new Operators::BinaryOperator((double(*)(double, double))pow, 8, true);
00260         supportedBinaryOperations["UNARY_MINUS"] = new Operators::FunctionOperator([](double val)->double {return -1 * val; }, 9, true);
00261     }
00262     if (!parenthesesOperator)
00263     {
00264         parenthesesOperator = new Operators::OperatorBase(-1);
00265     };
00266     if (!ifOperator)
00267     {
00268         ifOperator = new Operators::OperatorBase(1);
00269     }
00270     if (!ifOperatorClose)
00271     {
00272         ifOperatorClose = new Operators::IfOperator();
00273     }
00274     if (supportedFunctions.empty())
00275     {
00276         supportedFunctions["abs"] = new Operators::FunctionOperator((double(*)(double))abs);
00277         supportedFunctions["sin"] = new Operators::FunctionOperator((double(*)(double))sin);
00278         supportedFunctions["cos"] = new Operators::FunctionOperator((double(*)(double))cos);
00279         supportedFunctions["tan"] = new Operators::FunctionOperator((double(*)(double))tan);
00280         supportedFunctions["asin"] = new Operators::FunctionOperator((double(*)(double))asin);
00281         supportedFunctions["acos"] = new Operators::FunctionOperator((double(*)(double))acos);
00282         supportedFunctions["atan"] = new Operators::FunctionOperator((double(*)(double))atan);
00283         supportedFunctions["exp"] = new Operators::FunctionOperator((double(*)(double))exp);
00284         supportedFunctions["log"] = new Operators::FunctionOperator((double(*)(double))log);
00285         supportedFunctions["ceil"] = new Operators::FunctionOperator((double(*)(double))ceil);
00286         supportedFunctions["floor"] = new Operators::FunctionOperator((double(*)(double))floor);
00287         supportedFunctions["sqrt"] = new Operators::FunctionOperator((double(*)(double))sqrt);
00288         supportedFunctions["deg"] = new Operators::FunctionOperator([](double val)->double { return val * 180.0f / M_PI; });
00289         supportedFunctions["rad"] = new Operators::FunctionOperator([](double val)->double { return val * M_PI / 180.0f; });
00290     }
00291 };
00292 
00294 void CleanUpParser()
00295 {
00296     for (auto it : supportedBinaryOperations)
00297     {
00298         delete it.second;
00299     };
00300     supportedBinaryOperations.clear();
00301     for (auto it : supportedFunctions)
00302     {
00303         delete it.second;
00304     };
00305     supportedFunctions.clear();
00306     if (parenthesesOperator)
00307     {
00308         delete parenthesesOperator;
00309         parenthesesOperator = nullptr;
00310     };
00311     if (ifOperator)
00312     {
00313         delete ifOperator;
00314         ifOperator = nullptr;
00315     };
00316     if (ifOperatorClose)
00317     {
00318         delete ifOperatorClose;
00319         ifOperatorClose = nullptr;
00320     };
00321 };
00322 
00324 std::string FindOperator(const std::string& searchString)
00325 {
00326     std::string foundOperator;
00327     for (auto it : supportedBinaryOperations)
00328     {
00329         const std::string op(it.first);
00330         if (searchString.compare(0, op.length(), op) == 0)
00331         {
00332             if (op.length() > foundOperator.length())
00333             {
00334                 foundOperator = op;
00335             }
00336         };
00337     };
00338     return foundOperator;
00339 };
00340 
00343 bool ConvertToRPN(const std::string& expression, const ConstantMap& constants, std::queue<RPNTokens::TokenBase*>& rpn)
00344 {
00345     // initialize some internal variables, don't forget to call CleanUpParser() at the end
00346     InitParser();
00347     size_t pos = 0;
00348     std::stack<Operators::OperatorBase*> operatorStack;
00349     bool lastTokenWasOperator = true;
00350     const size_t expressionLength = expression.length();
00351     while (pos < expressionLength)
00352     {
00353         const char currentChar = expression[pos];
00354         if (lastTokenWasOperator && (currentChar == '+' || currentChar == '-'))
00355         {
00356             // special handling of +/- prefix
00357             if (currentChar == '-')
00358             {
00359                 operatorStack.push(supportedBinaryOperations["UNARY_MINUS"]);
00360             };
00361             pos++;
00362             lastTokenWasOperator = false;
00363             continue;
00364         }
00365         if (isdigit(currentChar) || currentChar == '.')
00366         {
00367             // parse numbers
00368             size_t index;
00369             double val;
00370             try
00371             {
00372                 val = std::stod(expression.substr(pos), &index);
00373             }
00374             catch (std::invalid_argument)
00375             {
00376                 throw ParseException("Invalid number");
00377             }
00378             catch (std::out_of_range)
00379             {
00380                 throw ParseException("Out of range");
00381             }
00382             index += pos;
00383             rpn.push(new RPNTokens::NumericToken(val));
00384             pos = index;
00385             lastTokenWasOperator = false;
00386             continue;
00387         }
00388         if (isalpha(currentChar))
00389         {
00390             // parse variable or function names
00391             const size_t found = expression.find_first_not_of("abcdefghijklmnopqrstuvwxyz0123456789_", pos);
00392             std::string subString;
00393             if (found != std::string::npos)
00394             {
00395                 subString = expression.substr(pos, found - pos);
00396                 // if next character is '(' we found a function name, otherwise we treat it as variable name
00397                 // all white space have been filtered out before
00398                 if (expression[found] == '(')
00399                 {
00400                     const auto foundFunction = supportedFunctions.find(subString);
00401                     if (foundFunction == supportedFunctions.end())
00402                     {
00403                         throw ParseException("Unknown function");
00404                     };
00405                     operatorStack.push(foundFunction->second);
00406                     operatorStack.push(parenthesesOperator);
00407                     pos = found + 1;
00408                     lastTokenWasOperator = true;
00409                     continue;
00410                 };
00411             }
00412             else
00413             {
00414                 // no further character in string, it can only be a variable name
00415                 subString = expression.substr(pos);
00416             };
00417             const auto foundVar = constants.find(subString);
00418             if (foundVar == constants.end())
00419             {
00420                 throw ParseException("Unknown variable");
00421             };
00422             rpn.push(new RPNTokens::NumericToken(foundVar->second));
00423             pos = found;
00424             lastTokenWasOperator = false;
00425             continue;
00426         };
00427         if (currentChar == '(')
00428         {
00429             // parse left parenthesis
00430             operatorStack.push(parenthesesOperator);
00431             pos++;
00432             lastTokenWasOperator = true;
00433             continue;
00434         };
00435         if (currentChar == ')')
00436         {
00437             // closing parenthesis
00438             bool matchingParenthesis = false;
00439             while (!operatorStack.empty())
00440             {
00441                 const int topPrecedenece = operatorStack.top()->GetPrecedence();
00442                 if (topPrecedenece == -2)
00443                 {
00444                     throw ParseException("Function without matching parenthesis");
00445                 }
00446                 if (topPrecedenece == -1)
00447                 {
00448                     // we found a matching parenthesis
00449                     matchingParenthesis = true;
00450                     operatorStack.pop();
00451                     break;
00452                 }
00453                 rpn.push(operatorStack.top()->GetTokenBase());
00454                 operatorStack.pop();
00455             }
00456             if (!matchingParenthesis)
00457             {
00458                 throw ParseException("Mismatched parentheses");
00459             };
00460             if (!operatorStack.empty() && operatorStack.top()->GetPrecedence() == -2)
00461             {
00462                 // we found a function on the operator stack
00463                 rpn.push(operatorStack.top()->GetTokenBase());
00464                 operatorStack.pop();
00465             };
00466             pos++;
00467             lastTokenWasOperator = false;
00468             continue;
00469         };
00470         if (currentChar == '?')
00471         {
00472             // we found an start of an ?: expression
00473             while (!operatorStack.empty() && operatorStack.top()->GetPrecedence() > 1)
00474             {
00475                 rpn.push(operatorStack.top()->GetTokenBase());
00476                 operatorStack.pop();
00477             };
00478             operatorStack.push(ifOperator);
00479             pos++;
00480             lastTokenWasOperator = true;
00481             continue;
00482         }
00483         if (currentChar == ':')
00484         {
00485             bool matchingIf = false;
00486             while (!operatorStack.empty())
00487             {
00488                 if (operatorStack.top()->GetPrecedence() == 1)
00489                 {
00490                     matchingIf = true;
00491                     operatorStack.pop();
00492                     break;
00493                 };
00494                 rpn.push(operatorStack.top()->GetTokenBase());
00495                 operatorStack.pop();
00496             }
00497             if (!matchingIf)
00498             {
00499                 throw ParseException("Mismatched ternary operator ?:");
00500             };
00501             operatorStack.push(ifOperatorClose);
00502             pos++;
00503             lastTokenWasOperator = true;
00504             continue;
00505         };
00506         // and finally the operators
00507         const std::string foundOperatorString = FindOperator(expression.substr(pos));
00508         if (foundOperatorString.empty())
00509         {
00510             throw ParseException("Invalid operator or unknown character");
00511         }
00512         Operators::OperatorBase* foundOperator = supportedBinaryOperations[foundOperatorString];
00513         while (!operatorStack.empty() && foundOperator->ComparePrecedence(operatorStack.top()))
00514         {
00515             rpn.push(operatorStack.top()->GetTokenBase());
00516             operatorStack.pop();
00517         };
00518         operatorStack.push(foundOperator);
00519         pos += foundOperatorString.length();
00520         lastTokenWasOperator = true;
00521     };
00522     while (!operatorStack.empty())
00523     {
00524         switch (operatorStack.top()->GetPrecedence())
00525         {
00526             case -2:
00527                 throw ParseException("Function with unbalanced parenthenses");
00528                 break;
00529             case -1:
00530                 throw ParseException("Unbalanced left and right parenthenses");
00531                 break;
00532             case 1:
00533                 throw ParseException("If without else");
00534                 break;
00535         }
00536         rpn.push(operatorStack.top()->GetTokenBase());
00537         operatorStack.pop();
00538     };
00539     return true;
00540 };
00541 
00544 bool EvaluateRPN(std::queue<RPNTokens::TokenBase*>& input, double& result)
00545 {
00546     std::stack<double> stack;
00547     try
00548     {
00549         while (!input.empty())
00550         {
00551             RPNTokens::TokenBase* token = input.front();
00552             token->evaluate(stack);
00553             delete token;
00554             input.pop();
00555         }
00556     }
00557     catch (ParseException)
00558     {
00559         ClearQueue(input);
00560         return false;
00561     };
00562     ClearQueue(input);
00563     if (stack.size() == 1)
00564     {
00565         result = stack.top();
00566         return true;
00567     }
00568     return false;
00569 };
00570 
00572 bool ParseExpression(const std::string& expression, double& result, const ConstantMap& constants)
00573 {
00574     std::queue<RPNTokens::TokenBase*> rpn;
00575     try
00576     {
00577         // remove all white spaces
00578         const std::string inputExpression = RemoveWhiteSpaces(expression);
00579         if (inputExpression.empty())
00580         {
00581             // if expression is now empty, return false
00582             return false;
00583         };
00584         ConstantMap inputConstants(constants);
00585         // add pi
00586         inputConstants["pi"] = M_PI;
00587         // convert expression to reverse polish notation rpn
00588         if (ConvertToRPN(inputExpression, inputConstants, rpn))
00589         {
00590             // if successful, evaluate queue
00591             return EvaluateRPN(rpn, result);
00592         }
00593         else
00594         {
00595             // could not convert to RPN
00596             ClearQueue(rpn);
00597             return false;
00598         };
00599     }
00600     catch (ParseException)
00601     {
00602         //something went wrong, delete queue and return false
00603         ClearQueue(rpn);
00604         return false;
00605     };
00606 };
00607 
00608 } //namespace Parser

Generated on 6 May 2016 for Hugintrunk by  doxygen 1.4.7