Evaluación de expresiones aritméticas usando recursividad

Las expresiones aritméticas pueden ser evaluadas de por lo menos dos formas: haciendo uso de un stack o haciendo uso de  invocaciones recursivas. En esta sección se presentará al forma recursiva para evaluar expresiones artiméticas  simples. Los operadores a considerar son: la suma (+), la resta (-) y la multiplicación. Además se considerarán los paréntesis como mecanismos de agrupación. Se debe respetar obviamente la asociativiada de estos operandos y su precedencia.

La idea es poder evaluar expresiones como (4+3)*5+8-5*2=

La técnica de evaluación recursiva parte de la observación que las expresiones aritméticas bien definidas deben satisfacer ciertas reglas gramaticales. Estas reglas se pueden definir como:

1.- Una evaluación es una expresión seguida de un signo igual (=, aunque pudo usarse otro símbolo).
2.- Una expresión está compuesta por una expresión seguida del operador + o - seguida de un término. Una expresión también puede ser sólo un término (cuando no hay sumas o restas )
3.- Un término se puede descomponer en un término seguido de un operador * seguido de un factor, o alternativamente un término puede ser sólo un factor.
4.- Finalmente un factor puede ser una expresión entre paréntesis o un número.

Las reglas de construcción indicadas del 1 al 4 definen qué es una expresión artimética bien construida en base a estos operadores.

Podemos expresar esta idea como: (entendiendo --> como "se compone de")
Valor -->  E=
E     -->  E+T
E     -->  E-T
E     -->  T
T     -->  T*F
T     -->  F
F     -->  (E)
F     --> número

Eliminación de la recursión por la izquierda

Estas reglas de producción de expresiones aritméticas no son convenientes para implementar un evaluador directamente porque, como usted podrá notar pronto, conducen a una recursión infinita. debido a que hay cosas del tipo E --> E operador T (se le llama recursión por la izquierda).
Afortunadamente existe un prodecimiento que permite eliminar tal tipo de recursión y generar un conjunto de reglas de producción que sí conducen a una estructura directamente programable que nos permitirá la evaluación.

En este caso el procedimiento de eliminación de la recursión por la izquierda.conduce a:

Valor  --> E=
E  --> T E'
E' --> +TE'
E' --> -TE'
E' -->          /* vacío, es decir puede ser reemplazado por un espacio o saltado sin problema.*/
T --> FT'
T' --> *FT'
T' -->
F --> (E)
F --> número
Mecanismo de evaluación recursivo

Una vez hecho el paso indicado anteriormente, es fácil efectuar la evaluación definiendo los siguientes métodos:

class Processor
{
public:
  Processor(string s): str(s), pos(0){};
  int eval();
private:
  Processor(){};
  int E();
  int T();
  int Ep(int t);
  int Tp(int f);
  int F();
  string str;
  int pos;
};

La evaluación de expresiones entreras está implementada aquí.