Notación Polaca Inversa






Es un método algebraico alternativo de introducción de datos. Su nombre viene por analogía con la relacionada notación polaca, una notación de prefijo introducida en 1920 por el matemático polaco Jan Lukasiewicz, en donde cada operador está antes de sus operandos. 



LA NOTACION



En la notación polaca inversa es al revés, primero están los operandos y después viene el operador que va a realizar los cálculos sobre ellos. Tanto la notación polaca como la notación polaca inversa no necesitan usar paréntesis para indicar el orden de las operaciones mientras la aridad del operador sea fija.

NPI              nuestra notación (expresión algebraica)
3 4 +    =>       3 + 4
  7                     7

Ventajas

  • Los cálculos se realizan secuencialmente según se van introduciendo operadores, en vez de tener que esperar a escribir la expresión al completo. Debido a esto, se cometen menos errores al procesar cálculos complejos.
  • El proceso de apilación permite guardar resultados intermedios para un uso posterior. Esta característica permite que las calculadoras RPN computen expresiones de complejidad muy superior a la que alcanzan las calculadoras algebraicas.
  • No requiere paréntesis ni reglas de preferencia, al contrario que la notación algebraica, ya que el proceso de apilamiento permite calcular la expresión por etapas.
  • En las calculadoras RPN, el cálculo se realiza sin tener que apretar la tecla "=" (aunque se requiere pulsar la tecla "Enter" para añadir cifras a la pila).
  • El estado interno de la calculadora siempre consiste en una pila de cifras sobre las que se puede operar. Dado que no se pueden introducir operadores en la pila, la notación polaca inversa es conceptualmente más sencilla y menos dada a errores que otras notaciones.

[editar]Desventajas

  • La adopción casi universal de la notación algebraica en los sistemas educativos hace que no haya muchas razones prácticas inmediatas para que los alumnos aprendan la notación polaca inversa. No obstante, muchos estudiantes afirman que, una vez aprendida, la notación polaca inversa simplifica en gran manera el cálculo de expresiones complejas.
  • Es difícil usar la notación polaca inversa al escribir a mano, dada la importancia de los espacios para separar operandos. Se requiere un caligrafía muy clara para evitar confundir, por ejemplo, 12 34+ (=46) de 123 4+ (=127) o 1 234+ (=235).
  • Las calculadoras RPN son relativamente raras. Forzado a usar una calculadora algebraica, el usuario de una calculadora RPN típicamente comete errores más frecuentemente debido a sus hábitos de uso normales. No obstante, esto no es un problema tan grave en la actualidad, debido a que muchos sistemas operativos pueden emular calculadoras RPN.

Ejemplo del algoritmo

Tenemos la expresion algebraica de 3+((2+4)*5)-1 y en la notacion polaca inversa es 3 2 4 + 5 * + 1 - evaluandose de izquierda a derecha

Entrada         Operación           Pila                Comentario

3                   introducir pila      3

2                   introducir pila      3,2

4                   introducir pila      3,2,4

+                   sumar                3,6                    tomar dos ultimos valores de pila (2,4) y poner resultado

5                   introducir pila      3,6,5           

*                    multiplicar          3,30                  tomar dos ultimos valores(6,5) y poner su resultado

+                   sumar                 33                   tomar dos ultimos valores (3,30) y poner resultado

1                    introducir pila     33,1                  

-                     resta                 32                     tomar los dos ultimos valores(33,1)y poner resultado


Al final el resultado (32) aparece como unico elemento de la pila

Aqui esta la implementacion del algoritmo de ingresando numero de 0 a 9 pero podria optimizarse

#include <cstdlib>
#include <iostream>
#include <string.h>

using namespace std;

int validar(char c)
{
    if(c>=48 && c<=57)
    return 1;
    else
    {
        if(c>=65 && c<=90)
        return 2;
        else
        {
            if(c>=97 && c<=122)
            return 3;
            else
            return 4;
        }
    }
}

typedef struct nodo
{float dato;
 struct nodo*sgt;
 struct nodo*ant;
}tnodo;

typedef struct pila
{struct nodo*p1;
 struct nodo*p2;
 int n;
}tpila;

tpila*crearpila()
{tpila*p=(tpila*)malloc(sizeof(struct pila));
 p->p1=NULL;
 p->p2=NULL;
 p->n=0;
 return p;
}

void push(float dato,tpila*pila)
{tnodo*nodo=NULL;
 nodo=(tnodo*)malloc(sizeof(struct nodo));
 nodo->dato=dato;
 nodo->ant=NULL;
 nodo->sgt=NULL;
 if(pila->p1==NULL)
 {pila->p1=nodo;
  pila->p2=nodo;
 }
 else
 {pila->p2->sgt=nodo;
  nodo->ant=pila->p2;
  pila->p2=nodo;
 }
 pila->n++;
}

void pop(tpila*pila)
{tnodo*ultimo=NULL;
 ultimo=pila->p2;
 if(pila->p1!=NULL)
 {pila->p2=pila->p2->ant;
  if(pila->p2==NULL)
   pila->p1=NULL;
  else
   pila->p2->sgt=NULL;
  free(ultimo);
  pila->n--;
 }
}

float cima(tpila*pila)
{float dato=0;
 dato=pila->p2->dato;
 return dato;
}

bool esvacia(tpila*pila)
{bool respuesta=false;
 if(pila->p1==NULL)
 respuesta=true;
 return respuesta;
}

int main()
{
    //pila
    tpila*pila=NULL;
    pila=crearpila();
    //push(8,pila);

    char *c=(char*)malloc(sizeof(char));
    cin>>c;
    int nc=strlen(c);
    float result=0,b;
    int stado=0,caso;
    int sfinal=3;
    bool error=false;
    int i=0;
    while(!error && stado!=3)
    {

        if(validar(c[i])==1 && stado==0)
        {
            push(c[i]-48,pila);
            i++;
        }
        else
        {
            if(validar(c[i])==4 && stado==0 && !esvacia(pila) && !error)
            {


                if(c[i]=='+')
                    caso=1;
                else
                {
                    if(c[i]=='-')
                        caso=2;
                    else
                    {
                        if(c[i]=='*')
                            caso=3;
                        else
                        {
                            if(c[i]=='/')
                                caso=4;
                            else
                                error=true;
                        }
                    }
                }

                if(!error)
                {
                    b=cima(pila);
                    pop(pila);
                    stado=1;

                    switch(caso)
                    {
                        case 1:
                                if(!esvacia(pila))
                                {
                                    result=cima(pila)+b;
                                    pop(pila);
                                    push(result,pila);
                                    stado=2;
                                }
                                else
                                error=true;
                                break;

                        case 2:
                                if(!esvacia(pila))
                                {
                                    result=cima(pila)-b;
                                    pop(pila);
                                    push(result,pila);
                                    stado=2;
                                }
                                else
                                error=true;
                                break;

                        case 3:
                                if(!esvacia(pila))
                                {
                                    result=cima(pila)*b;
                                    pop(pila);
                                    push(result,pila);
                                    stado=2;
                                }
                                else
                                error=true;
                                break;

                        case 4:
                                if(!esvacia(pila))
                                {
                                    result=cima(pila)/b;
                                    pop(pila);
                                    push(result,pila);
                                    stado=2;
                                }
                                else
                                error=true;
                                break;

                        default: cout<<"error de sistema :p";
                    }
                }
                i++;
            }
            else
            {
                if(i<nc && stado==2 && !esvacia(pila) && !error)
                stado=0;
                else
                {
                    if(stado==2 && !esvacia(pila)&& !error)
                    {
                        result=cima(pila);
                        pop(pila);
                        stado=3;
                        if(!esvacia(pila))
                        error=true;
                    }
                    else
                        error=true;
                }
            }
        }
    }
    if(!error)
    cout<<result;
    else
    cout<<"ecuacion invalida";
    system("PAUSE");
    return EXIT_SUCCESS;

}



// Fuente wikipedia
Siguiente
« Post Anterior