Evaluación de expresiones aritméticas en notación polaca inversa (RPN)

Detalles

Categoría: Programación

Publicado el Jueves, 19 Mayo 2011 20:02

Las expresiones aritméticas que utilizamos habitualmente en la actualidad se basan en una serie de operadores (la suma '+', la resta '-', y algunos otros que habitualmente colocamos entre dos operandos. Por ejemplo, si queremos sumar 3 y 7, lo expresamos como 3+7. Es lo que llamamos notación infija.

Cuando combinamos varias operaciones de éste tipo en una expresión, nos surgen algunas peculiaridades de ésta notación. Por ejemplo, si queremos sumar 3 al resultado multiplicar 7 por 2 (denotaremos la multiplicación con el signo '*'), lo podemos escribir como 3+7*2, pero debemos establecer unas prioridades en las operaciones. Primero se hacen las multiplicaciones y divisiones de izquierda a derecha, y luego las sumas, de tal manera que primero deberíamos evaluar 7*2=14, y finalmente 2+14=16. Por convención, mantenemos siempre este orden.

Sin embargo, si quisiéramos sumar 3+7, y el resultado multilicarlo por 2, nos vemos obligados a introducir paréntesis: (3+7)*2.

Bueno... no supone un gran problema. Conocemos varias técnicas que nos permiten evaluar una expresión de éste estilo, aun con las prioridades y los paréntesis.

No obstante, existe una alternativa bastante curiosa. Hay una forma de escribir expresiones con el operador al final. Es decir, primero se escriben los operandos, y finalmente el operador, de tal manera que sumar 3 y 7 se expresa 3 7 +.

Análogamente, 3+7*2 se expresa 3 7 2 * +, y (3+7)*2 se expresa 3 7 + 2 *. Es la llamada notación polaca Inversa (abreviado RPN -Reverse Polish Notation-).

Ésta forma de escribir las operaciones se utilizó en algunas calculadoras electrónicas, incluyendo la famosa Hewlett Packard 35, de los años 70, considerada la primera calculadora científica de bolsillo.Tiene dos características curiosas: no necesita precedencias de operadores ni paréntesis, y para evaluar expresiones sólo necesitaremos una estructura de tipo LIFO (una pila) junto con un sencillo algoritmo.

Así que en este artículo nos dedicaremos a construir un algoritmo para evaluar este tipo de expresiones.

El nombre

HP-35

La calculadora HP 35, considerada la primera calculadora científica de bolsillo, utilizaba RPN.
[imagen de wikipedia]

En los años 50-60 se recupera la idea, pero con los operadores detrás de los operandos, y por extensión, como en RPN se colocan los operadores detrás, se le llamó notación polaca inversa. Tuvo un cierto auge en los 60 debido a que es cuando realmente empieza a establecerse la algoritmia computacional como disciplina. La RPN ofrecía un algoritmo sencillo para evaluar expresiones complejas.

Hewlett-Packard la utilizó para varios modelos de sus calculadoras científicas en los años 60 y 70, y todavía hoy algunos modelos la utilizan también.

Comprendiendo la notación

Jan Łukasiewicz

Cada uno de estos operadores es binario. Es decir, cada uno de ellos necesita dos operandos. Para sumar dos números cualesquiera, en la notación infija  colocamos el operador entre los operandos. En notación postfija se coloca detrás. Además, separamos operandos y operadores con espacios. Esa idea es simple.

• Ej: 2+4 lo expresamos 2 4 +.

Ahora bien, el caso es que cada uno de los operandos puede ser, a su vez, el resultado de otra operación, que también se expresa en RPN.

• Ej: 2+(3*5) es una suma de dos operandos: el 2 y (3*5) → 2 3 5 * + Fijémonos en la expresión. El primer operador que encontramos es *. Esa es la operación a realizar en primer lugar, y sus operandos son los dos valores inmediatamente anteriores. El resultado de 3 5 * es  15 , así que, resolviendo la expresión, ese trozo lo podemos sustituir por su valor 15, quedando como 2 15 +, es decir, 17.

Asi, podemos construir expresiones más complejas, prescindiendo de paréntesis y prioridades.

• Ej:  14*(7+4+11/5)-9 → 14 7 4 + 11 5 / + * 9 -

Extendiendo la notación

Nosotros vamos a construir una pequeña calculadora que resuelva expresiones en RPN. Además de los cuatro operadores aritméticos podemos incluir las operaciones numéricas que consideremos oportuno... el límite son las ganas que tengas de ampliar el algortimo.

Por ejemplo, si deseasemos implementar en nuestra calculadora una operación potencia representada como un operador con el símbolo ^, de tal manera que 3⁷ lo escribieramos en RPN como 3 7 ^, pues sería relativamente sencillo de implementar.

Lo mismo ocurre con funciones trigonométricas (como seno, coseno, tangente), raíces... o cualquier otra cosa. Sólo hay que tener un concepto claro: la aridad de la operación.

La aridad es el número de operandos que necesita una operación. Por ejemplo, la suma es una operación de aridad 2 (por eso decimos que la suma es un operador bin-ario).
Una función trigonométrica, como el coseno tiene una aridad 1, porque se aplica sobre un solo valor (por eso decimos que es una operación un-aria).

Podemos incluso considerar una operación que no tome argumentos, pero que aun así devuelva un valor (serian de aridad 0, o 0-arias), y podríamos utilizarlas para devolver constantes interesantes, como pi.

Es decir, la calculadora es nuestra, así que a nosotros nos toca decidir qué operaciones implementará y cuál sera el operador que utilicemos (teniendo clara la aridad de la operación), que no necesariamente tiene por qué ser un símbolo. Por ejemplo, podemos decidir que la palabra cos representa a la operación unaria de obtener un coseno, y la palabra pi representa a una operación 0-aria que devuelve el valor de pi.

De este modo, una expresión como cos(2*π³)+5 la expresaríamos para nuestra calculadora RPN como 2 pi 3 ^ * cos 5 +. Se acostumbra uno en seguida.

El algoritmo

Evaluar una expresión RPN es sencillo comparado con las expresiones en notación infija. Separaremos tanto operadores como operandos con espacios. Con esto se simplifica la obtención de los distintos elementos que componen la expresión.

Cada uno de estos elementos debe ser, o bien un número, o bien un operador.

[div class="alert" class2="typo-icon"]Operaciones no conmutativas

Ojo: algunas operaciones no son conmutativas... es decir, alterar el orden de los operandos altera el resultado. Por ejemplo, la suma es conmutativa 2 3 + da como resultado lo mismo que 3 2 +. Sin embargo, la resta o la división no lo son.

En RPN se conserva el orden de los operandos. Eso significa que 10 5 / es 10 dividido entre 5, y no 5 dividido entre 10. En el algoritmo, si intentamos evaluar esta última expresión, al encontrar el 10 se mete en la pila. Al encontrar el 5 también. Al encontrar el operador / sacaremos un operando de la pila (y saldrá el 5, porque la pila es una estructura LIFO -el último que entró es el primero que sale-) luego sacaremos el otro operando de la pila (y saldrá el 10). Debemos dividir el segundo que salió (el 10, que es el primero que entró) entre el primero que salió (el 5, que en realidad es segundo que entró)
La pila "vuelve del revés el orden" de los operandos;-)[/div]

Manos a la obra (en C#)

Vamos a implementar toda la funcionad en una sola clase, que llamaremos RPN.

La implementación que vamos a utilizar no es la mejor del mundo, seguro... Pero vamos a intentar primar la claridad del código sobre obre otros criterios.

Debemos tomar algunas decisiones de diseño. Evaluar una expresión, no siempre conduce a un resultado. Podríamos encontrar errores en la evalución, y no obtener un resultado válido.

Es decir, para realizar el trabajo de evaluar una expresión RPN, tenemos:

• Datos de entrada:
  • Una expresión, que podemos aceptar con una cadena (string)
• Datos de salida
  • Un posible resultado numérico o...
  • Una indicación de error

Podíamos haber optado por utilizar excepciones para indicar las situaciones de error, pero en este caso, hemos optado por no hacerlo (no hay una buena razón para ello... probablemente es algo personal, siento un cierto hastío cada vez que me toca lidiar con excepciones, así que prácticamente las voy dejando para errores realmente excepcionales).

Aprovechando que C# tiene parámetros sólo de salida hemos decidido utilizarlos.

En nuestra clase, en la parte pública vamos a encontrar tres cosas:

• Un método público, que será el punto de entrada para evaluar una expresión, con ésta signatura: public TipoError Eval(String expresion, out decimal resultado), que acepta una expresión RPN como primer parámetro, y una variable de tipo decimal como segundo parámetro que conendrá el valor del resultado.
  Como retorno, se devuelve un valor del enumerado TipoError
• El enumerado TipoError tiene cuatro posibles valores: noError, faltaOperando, demasiadosOperandos, sintactico, que corresponden a los tres posibles errores que podemos encontrar, y otro valor más para indicar la ausencia de error. Es decir, después de invocar al método Eval, éste devolverá un valor del enumerado. El resultado será válido sólo si el retorno es noError.
  
• Es posible que nos interese saber, en el caso de que se produzca un error en la expresión, por dónde anda éste... así que hemos incluido una propiedad pública de sólo lectura public string SimboloError que nos dará el elemento que se estaba analizando cuando se encontró el error.

En la parte privada tenemos

• Una pila. Imprescindible (System.Collections.Generics.Stack), como variable de instancia. 
• Una variable de instancia de tipo TipoError llamada globalError, que contiene el último tipo de error encontrado. En cada evaluación se inicializa a noError, y se cambia su valor al encontrar errores.
• Una variable de instancia de tipo string  llamada globalErrorSymbol, que contendrá el elemento que generó el último error. Es la variable que contiene el valor de la propiedad SimboloError
• Un método private bool Operador(string tok). Lo llama Eval cuando encuentra un elemento que no es un número (se supone que será un operador). Si en efecto lo es, éste método opera (sacando sus operandos de la pila) y mete en la pila el resultado -y en ese caso, termina devolviendo true-. Si no se puede operar, se devuelve false. Éste método lo hemos programado para que sea fácilmente extensible, y que tú puedas añadir tus propios operadores de manera sencilla.
  

[div class="note" class2="typo-icon"]Estamos utilizando una pila con elementos de tipo decimal, en lugar de double. Es más adecuado para representar valores decimales, debido a su precisión fija. Además, double produce una irritante pérdida de precisión en SilverLight. Eso condiciona que todas las operaciones son con decimal. La clase Math trabaja con valores double, lo que nos obliga a realizar typecast.[/div]

El método principal, Eval tiene un comportamiento sencillo. En primer lugar, parte la expresión de entrada en distintos elementos (dado que están separados por espacios) utilizando el método split de la clase string. De esta manera, obtenemos un array de cadenas, con cada uno de los elementos en una posición.

Se inicia un bucle while que va recorriendo ese array.

• Si se encuentra un número (lo detectamos con el método TryParse de la clase decimal), lo mete en la pila
• Si se encuenta algo que no es un número, se supone que será un operador, así que se lo pasa al método Operar.
• El método Operar devolverá false si no se pudo operar, bien porque lo que se le pasó no es un operador (en cuyo caso tenemos un error sintáctico), o bien porque sí era un operador, pero no había suficientes parámetros en la pila, (en cuyo caso tenemos un error de falta de operandos). Si es así, el bucle while se detiene.

[div class="note" class2="typo-icon"]El método TryParse intenta obtener un valor decimal a partir de una cadena. Distintos paises tienen distintas formas de escribir los decimales. Por ejemplo, en España se suele utilizar la coma para separar los decimales (ej: 3,14), es una costumbre un tanto minoritaria, mientras que en otros paises se utiliza el punto (ej: 3.14). Nosotro hemos optado por forzar ésta última notación. C# utiliza el concepto de cultura con estas conversiones. Utilizamos la cultura neutra, es decir, la que usa el punto como separador de decimales por estar más extendida, al menos, en el ámbito de las calculadoras. [/div]

Una vez terminado el bucle, si no ha sido por errores, queda comprobar una última cosa: en la pila debe haber exáctamente un único valor. Si no es así, se han introducido demasiados operandos (o pocos operadores), lo cual, constituye también un error.

Eso es básicamente todo. Aquí tienes la clase RPN. En éste código sólo hemos puesto unos pocos operandos en el método Operador, para que tú puedas experimentar añadiendo los que consideres oportunos.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226

/*
 * Clase en C# para evaluar expresiones aritméticas en notación polaca inversa.
 * 
 * Puedes usar, modificar y distribuir libremente éste código, teniendo en cuenta
 * que se distribuye "tal cual", sin garantía ni responsabilidad de ningún tipo.
 * Si te resulta util, se agradece un link a "http://latecladeescape.com".
 * 
 * Éste código se acoge los términos de la licencia descrita a continuación en inglés
 * y su utilización de cualquier tipo supone la aceptación de dichos términos.
 * 
 * **************************************************************************
 * Copyright © 2011 by La tecla de ESCAPE <latecladeescape.com>.
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *   notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 * notice, this list of conditions and the following disclaimer in the
 *  documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 * ****************************************************************************
 * @version 1.0
 * 
 */
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
 
namespace ConsoleRPN
{
 
    /// <summary>
    /// Clase para evaluar expresiones en notación polaca inversa (RPN)
    /// </summary>
    class RPN
    {
        /// <summary>
        /// Enumeración que representa a los tres tipos de error y a la ausencia de errores
        /// </summary>
        public enum TipoError
        {
            noError, faltaOperando, demasiadosOperandos, sintactico
        }
 
        //Contiene el último error producido en una evaluación
        private TipoError globalError;
 
        //Contiene el último token que se evaluaba cuando se detectó un error
        private string globalErrorSymbol;
        
        /// <summary>
        /// Propiedad para poder consultar el token en el que se produjo el
        /// último error desde el exterior de la clase. Sólo lectura
        /// </summary>
        public string SimboloError
        {
            get
            {
                return globalErrorSymbol;
            }
        }
 
        //la pila. Utilizamos el tipo decimal porque es de precisión decimal fija,
        //y porque se comporta mejor que double en SilverLight
        private Stack<decimal> pila = new Stack<decimal>();
 
        /// <summary>
        /// Intenta realizar la operación que se le pase como parámetro, utilizando
        /// como operandos los valores numéricos de la pila.
        /// Modifica la pila y la varible globalError si se encontró un error.
        /// </summary>
        /// <param name="tok">El operador</param>
        /// <returns>true si se pudo operar con éxito. false si se produjo un error, y en ese caso,
        /// se indica en la variable globalError</returns>
        private bool Operador(string tok)
        {
            bool retorno=true;
            decimal resultado=1;
            decimal dAux; //auxiliar
            try 
            {
                switch(tok.ToLower())
                {
                    case "+":   resultado=pila.Pop()+pila.Pop(); //suma. binario
                                break;
                    case "-":   resultado=-pila.Pop()+pila.Pop(); //resta. binario
                                break;
                    case "*":   resultado=pila.Pop()*pila.Pop(); //multiplicación, binario
                                break;
                    case "/":   //división. binario. Utilizamos una variable auxiliar para
                                //sacar los operandos en orden de la pila
                                dAux=pila.Pop();
                                resultado=pila.Pop()/dAux;
                                break;
                    case "mod":  //resto de la división entera. binario
                                dAux=pila.Pop();
                                resultado=pila.Pop()%dAux;
                                break;
                    case "^":   //potencia. binario.
                                dAux = pila.Pop();
                                resultado = (decimal)Math.Pow((double)dAux, (double)pila.Pop());
                                break;
                    case "pi":  // 0-ario: simplemente, introduce un valor en la pila
                                resultado=(decimal)Math.PI;
                                break;
                    case "sqrt": //raíz cuadrada. unario: utiliza un único operando
                                resultado = (decimal)Math.Sqrt((double)pila.Pop());
                                break;
                    case "sin": //seno. unario: utiliza un único operando
                                resultado = (decimal)Math.Sin((double)pila.Pop());
                                break;
                    case "cos": //coseno. unario: utiliza un único operando
                                resultado = (decimal)Math.Cos((double)pila.Pop());
                                break;
                    //****************************************************
                    //*** Añade los operadores que consideres oportuno ***
                    //****************************************************                    default:
                                retorno=false;
                                break;
                }//switch
            } //try
            catch (InvalidOperationException )
            {
                globalError=TipoError.faltaOperando;
                retorno=false;
            }
            if (retorno) //Si se ha podido realizar la operación
            {
                pila.Push(resultado); //dejamos el resultado en la pila
            }
            return retorno;
        }
 
 
        /// <summary>
        /// Método para evaluar una expresión RPN
        /// </summary>
        /// <param name="expresion">Una cadena que contiene la expresión RPN</param>
        /// <param name="resultado">El resultado de la evaluación de la expresión.
        /// Sólo es válido si el retorno del metodo es TipoError.noError</param>
        /// <returns>Devuelve un valor del enumerado TipoError</returns>
        public TipoError Eval(string expresion, out decimal resultado)
        {
            //partimos la cadena por los expacios
            string[] tokens=expresion.Split(new char[]{' '},StringSplitOptions.RemoveEmptyEntries);
            pila.Clear(); //limpiar la pila
            int indice=0; //un índice para movernos por los elementos
            globalError = TipoError.noError; //Antes de evaluar no hay error
            globalErrorSymbol = null; //ni símbolo en el que se produce el error
 
            //recorremos los elementos, y paramos si se produce un error
            while(indice<tokens.Length && globalError==TipoError.noError)
            {
                decimal valor;
                //intentamos ver si el elemento es un valor decimal.
                //TryParse intenta obtener un valor decimal de una cadena. Si delvuelve
                //false es que no es un valor decimal.
                //Utilizamos una cultura neutra, para aceptar números con un "." como
                //separador decimal.
                if (decimal.TryParse(tokens[indice],
                       System.Globalization.NumberStyles.Number,
                       new System.Globalization.CultureInfo(""),
                       out valor))
                {
                    pila.Push(valor); //si es un valor decimal, va a la pila.
                }
                else //si no
                {
                    //supondremos que es un operador e intentamos evaluarlo.
                    bool esUnOperador=Operador(tokens[indice]);
                    if (!esUnOperador) //Si no se ha podido evaluar
                    {
                        if (globalError == TipoError.noError)
                        {
                            //entonces es un elemento no reconocido
                            globalError = TipoError.sintactico;
                        }
                    }
 
                }
 
                //finalmente, si no se han producido errores en la evaluación de 
                //éste elemento, pasamos al siguiente, haciendo avanzar el bucle while
                if (globalError == TipoError.noError)
                {
                    indice++;
                }
                else
                {
                    //si se han producido errores, tomamos nota del elemento en el que
                    //se ha producido el error
                    globalErrorSymbol = tokens[indice];
                }
            } //fin while
 
 
            //Una vez terminado el recorrido por los elementos de la expresión
            //queda comprobar que queda un solo valor en la pila.
            if (globalError==TipoError.noError && pila.Count != 1)
            {
                globalError = TipoError.demasiadosOperandos;
                globalErrorSymbol = "final de la expresión";
 
            }
            //el valor de la pila es el resultado de la evaluación
            resultado = pila.Pop();
            return globalError;
        }
 
    }
}

Minidemo

Puedes probar el código en acción con esta minidemo. Acepta los operadores aritméticos +, -, *, / y sqr para la raiz cuadrada (unario), mod para el resto de la división entera (binario), pi para el valor aproximado de pi (0-ario), las operaciones trigonométricas unarias sin y cos, y la potencia ^.

Curiosidades: el lenguaje de programación Forth

Si la notación polaca inversa te ha llamado la atención o ha despertado tu curiosidad, te recomiendo, si todavía no lo conoces, echar un vistazo al lenguaje de programación Forth. Se trata de un lenguaje fascinante, en el que toda su expresión se lleva a cabo sobre una pila. La notación polaca inversa desempeña un papel crucial en este lenguaje. Forth es prácticamente único en su especio y no se parece a nada.

Fue creado en los años 70 por Charles H. Moore y Elizabeth Rather, en principio para guiar a los grandes radiotelescopios, con un consumo mínimo de recursos. Aunque no es un lenguaje de uso mayoritario, 40 años después sigue causando cierta fascinación, y puede considerarse prácticamente un lenguaje "de culto".

Más:

• el lenguaje Forth en la wikipedia..
• Grupo de interés en el lenguaje Forth
• De Javier Gil Chica: Introducción a Forth, magnífico manual para aprender y Ejercicios de programación en Forth, desde sencillos a bastante peliagudos.

• Siguiente >