calculate_logo

Alberto Lorenzo Márquez¶

Ingeniero aeroespacial

Desarrollador de software (C++, Fortran, Python, Javascript)

Github: https://github.com/newlawrence

Twitter: @newlawrence

¿Era necesario otro párser más de expresiones matemáticas?¶

La respuesta...

No¶

Existen muchos, y muy buenos, pársers de expresiones matemáticas ahí fuera...

#	Library	Author	License	Numeric Type
00	ATMSP	Heinz van Saanen	GPL v3	double, MPFR
01	ExprTk	Arash Partow	MIT	double, float, MPFR
02	FParser	Juha Nieminen & Joel Yliluoma	LGPL	double
03	Lepton	Peter Eastman	MIT	double
04	MathExpr	Yann Ollivier	Copyright Notice 1997-2000	double
05	METL	Till Heinzel	Apache	double
06	MTParser	Mathieu Jacques	CPOL	double
07	muParser	Ingo Berg	MIT	double, float
08	muParserX	Ingo Berg	MIT	double, float
09	TinyExpr	Lewis Van Winkle	Zlib	double

Fuente: Math Parser Benchmark Project

Aunque se usan todos, más o menos, así:

double x, y;
te_variable vars[] = {{"x", &x}, {"y", &y}};
int err;

te_expr *expr = te_compile("sqrt(x^2+y^2)", vars, 2, &err);
if (expr) {
    x = 3; y = 4;
    const double h1 = te_eval(expr); /* Returns 5. */
    te_free(expr);
} else {
    printf("Parse error at %d\n", err);
}

Ejemplo de uso del párser TinyExpr.

¿En realidad hace falta toda esta maquinaria para definir una función?

template <typename T>
struct foo : public exprtk::ifunction<T> {
   foo() : exprtk::ifunction<T>(3) {}

   T operator()(const T& v1, const T& v2, const T& v3) {
      return T(1) + (v1 * v2) / T(v3);
   }
};

Ejemplo de uso del párser ExprTk.

¿No puede existir algo...

...así?

auto expr = parser.parse("sqrt(x^2+y^2)");
expr(3, 4);

parser.functions.insert({
    "f",
    [](double v1, double v2, double v3) { return 1 + (v1 * v2) / v3  }
});

¿Qué ofrece Calculate?¶

Sólo archivos de cabecera.

Genérica.

Símbolos definidos por el usuario.

Reglas del analizador léxico personalizables.

Interfaz no intrusiva.

C++ moderno (estándar C++14).

¿De qué elementos se compone Calculate?¶

Clase Parser.

Clase Lexer.

Subclases de Symbol: Constant, Function, Operator.

Clase Expression.

Uso básico de la biblioteca¶

In [2]:

#include "calculate.hpp"

Instanciar un parser¶

In [3]:

auto parser = calculate::Parser{};

Crear expresiones atendiendo a su notación¶

Calculate permite parsear expresiones escritas tanto en notación infija como posfija:

In [4]:

double result;

In [5]:

auto e1 = parser.from_infix("1+2*3");
result = e1;
result

Out[5]:

In [6]:

auto e2 = parser.from_postfix("1 2 3 * +");
result = e2;
result

Out[6]:

Crear expresiones con variables¶

Aquellos símbolos que no se encuentren cargados en un párser harán saltar una excepción:

In [8]:

try {
    parser.from_infix("x");
}
catch (const calculate::BaseError& error) {
    std::cout << error.what() << std::endl;
}

Undefined symbol: 'x'

Es posible especificar qué símbolos se han de tratar como variables al momento de construir un objeto expresión. Las expresiones se evalúan como si de funciones regulares se tratase.

In [9]:

auto e3 = parser.from_infix("x+y", "x", "y");
e3(1, 2)  // x == 1, y == 2

Out[9]:

In [10]:

auto e4 = parser.from_postfix("x y +", "x", "y");
e4(1, 2)  // x == 1, y == 2

Out[10]:

Los objetos de la clase Parser proveen además de un método adicional parse que va añadiendo a la lista de variables aquellos símbolos que no están previamente cargados según van apareciendo en la expresión:

In [11]:

auto e5 = parser.parse("a-b");

for (const auto& variable : e5.variables())
    std::cout << variable << " ";
std::cout << std::endl;

e5(1, 2)  // a == 1, b == 2

a b

Out[11]:

-1

La clase Parser¶

Posee un tipo objetivo Parser::Type (double por defecto).

Provee de los métodos para crear expresiones.

Permite generar las expresiones precalculando las ramas constantes de las mismas.

Dispone de unos contenedores para los distintos tipos de símbolos: constantes, operadores y funciones.

Optimizar una expresión¶

In [12]:

parser.parse("1+2+x").infix()

Out[12]:

"1+2+x"

Para generar expresiones precalculando aquellas ramas constantes se modifica el atributo optimize del objeto parser:

In [13]:

parser.optimize = true;
parser.parse("1+2+x").infix()

Out[13]:

"3+x"

¡Atención!¶

Calculate no dispone de capacidades CAS, sólo puede optimizar aquellas ramas para el árbol que ella misma genera. No es capaz de transformar dicho árbol a una forma canónica para llevar a cabo optimizaciones más evidentes desde el punto de vista matemático.

In [14]:

parser.parse("1+x+2").infix()

Out[14]:

"1+x+2"

Contenedores de símbolos¶

Los objetos de la clase Parser tienen contenedores específicos para:

In [16]:

{ parser.constants; }  // Constantes

In [17]:

{ parser.functions; }  // Funciones

In [18]:

{ parser.operators; }  // Operadores

Los contenedores proveen una interfaz equivalente a la de la clase unordered_map de la STL (con algunas licencias en cuanto a la implementación):

In [19]:

result = parser.constants["pi"];
result

Out[19]:

3.14159

In [20]:

for (const auto& operator_pair : parser.operators)
    std::cout << operator_pair.first << "   ";
std::cout << std::endl;

^   %   *   -   /   +

Por ejemplo, añadir una constante es tan sencillo como:

In [21]:

parser.constants.insert({"G", {6.674e-11}});   // Gravitación universal

Out[21]:

@0x7fbeae5e4a30

In [22]:

auto f_grav = parser.from_infix("G * m1 * m2 / r^2", "m1", "m2", "r");
f_grav(1, 5.972e24, 6371e3) // Gravedad terrestre en superficie

Out[22]:

9.81953

Las subclases de la clase Símbolo¶

Como ya se vio, las expresiones pueden estar formadas por tres tipos de símbolos diferentes (sin contar los paréntesis y la coma de separación propios de la notación posfija):

Constantes

Funciones

Operadores

Existe un cuarto tipo, las Variables, pero estas pertenecen al funcionamiento interno del párser y sólo existen para proporcionar la habilidad a las expresiones de funcionar como invocables. A efectos prácticos, funcionan como las constantes.

Constantes¶

Envuelven valores del tipo al que esté orientado el párser (double en el caso del parser por defecto).

In [23]:

calculate::Parser::Constant c{1};
double{c}

Out[23]:

Funciones¶

Son capaces de envolver cualquier tipo de invocable, siempre que todos sus argumentos (un número indefinido de ellos) y el resultado sean del tipo al que está orientado el párser:

In [24]:

double sum(double x, double y) { return x + y; }

In [25]:

calculate::Parser::Function f{sum};
f(2, 2)

Out[25]:

En el caso de funtores, estos han de tener su operador llamada declarado como constante (las funciones matemáticas no tienen efectos secundarios).

In [26]:

class Plus {
    double _x;

public:
    Plus(double x) : _x{x} {}
    double operator()(double x) const { return x + _x; }
};

In [27]:

f = Plus(2);
f(2)

Out[27]:

Dado que el número de argumentos del operador llamada de los objetos de la clase Function es indefinido, los errores en el número de ellos pasan al tiempo de ejecución:

In [28]:

try {
    f(2, 2);
}
catch (const calculate::BaseError& error) {
    std::cout << error.what() << std::endl;
}

Arguments mismatch: 1 needed argument vs 2 provided

Operadores¶

Al igual que las funciones, envuelven invocables, pero además poseen dos atributos adicionales:

Su precedencia (dada por un entero sin signo).

Su asociatividad (por la izquierda, por la derecha o ambas).

Por ejemplo, el operador + por defecto:

In [29]:

calculate::Parser::Operator plus = parser.operators["+"];

Tiene menor precedencia que el operador * por defecto:

In [30]:

bool{plus.precedence() < parser.operators["*"].precedence()}

Out[30]:

true

Y es asociativo por ambos lados:

$(1 + 2) + 3 == 1 + (2 + 3)$

In [31]:

bool{plus.associativity() == calculate::Parser::Associativity::FULL}

Out[31]:

true

El Analizador Léxico¶

La clase Lexer contiene el conjunto de reglas que se utilizan para separar y clasificar los elementos que conforman la expresión:

In [32]:

auto& lexer = parser.lexer();

for (const auto& t : lexer.tokenize_infix("1+sin(2*pi*x)"))
    std::cout << t.token << "   ";
std::cout << std::endl;

1   +   sin   (   2   *   pi   *   x   )

A su vez, el analizador léxico tiene definidas las funciones para convertir del tipo objetivo del párser a cadena:

In [33]:

lexer.to_string(1.234)

Out[33]:

"1.234"

Y viceversa:

In [34]:

lexer.to_value("1.234")

Out[34]:

1.234

Expresiones regulares¶

El analizador léxico se sirve de expresiones regulares para determinar qué debe ser tratado como un número, qué como el nombre de una constante o función, y qué como un operador:

In [35]:

lexer.number

Out[35]:

"^[+\-]?(?:(?:NaN|Inf)|(?:(?:\d+\.?\d*|\.\d+)(?:[eE][+\-]?\d+)?))$"

In [36]:

lexer.name

Out[36]:

"^[A-Za-z_]+[A-Za-z_\d]*$"

In [37]:

lexer.sign

Out[37]:

"^(?:[^A-Za-z\d.(),_\s]|(?:\.(?!\d)))+$"

Ejemplo interactivo.

Calculate permite crear parsers especificando otros conjuntos de expresiones regulares:

In [38]:

auto l1 = calculate::lexer_from_regexes<calculate::Parser::Type>(
    calculate::defaults::number<calculate::Parser::Type>,
    calculate::defaults::name,
    R"(^(?:[^A-Za-z\d.(),_\s]|(?:\.(?!\d)))$)"
);
auto p1 = calculate::Parser{l1};

En el ejemplo, se ha modificado la lógica que dictamina qué es un operador. El párser por defecto tiende a unir todos los símbolos no alfanuméricos que encuentra al estilo de Haskell, por lo que la siguiente prueba no sería posible saltando una excepción indicando que el operador *- no está definido:

In [39]:

p1.parse("2*-1").infix()

Out[39]:

"2*(-1)"

Símbolos propios de la notación posfija¶

La notación posfija requiere de dos elementos que modifiquen la prioridad de las operaciones (los paréntesis):

In [40]:

lexer.left

Out[40]:

"("

In [41]:

lexer.right

Out[41]:

")"

A su vez, también necesita de un símbolo adicional para separar los argumentos de las funciones (la coma):

In [42]:

lexer.separator

Out[42]:

","

Calculate permite modificar también todos estos elementos para adaptarlos a las necesidades del usuario:

In [43]:

auto l2 = calculate::Lexer<calculate::Parser::Type>{
    calculate::defaults::number<calculate::Parser::Type>,
    calculate::defaults::name,
    R"(^(?:[^A-Za-z\d.\[\];_\s]|(?:\.(?!\d)))+$)",
    "[", "]", ";"  // Símbolos deseados
};
auto p2 = calculate::Parser{l2};

En el ejemplo, se ha modificado la expresión regular que determina qué es un símbolo para que excluya a los nuevos símbolos de prioridad (ahora corchetes) y al nuevo separador (ahora el punto y coma):

In [44]:

p2.parse("pow[a;b]")(2, 3)

Out[44]:

Los objetos de la clase Expresión¶

Los objetos expresión son el producto último de la biblioteca Calculate. Son la representación del concepto matemático y exponen una serie de métodos que los hacen sentir como tal, más allá del hecho de ser funtores en en el sentido de C++.

In [45]:

auto expr1 = parser.parse("1+2*3-4/5");

¿Cuál es el nodo raíz de la anterior expresión?

In [46]:

expr1.token()

Out[46]:

"-"

La principal característica de las expresiones es que son, a su vez los nodos de su propio árbol.

In [47]:

expr1.branches()

Out[47]:

Las ramas de una expresión son objetos expresión:

In [48]:

expr1[0].infix()

Out[48]:

"1+2*3"

In [49]:

expr1[1].infix()

Out[49]:

"4/5"

Gracias a ello, es posible navegar por el propio árbol interno de la expresión:

In [51]:

void print_tree(const calculate::Parser::Expression& expr) {
    using NodeIterator = calculate::Parser::Expression::const_iterator;
    std::stack<std::pair<NodeIterator, NodeIterator>> nodes;
    std::string indent;

    nodes.push({expr.begin(), expr.end()});
    std::cout << expr.token() << std::endl;
    while (!nodes.empty()) {
        auto node = nodes.top().first, end = nodes.top().second;
        nodes.pop();
        if (node != end) {
            std::cout << indent << "\\_ " << node->token() << std::endl;
            nodes.push({node + 1, end});
            if (node->branches()) {
                nodes.push({node->begin(), node->end()});
                indent += "   ";
            }
        }
        else
            if (indent.length() > 3)
                indent.erase(indent.length() - 3);
            else
                indent = "";
    }
}

Así, de la expresión:

In [52]:

expr1.infix()

Out[52]:

"1+2*3-4/5"

He aquí el árbol:

In [53]:

print_tree(expr1)

-
\_ +
   \_ 1
   \_ *
      \_ 2
      \_ 3
\_ /
   \_ 4
   \_ 5

Las variables de las subexpresiones (y, por lo tanto, el número de argumentos) también se adaptan según se navega por el árbol.

In [54]:

auto expr2 = parser.parse("x+y");
expr2.variables()

Out[54]:

{ "x", "y" }

Si bien, es necesario realizar copias de las subexpresiones ya que la generación de nuevas variables para las subexpresiones es cara y no se realiza cuando simplemente se piden las referencias:

In [55]:

auto expr3 = expr2[0];
expr3.variables()

Out[55]:

{ "x" }

In [56]:

auto expr4 = expr2[1];
expr4.variables()

Out[56]:

{ "y" }

Extendiendo Calculate¶

Calculate no es sólo una biblioteca orientada al parseo de expresiones matemáticas al uso; también aporta la capacidad de crear pársers personalizados basados en las notaciones infija y posfija y el algortimo de Shunting Yard para convertir de la una en la otra.

Parser de números complejos¶

Calculate provee por defecto de un párser de expresiones cuyo tipo de dato objetivo son los números complejos cuyo funcionamiento es idéntico al, hasta ahora, expuesto párser orientado a números reales.

In [57]:

auto complex_parser = calculate::ComplexParser{};

// Identidad de Euler
std::real(complex_parser.parse("exp(-1i * pi) + 1")())

Out[57]:

Creación de un párser de números enteros¶

Calculate no dispone por defecto de un párser de números enteros, pero crear uno es muy sencillo. Sólo hay que heredar de la clase plantilla BaseParser y proveer en el constructor todas aquellas constantes, funciones y operadores que se desee vengan precargados.

In [58]:

namespace calculate {
class IntegerParser : public BaseParser<int> {
public:
    IntegerParser() : BaseParser<Type>{lexer_from_defaults<Type>()} {
        using namespace defaults;
        operators.insert({
            {"+", {add<Type>, Precedence::low, Associativity::FULL}},
            {"-", {sub<Type>, Precedence::low, Associativity::LEFT}},
            {"*", {mul<Type>, Precedence::normal, Associativity::FULL}},
            {"/", {div<Type>, Precedence::normal, Associativity::LEFT}},
        });
    }
};
}

In [59]:

auto integer_parser = calculate::IntegerParser{};
int{integer_parser.parse("1 + 2 * 3")}

Out[59]:

¡Atención!¶

El procedimiento para crear pársers cuyo tipo de dato objetivo no sea numérico requiere de implementar a su vez un analizador léxico para dicho tipo dato.

Prueba de concepto de la creación de un párser cuyo tipo de dato objetivo son cadenas.

¡Eso es todo!¶

The most dangerous phrase in the language is "we've always done it this way." - Rear admiral Grace Murray Hopper