I wrote a parser to solve math expressions like "3.0 ^(4 - 5)", or "3 / 8".
It's bad luck to name an interface after its implementation. This file could
have been "expressionSolver.h". But naturally, if I set out to implement
recursive descent parsing, that tainted my filename selection.
Below my sig is recursiveDescentParser.h, a math expression solver. Using
the test framework, and test suite appearing in RecursiveDescentParserTest and RecursiveDescentParserCpp, and
TestDrivenDevelopment?, I produced this little parser. Extending it to use
variables, or your favorite math notation, should be relatively easy.
The primary interface is parse("1 + 3"). This returns a type that can
contain either a double or a beef, which is an error message string.
The code is 'inline' due to laziness; no speed gain is implied.
--PhlIp
#ifndef RECURSIVE_DESCENT_PARSER_H_
# define RECURSIVE_DESCENT_PARSER_H_
# include <ctype.h>
# include <stdexcept>
# include <string>
# include <assert.h>
# include <math.h>
namespace parser {
using std::string;
class
Fallible_double_t
{
// contains either a double or a beef
double m_value;
public:
const string m_beef;
Fallible_double_t(string beef): m_value(0.0), m_beef(beef) {}
Fallible_double_t(double value): m_value(value) {}
bool getValid() { return m_beef.size() == 0; }
operator double()
{
assert(getValid());
return m_value;
}
}; // named after Barton & Nackman's Fallible type
inline void
eatBlanks(char const * &z)
{
while (isspace(*z))
++z;
}
inline Fallible_double_t
parseTerminal(char const * &z)
{
eatBlanks(z);
char * end = NULL;
double result = strtod(z, &end);
if (z == end)
return Fallible_double_t("syntax error");
z = end;
eatBlanks(z);
return result;
}
inline Fallible_double_t parseTerms(char const * &z);
# define bounce_(x_) if (!x_.getValid()) return x_;
inline Fallible_double_t
parseParentheses(char const * &z)
{
eatBlanks(z);
if (*z == '(')
{
++z;
Fallible_double_t contents = parseTerms(z);
bounce_(contents);
if (*z != ')')
return Fallible_double_t("");
++z;
eatBlanks(z);
return contents;
}
return parseTerminal(z);
}
inline Fallible_double_t
parseExponentiation(char const * &z)
{
Fallible_double_t arg_ = parseParentheses(z);
bounce_(arg_);
double arg (arg_);
while (*z == '^')
{
char op (*z++);
Fallible_double_t factor = parseParentheses(z);
bounce_(factor);
return pow(arg, factor);
}
return arg;
}
inline Fallible_double_t
parseFactors(char const * &z)
{
Fallible_double_t arg_ = parseExponentiation(z);
bounce_(arg_);
double arg (arg_);
while (*z == '*' || *z == '/')
{
char op (*z++);
Fallible_double_t factor = parseExponentiation(z);
bounce_(factor);
switch(op)
{
case '*': arg *= factor; break;
case '/':
if (factor == 0.0)
return Fallible_double_t("division by zero error");
arg /= factor;
break;
}
}
return arg;
}
inline Fallible_double_t
parseTerms(char const * &z)
{
Fallible_double_t arg_ = parseFactors(z);
bounce_(arg_);
double arg (arg_);
while (*z == '+' || *z == '-')
{
char op (*z);
Fallible_double_t factor = parseFactors(++z);
bounce_(factor);
switch(op)
{
case '+': arg += factor; break;
case '-': arg -= factor; break;
}
}
return arg;
}
inline Fallible_double_t
parse(char const * input)
{
char const * end = input;
Fallible_double_t got = parseTerms(end);
if (got.getValid() && input + strlen(input) != end)
return Fallible_double_t("incomplete expression"); // oh, you were
so close!
return got;
}
} // namespace parser
#endif // ndef RECURSIVE_DESCENT_PARSER_H_