Crear una calculadora 'Simple'

NOTA: Este artículo da por sentado que el lector tiene conocimientos acerca de Tipos de Datos Abstractos (ADT), específicamente hablando: Pilas.

1. Introducción:

Esta calculadora tendrá unas funciones básicas y simples. Hay que tener ciertos detalles en cuenta:

La expresión introducida es sintácticamente correcta.
No hay operadores unarios. Por ejemplo: (-3*5)
No hay ningún operador exponencial. Por ejemplo: 2^3 = 8
Los operandos son números de un solo dígito: de 0 a 9.

2. Algoritmo Básico de la Simulación de una Calculadora

He aquí el algoritmo básico (sin detalles) de la calculadora:

Transformar la expresión algebraica, que está en forma infija, a postfija.
Evaluar la expresión postfija para obtener el resultado de dicha expresión algebraica.

3. Expresiones Algebraicas: Prefija, Infija, y Postfija

Si el lector tiene conocimientos acerca de Expresiones Algebraicas en forma prefija, infija, y postfija, entonces puede saltarse esta sección y continuar con la sección 4. Algoritmo: Pasar de Infija a Postfija.

Las expresiones algebraicas que usamos en el mundo occidental son las llamadas infijas. Esto quiere decir que los operadores están colocados entre medias de dos operandos. Por ejemplo, "2+3". "2" y "3" son operandos y "+" es el operador, el cual está situado entre los operandos.

Las expresiones de forma prefija y postfija siguen la misma lógica que la infija, excepto que la prefija sitúa el operador antes (pre-) de los dos operandos y postfija, detrás (post). En el ejemplo anterior, "2+3", la expresión en forma prefija sería "+23", y en forma postfija, sería "23+".

Otro ejemplo más complejo:

Infija: 2*3+9/3 = 6+9/3 = 6+3 = 9

Prefija: +*23/93 = +6/93 = +63 = 9

Postfija: 23*93/+ = 693/+ = 63+ = 9

La forma de convertir de infija a prefija o postfija es relativamente simple:

Se dejan los números en la misma colocación: 2 * 3 + 9 / 3
Se "borran" los operadores: 2 3 9 3
Ahora se colocan los operadores a la derecha (prefija) o izquierda (postfija) de los operandos. Para prefija: + * 2 3 / 9 3, y para postfija: 2 3 * 9 3 / +

Las ventajas de tener una expresión algebraica en prefija o postfija en vez de infija son:

Evaluando una expresión en forma prefija se asemeja a programar en ensamblaje: <instrucción> <operando1> <operando2>
Evaluando una expresión en forma postfija es más fácil a la hora de implementar analizadores de lenguajes, calculadoras (como veremos pronto), etc..
Las formas prefijas o postfijas no contienen paréntesis, como los suele tener la forma infija. Ejemplo:
Infija: 2*(3+9)/3 = 2*12/3 = 24/3 = 8
Prefija: /*2+393 = / * 2 12 3 = / 24 3 = 8
Postfija: 239+*3/ = 2 12 * 3 / = 24 3 / = 8

La ventaja de la forma infija es que es más sencilla de dictar, ya que es más lógica (al menos para nosotros humanos) que las formas prefijas y postfijas. Estas dos últimas formas necesitan tener la expresión entera antes de poder evaluar, mientras que la infija suele ser evaluada a medida que se vaya obteniendo información. Hay quizá otra ventaja al usar la forma infija, los operadores separan una agrupación de dígitos de otra; así es más fácil de leer los números, que las formas prefijas y postfijas.

4. Algoritmo: Pasar de Infija a Postfija

Para pasar una expresión algebraica de forma infija a postfija haremos uso de una Pila y las operaciones pertenecientes.

Aquí muestro el pseudocódigo para lograrlo. P se refiere a la Pila, la cual contiene la expresión algebraica en forma infija. Prioridad dicta la precedencia del operador:

Inicializar la Expresión Postfija EP
For cada caracter C en la expresión infija
{
   Switch( C )
   {
      Case operando	:  Agregar( EP, C )
      Case '('		:  Empuja( P, C )
      Case ')'		:  // Sigue Sacando hasta que se encuentre el paréntesis abierto
      {
         while( MirarPila( P ) != '(' )
         {
            Agregar( EP, Saca( P ) )
         }
         Saca( P )	// Saca el paréntesis abierto
      }
      Case operador	:  // Guardar C hasta que pueda ser determinado dónde colocarlo
      {
         while( (!PilaEstaVacia( P )) && (MirarPila( P ) != '(') &&
           (Prioridad( MirarPila( P ) ) >= Prioridad( C )) )
         {
            Agregar( EP, Saca( P ) )
         }
         Empuja( P, C )
      }
   }
}
// Agregar a EP los operadores restantes en la Pila
while( !PilaEstaVacia( P ) )
{
   Agregar( EP, Saca( C ) )
}

5. Evaluación de una Expresión Algebraica en Forma Postfija

Una vez que obtengamos la expresión algebraica en forma postfija, podemos empezar a evaluarla. Aquí presento el pseudocódigo:

For cada caracter C en la expresión
{
   If C es un operador llamado Op
   {
      Operando2 = Saca( P )
      Operando1 = Saca( P )
      Resultado = Operando1 Op Operando2
      Empuja( P, Resultado )
   }
   else  Empuja( P, C )
}

6. Bibliografía

Frank M. Carrano, Paul Helman, Robert Veroff. Data Structures and Problem Solving with Turbo Pascal: Walls and Mirrors. Redwood City, California: The Benjamin/Cummings Publishing Company, Inc., 1993.