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  Token(T t, tokType type) : val(t) { this->type=type; }
88 
89  /** \brief The actual value stored
90  */
91  T val;
92  };
93 
94  /** \brief A typedef for a queue of tokens for \ref o2scl::calculator
95  */
96  typedef std::queue<TokenBase*> TokenQueue_t;
97 
98  /** \brief Evaluate a mathematical expression in a string
99 
100  This is based on Brandon Amos' code at
101  https://github.com/bamos/cpp-expression-parser
102  in turn based on Jesse Brown's code at
103  http://www.daniweb.com/software-development/cpp/code/427500/calculator-using-shunting-yard-algorithm .
104 
105  The original code has been modified for use in \o2 .
106  */
107  class calculator {
108 
109  private:
110 
111  /** \brief A map denoting operator precedence
112  */
113  static std::map<std::string, int> opPrecedence;
114 
115  /** \brief Build the operator precedence map
116  */
117  static std::map<std::string, int> buildOpPrecedence();
118 
119  /** \brief Return true if \c is a variable
120  */
121  static bool isvariablechar(char c);
122 
123  public:
124 
125  /** \brief Compile and evaluate \c expr using definitions in
126  \c vars
127  */
128  static double calculate(const char* expr,
129  std::map<std::string, double>* vars = 0,
130  bool debug=false);
131 
132  private:
133 
134  /** \brief Compile and evaluate the expression in \c RPN
135  using definitions in \c vars
136  */
137  static double calculate(TokenQueue_t RPN,
138  std::map<std::string, double>* vars = 0);
139 
140  /** \brief Empty and free memory associated with \c rpn
141 
142  \note This is called by the destructor to free the memory in
143  \ref RPN .
144  */
145  static void cleanRPN(TokenQueue_t& rpn);
146 
147  /** \brief Convert the expression in \c expr to RPN
148  */
149  static TokenQueue_t toRPN(const char* expr,
150  std::map<std::string, double>* vars,
151  bool debug=false,
152  std::map<std::string, int> opPrec=opPrecedence);
153 
154  private:
155 
156  /** \brief The current expression in RPN
157  */
158  TokenQueue_t RPN;
159 
160  public:
161 
162  ~calculator();
163 
164  /** \brief Create an empty calculator object
165  */
167 
168  /** \brief Compile expression \c expr using variables
169  specified in \c vars
170  */
171  calculator(const char* expr,
172  std::map<std::string, double> *vars=0,
173  bool debug=false,
174  std::map<std::string, int> opPrec=opPrecedence);
175 
176  /** \brief Compile expression \c expr using variables
177  specified in \c vars
178  */
179  void compile(const char* expr,
180  std::map<std::string, double> *vars=0,
181  bool debug=false,
182  std::map<std::string, int> opPrec=opPrecedence);
183 
184  /** \brief Evalate the previously compiled expression using
185  variables specified in \c vars
186  */
187  double eval(std::map<std::string, double> *vars=0);
188 
189  /** \brief Convert the RPN expression to a string
190 
191  \note This is mostly useful for debugging
192  */
193  std::string RPN_to_string();
194  };
195 
196 }
197 
198 // End of "#ifndef O2SCL_SHUNTING_YARD_H"
199 #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 class for o2scl::calculator.
Definition: shunting_yard.h:81
T val
The actual value stored.
Definition: shunting_yard.h:91
Token(T t, tokType type)
Create a token of type type with value t.
Definition: shunting_yard.h:87
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.
Definition: shunting_yard.h:96
calculator()
Create an empty calculator object.

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