Esta solución consta de 5 métodos que para mayor comodidad se pusieron todos en la misma clase, aunque perfectamente se puede hacer otra modelación de clases para dar solución al problema planteado.
Además, se usa la estructura de datos Pila (Stack), la cual es fundamental para la resolución del problema planteado.
Una Pila en pocas palabras es como una lista enlazada a la que se le pueden añadir y retirar elementos únicamente de su parte superior. Por esta razón se dice que una Pila es una estructura de datos LIFO (last in, first out / último en entrar, primero en salir). Es decir el último elemento en entrar será el primero en salir. La Pila por supuesto tiene muchísimas aplicaciones y una de ellas es la que trato en este post.
En este post primero se convierte la expresión infija a postfija y posteriormente se hace el cálculo de la expresión ya convertida en notación postfija.
Una expresión en notación infija bien pudiera ser: (6 + 2) * 5 - 8 / 4, como ven puede estar compuesta por paréntesis izquierdo y derecho, números(que se les llama también operandos) y operadores que serían los símbolos de suma, resta, multiplicación y división.
A continuación la descripción del algoritmo para convertir de notación infija a postfija:
1) Inserte (push) un paréntesis izquierdo '(' en la parte superior de la Pila.
2) Agregue un paréntesis derecho ')' al final de infix.
3) En tanto la Pila no esté vacía, lea infix de izquierda a derecha y haga lo siguiente:
3.1) Si el caracter actual en infix es un dígito, cópielo al siguiente elemento de postfix.
3.2) Si el caracter actual en infix es un paréntesis izquierdo, insértelo (push) sobre la Pila.
3.3) Si el caracter actual en infix es un operador,
3.3.1) Retire (Pop) los operadores (si es que hay alguno) en la parte superior de la Pila en tanto tengan precedencia igual o mayor que el operador actual, e inserte los operadores retirados en postfix.
3.3.2) Inserte (Push) el caracter actual en infix sobre la Pila.
3.4) Si el caracter actual en infix es un paréntesis derecho:
3.4.1) Retire (Pop) los operadores de la parte superior de la Pila e insértelos en postfix hasta que en la parte superior de la Pila quede un paréntesis izquierdo.
3.4.2) Retire (Pop) y descarte el paréntesis izquierdo de la Pila.
Atendiendo a la descripción del algoritmo expuesto arriba adjunto el siguiente código:
using System;
using System.Collections.Generic;
using System.Linq;
namespace EvaluadorExpresionesAritmeticas
{
static class EvaluadorExpresiones
{
static private Stack<string> pila = new Stack<string>();
static private List<string> operadores = new List<string> {"*", "/", "+", "-"};
static private int CalcularOperacion(int x, int y, string operador)
{
int resultado = 0;
switch (operador)
{
case "+":
{
resultado = x + y;
break;
}
case "-":
{
resultado = x - y;
break;
}
case "*":
{
resultado = x * y;
break;
}
case "/":
{
resultado = x / y;
break;
}
default:
break;
}
return resultado;
}
static private List<string> StringToList(string expresion)
{
var listaExpresion = new List<string>();
int indiceListaExpresion = 0;
listaExpresion.Add(expresion[0].ToString());
for (int i = 1; i < expresion.Length; i++)
{
var valor = expresion[i];
if (char.IsDigit(valor) && operadores.Concat(new string[2] { "(", ")" }).Contains(listaExpresion.ElementAt(indiceListaExpresion)))
{
listaExpresion.Add(valor.ToString());
indiceListaExpresion++;
}
else if (operadores.Concat(new string[2] { "(", ")" }).Contains(valor.ToString()))
{
listaExpresion.Add(valor.ToString());
indiceListaExpresion++;
}
else
{
var numero = listaExpresion.ElementAt(indiceListaExpresion) + valor;
listaExpresion.RemoveAt(indiceListaExpresion);
listaExpresion.Add(numero);
}
}
return listaExpresion;
}
static private int PrecedenciaOperador(string operador)
{
int precedencia = 0;
if (operador == "*" || operador == "/")
{
precedencia = 1;
}
else if (operador == "+" || operador == "-")
{
precedencia = 2;
}
return precedencia;
}
static public string InFijaToPostFija(string expresionInfija)
{
string expresionPostFija = "";
int numero = 0;
expresionInfija = expresionInfija.Replace(" ", "");
var listaExpresionInfija = StringToList(expresionInfija);
pila.Push("(");
listaExpresionInfija.Add(")");
foreach (var x in listaExpresionInfija)
{
if (Int32.TryParse(x, out numero))
{
expresionPostFija += x + " ";
}
else if (x == "(")
{
pila.Push(x.ToString());
}
else if (operadores.Contains(x.ToString()))
{
var operadorPila = pila.Peek();
int precedenciaOperadorPila = PrecedenciaOperador(operadorPila);
int precedenciaOperadorExpresion = PrecedenciaOperador(x.ToString());
while (precedenciaOperadorPila <= precedenciaOperadorExpresion && operadores.Contains(operadorPila))
{
expresionPostFija += pila.Pop() + " ";
operadorPila = pila.Peek();
precedenciaOperadorPila = PrecedenciaOperador(operadorPila);
}
pila.Push(x.ToString());
}
else if (x == ")")
{
while (pila.Peek() != "(")
{
expresionPostFija += pila.Pop() + " ";
}
pila.Pop();
}
}
return expresionPostFija;
}
static public int EvaluarExpresionPostFija(string expresionInfija, out string expresionPostfija)
{
expresionPostfija = InFijaToPostFija(expresionInfija);
int op1, op2 = 0;
var listaPostFija = expresionPostfija.Split(' ').Where(s => !string.IsNullOrWhiteSpace(s)).ToList();
int numero = 0;
foreach (var x in listaPostFija)
{
if (Int32.TryParse(x, out numero))
{
pila.Push(x);
}
else if (operadores.Contains(x))
{
op1 = Convert.ToInt32(pila.Pop());
op2 = Convert.ToInt32(pila.Pop());
pila.Push(CalcularOperacion(op2, op1, x).ToString());
}
}
return Convert.ToInt32(pila.Pop());
}
}
}
Vamos por parte:
Se declara la clase estática EvaluadorExpresiones, esta clase tendrá dos campos privados, uno que será la Pila (Stack) como tal y otro será una lista con los operadores aritméticos (solo trato los operadores aritméticos de suma, resta, multiplicación y división, aunque perfectamente pueden incluirse otros, tales como el resto de la división, la potenciación, etc.).
El método InFijaToPostFija, es el responsable de convertir la expresión infija en postfija, este método implementa los pasos antes descritos en la descripción del algoritmo, a continuación su descripción:
El método recibe un parámetro de tipo string que sería la expresión infija y devuelve otro string que sería ya la expresión convertida a postfija, una vez dentro del método se declaran las siguientes variables:
expresionPostFija: es de tipo string y en ella se va guardando la expresión postifija obtenida, la cual es la que retorna el método.
numero: es de tipo entero y se utiliza para guardar los números que se vayan encontrando en la expresión (una expresión puede tener elementos tales como números, paréntesis izquierdo y derecho y los operadores de suma, resta, división y multiplicación).
Posteriormente se quitan los espacios de la variable expresionInfija, la cual fue pasada como parámetro al método, y la cadena de texto contenida en esa variable se transforma a una lista de string a través de la funcion StringToList, es decir se separa en tokens la cadena de textos y cada elemento de esa cadena sería un elemento en la lista de string.
Ya posteriormente vendría como tal la implementación del algoritmo, es decir se inserta un paréntesis izquierdo a la Pila y se inserta un paréntesis derecho a la lista antes obtenida.
Después mediante un ciclo foreach recorreríamos la lista y por cada elemento haremos lo siguiente:
Si es un número, concatenamos dicho número a la variable expresionPostFija para ir armando poco a poco lo que se nos pide.
Si es un paréntesis izquierdo lo insertamos en la Pila.
Si es un operador obtenemos su precedencia mediante la función PrecedenciaOperador, por ejemplo la multiplicación y la división tienen mayor precedencia que la suma y la resta, por lo que las operaciones de multiplicación y división se realizarán primero que las operaciones de suma y resta. Otra ventaja que tiene usar la notación postfija es que se descarta el uso de paréntesis, es decir si la expresión infija posee paréntesis no importa, ya que la expresión postfija
los elimina y sigue respetando la precedencia de los operadores, la notación postfija aunque elimina los paréntesis le va dando un orden a la expresión donde se va a ejecutar primero las operaciones que estarían dentro de los paréntesis en notación infija, luego se calcula la multiplicación y la división en el orden que aparezcan y por último la suma y la resta en el orden que aparezcan.
En este paso se ejecutarían las acciones descritas en el paso 3.3 del algoritmo anteriormente descrito.
Si es un paréntesis derecho se ejecutarán las acciones descritas en el paso 3.4.
Cuando se sale del ciclo foreach ya tendremos la expresión postfija guardada en la variable expresionPostFija, este valor es el que retornará la función.
Ej. si la expresión infija era (6 + 2) * 5 - 8 / 4, ahora esa expresión en notación postfija será: 6 2 + 5 * 8 4 / -.
Ahora que ya tenemos la expresión postfija correspondería hacer el cálculo de dicha expresión, para ello seguimos los pasos del siguiente algoritmo:
1) Recorrer la notación postfija de izquierda a derecha y por cada elemento preguntar:
1.1) Si el caracter actual es un número:
1.1.1) Inserte (push) su valor entero en la Pila.
1.2) De lo contrario, si el caracter actual es un operador:
1.2.1) Retire (pop) los dos elementos superiores de la Pila a las variables x e y. Calcule y operador x.
1.2.2) Inserte (push) el resultado del cálculo en la Pila.
2) Se devuelve el resultado final del cálculo realizado.
El método encargado de realizar el cálculo de una expresión postfija es EvaluarExpresionPostFija, el cual devuelve un entero, que sería el resultado del cálculo realizado y recibe como parámetros dos variables de tipo string, el primer parámetro es de entrada y representa la expresión infija que será convertida a notación postfija. El segundo parámetro es un parámetro de salida(a los parámetros de salida se les pone la palabra reservada out antes del tipo de datos) y este parámetro es el que va a devolver la expresión postfija obtenida.
Dentro del método se hace lo siguiente:
Se llama a la función InFijaToPostFija descrita anteriormente y se guarda el valor devuelto en el parámetro de salida expresionPostfija.
Se declaran dos variables enteras op1 y op2, que guardarán los números que se vayan encontrando en la Pila para realizar determinada operación aritmética.
Se declara la variable listaPostFija la cual guarda la conversión de texto a lista del texto obtenido en la variable expresionPostfija, para ello se usa la función Split para separar la cadena por espacios, y descarta los caracteres vacíos, de esta forma cada elemento de esta lista será un caracter de la variable expresionPostfija.
Se declara la variable numero la cual guardará los números que se vayan encontrando al recorrer la lista listaPostFija.
Posteriormente se ejecuta un ciclo foreach que recorrerá todos los elementos que están guardados en la lista listaPostFija y para cada elemento de la lista se pregunta:
Si es un número se inserte dicha número en la Pila.
Si es un operador se extraen de la Pila los dos primeros elementos, los cuales son números y se guardan dichos números en las variables op1 y op2. Se llama a la función CalcularOperacion la cual recibe tres parámetros, los dos operandos(op1 y op2) y el operador, en dicha función se hace el cálculo correspondiente de los operandos atendiendo al operador, es decir si el operador es suma, se suman los operandos, de ser multiplicación se multiplican los operandos y así con el resto de las operaciones aritméticas. Por último este cálculo obtenido se inserta en la Pila.
Después de salir del ciclo foreach se extrae el último elemento de la Pila, siendo este el resultado final de todo el cálculo realizado en la expresión postfija.
Para resumir el proceso supongamos que entramos la expresión en notación infija:
(6 + 2) * 5 - 8 / 4. Primero esta expresión se convierte a notación postfija, que seria:
6 2 + 5 * 8 4 / -. Posteriormente se hace el cálculo correspondiente usando la notación postfija, cuyo resultado seria: 38
Para usar la clase antes descrita haríamos lo siguiente:
string postfija = "";
string infija = "(6 + 2) * 5 - 8 / 4";
int resultado = EvaluadorExpresiones.EvaluarExpresionPostFija(infija, out postfija);
//Imprimir la expresión ya convertida a notación postfija.
//Imprimir resultado del cálculo
Declaramos la variable infija de tipo string, la cual guardará la expresión en notación infija, esta variable será pasada como parámetro al método EvaluarExpresionPostFija, para ser convertida a notación postfija.
Declaramos una variable de tipo string llamada postfija, la cual será pasada como parámetro de salida, al método EvaluarExpresionPostFija, en esta variable se retornará la expresión ya convertida a notación postfija.
Y se declara la variable resultado de tipo int que guardará el cálculo de la expresión previamente evaluada.
Como ven el uso de la estructura de datos Pila (Stack) es fundamental tanto para convertir de notación infija a postfija, como para realizar el cálculo aritmético de la expresión en notación postfija.
Nota importante: En este post se asume que la expresión evaluada en notación infija esta correctamente escrita, es decir de escribir una expresión incorrecta como:
))(6 ++ 2) * )5 - 8 / 4, el algoritmo no funcionará, ya que eso lleva otro tipo de validación, que no es la tratada en este post.