Belle II Software  release-05-02-19
FormulaParser.h
1 /**************************************************************************
2  * BASF2 (Belle Analysis Framework 2) *
3  * Copyright(C) 2018 - Belle II Collaboration *
4  * *
5  * Author: The Belle II Collaboration *
6  * Contributors: Martin Ritter *
7  * *
8  * This software is provided "as is" without any warranty. *
9  **************************************************************************/
10 
11 #pragma once
12 
13 #include <framework/utilities/Utils.h>
14 #include <sstream>
15 #include <variant>
16 #include <stack>
17 #include <string>
18 
19 
20 namespace Belle2 {
29  class FormulaParserBase {
30  public:
33  enum class EOperator : unsigned char {
34  c_noop = 0x00,
35  c_roundBracketOpen = 0x01,
36  c_roundBracketClose = 0x02,
38  c_squareBracketClose = 0x04,
39  c_plus = 0x11,
40  c_minus = 0x12,
41  c_multiply = 0x21,
42  c_divide = 0x22,
43  c_power = 0x31
44  };
45 
47  enum class ENumberStatus {
48  c_Invalid,
49  c_Empty,
50  c_Sign,
51  c_Int,
52  c_Dot,
53  c_LeadingDot,
54  c_Float,
58  };
59 
61  typedef std::variant<std::string, double> InputToken;
62 
64  static char operatorToChar(EOperator op) noexcept;
65 
67  static double applyOperator(EOperator op, double a, double b);
68 
71  static ENumberStatus checkNumber(ENumberStatus current, char next);
72 
74  FormulaParserBase() = default;
75 
77  virtual ~FormulaParserBase() = default;
78  protected:
80  static void assertOperatorUsable(size_t stacksize);
82  virtual void executeOperator(EOperator op) = 0;
84  virtual void addVariable(const InputToken& token) = 0;
86  void processString(const std::string& formula);
89  [[noreturn]] void raiseError(const std::runtime_error& e);
90  private:
94  void addOperator(EOperator op);
97  void flushCurrentVariable();
99  void flushPendingOperators();
101  EOperator checkForOperator(char next);
105  std::istringstream m_buffer;
107  std::string m_currentVariableName;
111  std::stack<EOperator> m_operatorStack;
112  };
113 
114 
136  template<class VariableConstructor> class FormulaParser: public FormulaParserBase {
137  public:
139  typedef typename VariableConstructor::type VariableType;
141  typedef std::variant<VariableType, double> OutputToken;
142 
146  VariableType parse(const std::string& formula)
147  {
148  try {
149  // clear stacks
150  std::stack<OutputToken>().swap(m_outputStack);
151  // process
152  processString(formula);
153  // sanity checks
154  if (m_outputStack.empty())
155  throw std::runtime_error("empty string");
156  if (m_outputStack.size() != 1)
157  throw std::runtime_error("could not parse, stack size not 1, probably a bug, please report");
158  // so return the object
159  return std::visit(Utils::VisitOverload{
160  [](const VariableType & v) -> VariableType {return v;},
161  [](double d) -> VariableType { return VariableConstructor()(d); }
162  }, m_outputStack.top());
163  } catch (std::runtime_error& e) {
164  // add context to error
165  raiseError(e);
166  }
167  }
168  protected:
170  void executeOperator(EOperator op) override
171  {
173  // so far all a binary operators
174  // cppcheck-suppress unreadVariable; used in lambda below
175  OutputToken op2 = m_outputStack.top(); m_outputStack.pop();
176  // cppcheck-suppress unreadVariable; used in lambda below
177  OutputToken op1 = m_outputStack.top(); m_outputStack.pop();
178  // and apply ...
179  m_outputStack.push(std::visit(Utils::VisitOverload{
180  // eagerly apply operations if both operands are numbers
181  [op](double a, double b) -> OutputToken { return OutputToken(applyOperator(op, a, b)); },
182  // otherwise defer to variable constructor
183  [op](auto a, auto b) -> OutputToken { return VariableConstructor()(op, a, b); },
184  }, op1, op2));
185  }
186 
188  void addVariable(const InputToken& var) override
189  {
190  m_outputStack.push(std::visit(Utils::VisitOverload{
191  // if the variable is a string its an identifier and we have to construct a variable from it
192  [](const std::string & s) -> OutputToken { return VariableConstructor()(s); },
193  // otherwise keep as is
194  [](auto s) -> OutputToken { return s; }
195  }, var));
196  }
197 
199  std::stack<OutputToken> m_outputStack;
200  };
201 
205  struct StringFormulaConstructor {
207  typedef std::string type;
210 
212  type operator()(const std::string& name) { return "'" + name + "'"; }
214  type operator()(double value) { return std::to_string(value); }
216  type operator()(Op op, const type& a, const type& b)
217  {
218  return "(" + a + FormulaParserBase::operatorToChar(op) + b + ")";
219  }
221  type operator()(Op op, double a, const type& b) { return (*this)(op, std::to_string(a), b); }
223  type operator()(Op op, const type& a, double b) { return (*this)(op, a, std::to_string(b)); }
224  };
225 
227 }
Belle2::FormulaParserBase::InputToken
std::variant< std::string, double > InputToken
Input token type: an input tokein is either a string or a float variable.
Definition: FormulaParser.h:69
Belle2::FormulaParserBase::m_currentVariableName
std::string m_currentVariableName
collect characters into a variable name
Definition: FormulaParser.h:115
Belle2::FormulaParserBase::EOperator::c_plus
@ c_plus
Addition.
Belle2::FormulaParserBase::EOperator::c_divide
@ c_divide
Division.
Belle2::Utils::VisitOverload
Helper struct for the C++17 std::visit overload pattern to allow simple use of variants.
Definition: Utils.h:19
Belle2::FormulaParserBase::checkForOperator
EOperator checkForOperator(char next)
Check if the next character is a operator.
Definition: FormulaParser.cc:202
Belle2::FormulaParserBase::addVariable
virtual void addVariable(const InputToken &token)=0
Add a variable token to the current state.
Belle2::Utils::VisitOverload
VisitOverload(Ts...) -> VisitOverload< Ts... >
Function for the C++17 std::visit overload pattern to allow simple use of variants.
Belle2::FormulaParserBase::m_operatorStack
std::stack< EOperator > m_operatorStack
Stack of operators for the Shunting-yard algorithm.
Definition: FormulaParser.h:119
Belle2::FormulaParserBase::ENumberStatus::c_Invalid
@ c_Invalid
Not a valid number.
Belle2::FormulaParserBase::EOperator::c_squareBracketOpen
@ c_squareBracketOpen
Open square bracket.
Belle2::FormulaParserBase::EOperator::c_power
@ c_power
Exponentation.
Belle2::FormulaParserBase::ENumberStatus::c_Scientific
@ c_Scientific
exponent followed by sign and digits
Belle2::FormulaParserBase::ENumberStatus::c_Empty
@ c_Empty
Empty string.
Belle2::FormulaParserBase::ENumberStatus::c_Dot
@ c_Dot
[leading sign] + digits + dot
Belle2::FormulaParserBase::ENumberStatus::c_Sign
@ c_Sign
Leading sign.
Belle2::FormulaParserBase::flushCurrentVariable
void flushCurrentVariable()
Flush the currently parsed variable name and add it to the state either as variable or number.
Definition: FormulaParser.cc:183
Belle2::FormulaParser::m_outputStack
std::stack< OutputToken > m_outputStack
Stack of output tokens in the reversh polish notation.
Definition: FormulaParser.h:207
Belle2::FormulaParserBase::addOperator
void addOperator(EOperator op)
Add an operator to the internal state, convert them to reverse polish notation using the shunting yar...
Definition: FormulaParser.cc:121
Belle2::FormulaParserBase::ENumberStatus::c_LeadingDot
@ c_LeadingDot
leading dot without preceding digits
Belle2::FormulaParserBase::EOperator::c_multiply
@ c_multiply
Multiply.
Belle2::FormulaParserBase::ENumberStatus::c_Float
@ c_Float
[leading sign] + [digits] + dot + digits
Belle2::FormulaParser::parse
VariableType parse(const std::string &formula)
Parse the formula and return a varible object of the correct type.
Definition: FormulaParser.h:154
Belle2::FormulaParserBase::checkNumber
static ENumberStatus checkNumber(ENumberStatus current, char next)
Check if a string literal with a given number status continues to be a valid number if next is append...
Definition: FormulaParser.cc:59
Belle2::FormulaParserBase::EOperator::c_roundBracketClose
@ c_roundBracketClose
Close round bracket.
Belle2::FormulaParserBase::EOperator::c_noop
@ c_noop
No operation.
Belle2::FormulaParser::executeOperator
void executeOperator(EOperator op) override
Execute the given operator by taking the operands from the stack and applying the operator to them.
Definition: FormulaParser.h:178
Belle2::FormulaParserBase::m_currentVariableNameNumberStatus
ENumberStatus m_currentVariableNameNumberStatus
State of the current variable name being a valid float literal.
Definition: FormulaParser.h:117
Belle2::FormulaParserBase::applyOperator
static double applyOperator(EOperator op, double a, double b)
Apply operator on two values.
Definition: FormulaParser.cc:46
Belle2::FormulaParserBase::ENumberStatus::c_Exponent
@ c_Exponent
[float] + E or e
Belle2::StringFormulaConstructor::type
std::string type
Create strings as output of FormulaParser.
Definition: FormulaParser.h:215
Belle2::FormulaParserBase::m_lastTokenWasOperator
bool m_lastTokenWasOperator
Bool to check whether there were consecutive operators or variables.
Definition: FormulaParser.h:111
Belle2::FormulaParserBase::flushPendingOperators
void flushPendingOperators()
Flush all pending operators at the end of processing.
Definition: FormulaParser.cc:171
Belle2::FormulaParser::OutputToken
std::variant< VariableType, double > OutputToken
typedef for output tokens on the stack: either a variable or a double
Definition: FormulaParser.h:149
Belle2::FormulaParserBase
Base class with the non-templated part of the formula parser.
Definition: FormulaParser.h:37
Belle2
Abstract base class for different kinds of events.
Definition: MillepedeAlgorithm.h:19
Belle2::FormulaParserBase::ENumberStatus::c_ExponentSign
@ c_ExponentSign
exponent followed by plus or minus
Belle2::FormulaParserBase::m_buffer
std::istringstream m_buffer
Buffer for the formula.
Definition: FormulaParser.h:113
Belle2::FormulaParserBase::processString
void processString(const std::string &formula)
Process the given formula and store the final state.
Definition: FormulaParser.cc:236
Belle2::FormulaParser::VariableType
VariableConstructor::type VariableType
Type of the return variable object.
Definition: FormulaParser.h:147
Belle2::FormulaParserBase::ENumberStatus
ENumberStatus
States of a string literal when checking if it is a valid number.
Definition: FormulaParser.h:55
Belle2::FormulaParserBase::~FormulaParserBase
virtual ~FormulaParserBase()=default
virtual, but empty destructor
Belle2::FormulaParserBase::FormulaParserBase
FormulaParserBase()=default
Default constructor.
Belle2::StringFormulaConstructor::operator()
type operator()(const std::string &name)
Create output type from a string identifier: let's quote it.
Definition: FormulaParser.h:220
Belle2::FormulaParser::addVariable
void addVariable(const InputToken &var) override
Add the variable to the output token stack, create it from a string or keep it as it is.
Definition: FormulaParser.h:196
Belle2::StringFormulaConstructor::Op
FormulaParserBase::EOperator Op
Shorthand for the operator enum.
Definition: FormulaParser.h:217
Belle2::FormulaParserBase::raiseError
void raiseError(const std::runtime_error &e)
Format the given runtime_error with context information and rethrow a new one.
Definition: FormulaParser.cc:305
Belle2::FormulaParserBase::EOperator
EOperator
List of known operators.
Definition: FormulaParser.h:41
Belle2::FormulaParserBase::EOperator::c_roundBracketOpen
@ c_roundBracketOpen
Open round bracket.
Belle2::FormulaParserBase::assertOperatorUsable
static void assertOperatorUsable(size_t stacksize)
Make sure we have enough operands to use an operator.
Definition: FormulaParser.cc:112
Belle2::FormulaParserBase::ENumberStatus::c_Int
@ c_Int
[leading sign] + digits
Belle2::FormulaParser
FormulaParser to parse a text formula like "a + b * c ^ d" where the separate parts can be either var...
Definition: FormulaParser.h:144
Belle2::FormulaParserBase::EOperator::c_minus
@ c_minus
Subtraction.
Belle2::FormulaParserBase::operatorToChar
static char operatorToChar(EOperator op) noexcept
Convert operator code to character.
Definition: FormulaParser.cc:29
Belle2::FormulaParserBase::executeOperator
virtual void executeOperator(EOperator op)=0
Execute an operator on the current state.
Belle2::FormulaParserBase::EOperator::c_squareBracketClose
@ c_squareBracketClose
Close square bracket.