shunting_yard.h
Go to the documentation of this file.
1 /*
2  -------------------------------------------------------------------
3 
4  Original author: Jesse Brown
5  Modifications: Brandon Amos, redpois0n
6  Modifications for O2scl copyright (C) 2017-2020, Andrew W. Steiner
7 
8  This file is part of O2scl.
9 
10  O2scl is free software; you can redistribute it and/or modify
11  it under the terms of the GNU General Public License as published by
12  the Free Software Foundation; either version 3 of the License, or
13  (at your option) any later version.
14 
15  O2scl is distributed in the hope that it will be useful,
16  but WITHOUT ANY WARRANTY; without even the implied warranty of
17  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18  GNU General Public License for more details.
19 
20  You should have received a copy of the GNU General Public License
21  along with O2scl. If not, see <http://www.gnu.org/licenses/>.
22 
23  -------------------------------------------------------------------
24 */
25 /*
26  Original cpp-expresion-parser license from Brandon Amos:
27 
28  The MIT License (MIT)
29 
30  Copyright (c) 2013 Brandon Amos <http://bamos.github.io>
31 
32  Permission is hereby granted, free of charge, to any person
33  obtaining a copy of this software and associated documentation files
34  (the "Software"), to deal in the Software without restriction,
35  including without limitation the rights to use, copy, modify, merge,
36  publish, distribute, sublicense, and/or sell copies of the Software,
37  and to permit persons to whom the Software is furnished to do so,
38  subject to the following conditions:
39 
40  The above copyright notice and this permission notice shall be
41  included in all copies or substantial portions of the Software.
42 
43  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
44  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
45  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
46  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
47  BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
48  ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
49  CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
50  SOFTWARE.
51 */
52 #ifndef O2SCL_SHUNTING_YARD_H
53 #define O2SCL_SHUNTING_YARD_H
54 
55 /** \file shunting_yard.h
56  \brief Definitions for \ref o2scl::calculator
57 */
58 
59 #include <map>
60 #include <stack>
61 #include <string>
62 #include <queue>
63 
64 namespace o2scl {
65 
66  /** \brief Token list for \ref o2scl::calculator
67  */
68  enum tokType {NONE,OP,VAR,NUM};
69 
70  /** \brief Token base data type for \ref o2scl::calculator
71  */
72  struct TokenBase {
73  /** \brief The token type
74  */
76  virtual ~TokenBase() {}
77  };
78 
79  /** \brief Token class for \ref o2scl::calculator
80  */
81  template<class T> class Token : public TokenBase {
82 
83  public:
84 
85  /** \brief Create a token of type \c type with value \c t
86 
87  \comment
88  AWS: renamed type to typex to prevent shadow warnings
89  \endcomment
90  */
91  Token(T t, tokType typex) : val(t) { this->type=typex; }
92 
93  /** \brief The actual value stored
94  */
95  T val;
96  };
97 
98  /** \brief A typedef for a queue of tokens for \ref o2scl::calculator
99  */
100  typedef std::queue<TokenBase*> TokenQueue_t;
101 
102  /** \brief Evaluate a mathematical expression in a string
103 
104  This is based on Brandon Amos' code at
105  https://github.com/bamos/cpp-expression-parser
106  in turn based on Jesse Brown's code at
107  http://www.daniweb.com/software-development/cpp/code/427500/calculator-using-shunting-yard-algorithm .
108 
109  The original code has been modified for use in \o2 .
110 
111  \future Add functions atan2, cot, csc, ceil, floor, int, max, min,
112  and maybe if?
113 
114  \warning The nothrow() functions are a naive attempt at
115  more detailed error handling than Amos' original code. I have
116  tried to make sure they don't create any memory leaks, but
117  I have not fully tested this.
118  */
119  class calculator {
120 
121  private:
122 
123  /** \brief A map denoting operator precedence
124  */
125  static std::map<std::string, int> opPrecedence;
126 
127  /** \brief Build the operator precedence map
128  */
129  static std::map<std::string, int> buildOpPrecedence();
130 
131  /** \brief Return true if \c is a variable
132  */
133  static bool isvariablechar(char c);
134 
135  public:
136 
137  /** \brief Compile and evaluate \c expr using definitions in
138  \c vars
139  */
140  static double calculate(const char* expr,
141  std::map<std::string, double>* vars = 0,
142  bool debug=false);
143 
144  /** \brief Compile and evaluate \c expr using definitions in
145  \c vars and return an integer to indicate success or failure
146  */
147  static int calculate_nothrow(const char* expr,
148  std::map<std::string, double>* vars,
149  bool debug, double &result);
150 
151  private:
152 
153  /** \brief Compile and evaluate the expression in \c RPN
154  using definitions in \c vars
155  */
156  static double calculate(TokenQueue_t RPN,
157  std::map<std::string, double>* vars = 0);
158 
159  /** \brief Compile and evaluate the expression in \c RPN using
160  definitions in \c vars and return an integer to indicate
161  success or failure
162  */
164  std::map<std::string, double>* vars,
165  double &result);
166 
167  /** \brief Empty and free memory associated with \c rpn
168 
169  \note This is called by the destructor to free the memory in
170  \ref RPN .
171  */
172  static void cleanRPN(TokenQueue_t &rpn);
173 
174  /** \brief Convert the expression in \c expr to RPN
175  */
176  static TokenQueue_t toRPN(const char* expr,
177  std::map<std::string, double>* vars,
178  bool debug=false,
179  std::map<std::string, int> opPrec=opPrecedence);
180 
181  /** \brief Convert the expression in \c expr to RPN and return an
182  integer to indicate success or failure
183  */
184  static int toRPN_nothrow(const char* expr,
185  std::map<std::string, double>* vars,
186  bool debug,
187  std::map<std::string, int> opPrec,
188  TokenQueue_t &queue2);
189 
190  private:
191 
192  /** \brief The current expression in RPN
193  */
195 
196  public:
197 
198  ~calculator();
199 
200  /** \brief Create an empty calculator object
201  */
203 
204  /** \brief Compile expression \c expr using variables
205  specified in \c vars
206  */
207  calculator(const char* expr,
208  std::map<std::string, double> *vars=0,
209  bool debug=false,
210  std::map<std::string, int> opPrec=opPrecedence);
211 
212  /** \brief Compile expression \c expr using variables
213  specified in \c vars and return an
214  integer to indicate success or failure
215  */
216  void compile(const char* expr,
217  std::map<std::string, double> *vars=0,
218  bool debug=false,
219  std::map<std::string, int> opPrec=opPrecedence);
220 
221  /** \brief Compile expression \c expr using variables
222  specified in \c vars and return an
223  integer to indicate success or failure
224  */
225  int compile_nothrow(const char* expr,
226  std::map<std::string, double> *vars=0,
227  bool debug=false,
228  std::map<std::string, int> opPrec=opPrecedence);
229 
230  /** \brief Evalate the previously compiled expression using
231  variables specified in \c vars
232  */
233  double eval(std::map<std::string, double> *vars=0);
234 
235  /** \brief Evalate the previously compiled expression using
236  variables specified in \c vars
237  */
238  int eval_nothrow(std::map<std::string, double> *vars, double &result);
239 
240  /** \brief Convert the RPN expression to a string
241 
242  \note This is mostly useful for debugging
243  */
244  std::string RPN_to_string();
245  };
246 
247 }
248 
249 // End of "#ifndef O2SCL_SHUNTING_YARD_H"
250 #endif
o2scl::calculator::RPN_to_string
std::string RPN_to_string()
Convert the RPN expression to a string.
o2scl::calculator::calculator
calculator()
Create an empty calculator object.
Definition: shunting_yard.h:202
o2scl::calculator::compile_nothrow
int compile_nothrow(const char *expr, std::map< std::string, double > *vars=0, bool debug=false, std::map< std::string, int > opPrec=opPrecedence)
Compile expression expr using variables specified in vars and return an integer to indicate success o...
o2scl::calculator::eval_nothrow
int eval_nothrow(std::map< std::string, double > *vars, double &result)
Evalate the previously compiled expression using variables specified in vars.
o2scl::calculator::RPN
TokenQueue_t RPN
The current expression in RPN.
Definition: shunting_yard.h:194
o2scl::Token::val
T val
The actual value stored.
Definition: shunting_yard.h:95
o2scl::calculator::isvariablechar
static bool isvariablechar(char c)
Return true if is a variable.
o2scl
The main O<span style='position: relative; top: 0.3em; font-size: 0.8em'>2</span>scl O$_2$scl names...
Definition: anneal.h:42
o2scl::calculator::toRPN_nothrow
static int toRPN_nothrow(const char *expr, std::map< std::string, double > *vars, bool debug, std::map< std::string, int > opPrec, TokenQueue_t &queue2)
Convert the expression in expr to RPN and return an integer to indicate success or failure.
o2scl::calculator::cleanRPN
static void cleanRPN(TokenQueue_t &rpn)
Empty and free memory associated with rpn.
o2scl::calculator::opPrecedence
static std::map< std::string, int > opPrecedence
A map denoting operator precedence.
Definition: shunting_yard.h:125
o2scl::Token
Token class for o2scl::calculator.
Definition: shunting_yard.h:81
o2scl::calculator::calculate
static double calculate(const char *expr, std::map< std::string, double > *vars=0, bool debug=false)
Compile and evaluate expr using definitions in vars.
o2scl::Token::Token
Token(T t, tokType typex)
Create a token of type type with value t.
Definition: shunting_yard.h:91
o2scl::calculator::compile
void compile(const char *expr, std::map< std::string, double > *vars=0, bool debug=false, std::map< std::string, int > opPrec=opPrecedence)
Compile expression expr using variables specified in vars and return an integer to indicate success o...
o2scl::calculator
Evaluate a mathematical expression in a string.
Definition: shunting_yard.h:119
o2scl::TokenQueue_t
std::queue< TokenBase * > TokenQueue_t
A typedef for a queue of tokens for o2scl::calculator.
Definition: shunting_yard.h:100
o2scl::tokType
tokType
Token list for o2scl::calculator.
Definition: shunting_yard.h:68
o2scl::calculator::toRPN
static TokenQueue_t toRPN(const char *expr, std::map< std::string, double > *vars, bool debug=false, std::map< std::string, int > opPrec=opPrecedence)
Convert the expression in expr to RPN.
o2scl::calculator::buildOpPrecedence
static std::map< std::string, int > buildOpPrecedence()
Build the operator precedence map.
o2scl::calculator::eval
double eval(std::map< std::string, double > *vars=0)
Evalate the previously compiled expression using variables specified in vars.
o2scl::TokenBase
Token base data type for o2scl::calculator.
Definition: shunting_yard.h:72
o2scl::TokenBase::type
tokType type
The token type.
Definition: shunting_yard.h:75
o2scl::calculator::calculate_nothrow
static int calculate_nothrow(const char *expr, std::map< std::string, double > *vars, bool debug, double &result)
Compile and evaluate expr using definitions in vars and return an integer to indicate success or fail...

Documentation generated with Doxygen. Provided under the GNU Free Documentation License (see License Information).