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, 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  class calculator {
115 
116  private:
117 
118  /** \brief A map denoting operator precedence
119  */
120  static std::map<std::string, int> opPrecedence;
121 
122  /** \brief Build the operator precedence map
123  */
124  static std::map<std::string, int> buildOpPrecedence();
125 
126  /** \brief Return true if \c is a variable
127  */
128  static bool isvariablechar(char c);
129 
130  public:
131 
132  /** \brief Compile and evaluate \c expr using definitions in
133  \c vars
134  */
135  static double calculate(const char* expr,
136  std::map<std::string, double>* vars = 0,
137  bool debug=false);
138 
139  private:
140 
141  /** \brief Compile and evaluate the expression in \c RPN
142  using definitions in \c vars
143  */
144  static double calculate(TokenQueue_t RPN,
145  std::map<std::string, double>* vars = 0);
146 
147  /** \brief Empty and free memory associated with \c rpn
148 
149  \note This is called by the destructor to free the memory in
150  \ref RPN .
151  */
152  static void cleanRPN(TokenQueue_t& rpn);
153 
154  /** \brief Convert the expression in \c expr to RPN
155  */
156  static TokenQueue_t toRPN(const char* expr,
157  std::map<std::string, double>* vars,
158  bool debug=false,
159  std::map<std::string, int> opPrec=opPrecedence);
160 
161  private:
162 
163  /** \brief The current expression in RPN
164  */
165  TokenQueue_t RPN;
166 
167  public:
168 
169  ~calculator();
170 
171  /** \brief Create an empty calculator object
172  */
174 
175  /** \brief Compile expression \c expr using variables
176  specified in \c vars
177  */
178  calculator(const char* expr,
179  std::map<std::string, double> *vars=0,
180  bool debug=false,
181  std::map<std::string, int> opPrec=opPrecedence);
182 
183  /** \brief Compile expression \c expr using variables
184  specified in \c vars
185  */
186  void compile(const char* expr,
187  std::map<std::string, double> *vars=0,
188  bool debug=false,
189  std::map<std::string, int> opPrec=opPrecedence);
190 
191  /** \brief Evalate the previously compiled expression using
192  variables specified in \c vars
193  */
194  double eval(std::map<std::string, double> *vars=0);
195 
196  /** \brief Convert the RPN expression to a string
197 
198  \note This is mostly useful for debugging
199  */
200  std::string RPN_to_string();
201  };
202 
203 }
204 
205 // End of "#ifndef O2SCL_SHUNTING_YARD_H"
206 #endif
tokType
Token list for o2scl::calculator.
Definition: shunting_yard.h:68
The main O<span style=&#39;position: relative; top: 0.3em; font-size: 0.8em&#39;>2</span>scl O$_2$scl names...
Definition: anneal.h:42
Token(T t, tokType typex)
Create a token of type type with value t.
Definition: shunting_yard.h:91
Token class for o2scl::calculator.
Definition: shunting_yard.h:81
T val
The actual value stored.
Definition: shunting_yard.h:95
Token base data type for o2scl::calculator.
Definition: shunting_yard.h:72
tokType type
The token type.
Definition: shunting_yard.h:75
static std::map< std::string, int > opPrecedence
A map denoting operator precedence.
TokenQueue_t RPN
The current expression in RPN.
Evaluate a mathematical expression in a string.
std::queue< TokenBase * > TokenQueue_t
A typedef for a queue of tokens for o2scl::calculator.
calculator()
Create an empty calculator object.

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