| Contacto | Chat | Foro |__
  
 
Principal Hoja de Vida Universidad Artículos Programas Descargas
 

Evaluador de expresiones matemáticas


PROG00013 - C/C++
Implementación de un evaluador de expresiones matemáticas. Admite sólo operadores aritméticos y de potenciación. El funcionamiento está basado en dos pasos; el primero consiste en convertir la expresión a notación polaca inversa para luego proceder a la evaluación de esta última. Muestra la utilización de la clase para manejo de pilas.

Teoría de operación


El funcionamiento de la rutina consiste en dos fases: Conversión de formato infijo a postfijo (notación polaca inversa) y Evaluación de la expresión postfija.

La primera fase está basada en el siguiente algoritmo:

    1. Insertar un paréntesis izquierdo '(' en la pila.
    2. Agregar un paréntesis derecho ')' al final de la expresión infija.
    3. En tanto la pila no esté vacía, leer la expresión infija de izquierda a derecha y hacer los
        siguiente:
          • Si el carácter actual en la expresión infija es un dígito, copiarlo en el siguiente elemento
           de la expresión postfija.
          • Si el carácter actual en la expresión infija es un paréntesis izquierdo, insertarlo en la pila.
          • Si el carácter actual en la expresión infija es un operador
               - Retirar los operadores de la parte superior de la pila, en tanto tengan precedencia
                 igual o mayor que el operador actual, e insertarlos en la expresión postfija.
               - Insertar el carácter actual de la expresión infija en la pila.
          • Si el carácter actual en la expresión infija es un paréntesis derecho
               - Retirar los operadores de la parte superior de la pila e insertarlos en la expresión
                 postfija hasta que en la parte superior de la pila quede un paréntesis izquierdo.
               - Retirar y descartar el paréntesis izquierdo de la pila

La segunda fase, de evaluación de la expresión postfija consiste en lo siguiente:

     1. Agregar un carácter nulo al final de la expresión postfija.
     2. En tanto no se encuentre el carácter nulo, leer la expresión de izquierda a derecha
          • Si el carácter actual es un dígito, insertar su valor en la pila
          • De lo contrario, si el carácter es un operador, retirar los dos elementos superiores de la
             pila y calcular el operador; luego insertar el resultado en la pila.

A estos algoritmos básicos se le han añadido modificaciones para manejo de números reales y consideración del operador unario '-'.

STACK<int> S;

int isNumeral (int c)
{
   return (isdigit(c)||(c=='.'));
}

int isOperator (int c)
{
   switch (c)
   {
      case '+': case '-': case '*': case '/': case '~': case '^':
         return (1);

      default:
         return (0);
   }
}

int GoEP (int op1,int op2)
{
   int r;

   switch (op1)
   {
      case '*': case '/': case '%': case '~': case '^':
         r= 1;
         break;

      case '+': case '-':
         switch (op2)
         {
            case '*': case '/': case '%': case '~': case '^':
               r= 0;
               break;

            case '+': case '-':
               r= 1;
               break;
         }
   }

   return(r);
}

void convertToPostFix (char *InFix,char *PostFix)
{
   int IFc,PFc,oFlg= 1;

   S.Push('(');
   strcat(InFix,")");

   for (IFc=PFc=0;!S.IsEmpty();)
   {
      if (isNumeral(InFix[IFc]))
      {
         PostFix[PFc++]= InFix[IFc++];
         oFlg= 0;
      }
      else
      {
         if (InFix[IFc]=='(')
         {
            S.Push('(');
            IFc++;
         }
         else
            if (isOperator(InFix[IFc]))
            {
               if ((oFlg)&&(InFix[IFc]=='-'))
               {
                  PostFix[PFc++]= '0';
                  PostFix[PFc++]= ' ';
                  S.Push('~');
                  IFc++;
               }
               else
               {
                  PostFix[PFc++]= ' ';
                  while ((isOperator(S.Top()))&& (GoEP(S.Top(),InFix[IFc])))
                  {
                     PostFix[PFc++]= S.Pop();
                     PostFix[PFc++]= ' ';
                  }
                  S.Push(InFix[IFc++]);
                  oFlg= 1;
               }
            }
            else
               if (InFix[IFc]==')')
               {
                  while (S.Top()!='(')
                  {
                     PostFix[PFc++]= ' ';
                     PostFix[PFc++]= S.Pop();
                  }
                  S.Pop();
                  IFc++;
               }
               else IFc++;
      }
   }
    PostFix[PFc]= '\0';
}

STACK <double> R;

double doOperation (double op1,double op2, int op)
{
   double R;

   switch (op)
   {
      case '+':
         R= op1+op2;
         break;
      case '-': case '~':
         R= op1-op2;
         break;
      case '*':
         R= op1*op2;
         break;
      case '/':
         R= op1/op2;
         break;
      case '^':
         R= pow(op1,op2);
         break;
   }
   return (R);
}

doubleEvaluate (char* InFix)
{
   char PostFix[255];
   char *Tmp; char *E;

   convertToPostFix(InFix,PostFix);
   Tmp= strtok(PostFix," ");

   while (Tmp[0]!='\0')
   {
      if (isNumeral(Tmp[0]))
         R.Push(strtod(Tmp,&E));
      else
         if (isOperator(Tmp[0]))
            R.Push(doOperation(R.Pop(),R.Pop(),Tmp[0]));
      Tmp= strtok(NULL," ");
   }
   return(R.Pop());
}


Advertencia
Aunque no he escatimado esfuerzos en cuanto a proveer aplicaciones e información confiable y veraz, sin embargo no puedo garantizar que esté totalmente libre de errores; por esa razón, no asumo responsabilidad alguna por las consecuencias que se deriven de su empleo.




7-Zip

Descarga Adobre Reader

Descargar programa
  Copyright 2005 | Ramón Medina | Todos los derechos reservados | Última Actualización: Agosto del 2008 |webmaster@ramonmedina.name