Evaluador de expresiones con pilas y variables
Una calculadora que entiende expresiones con paréntesis, prioridad de operadores, menos unario y variables: convierte cada expresión a notación postfija con el algoritmo de la estación de maniobras, la evalúa con una pila y detecta cada error. Pilas, mapas, excepciones propias y análisis de texto.
- ArrayDeque como pila
- TreeMap
- Excepciones propias
- Análisis léxico
- Notación postfija
- Math.addExact
Enunciado
Las calculadoras, las hojas de cálculo y los compiladores tienen que entender expresiones como 3 + 4 * (2 - 1), donde la multiplicación va antes que la suma y los paréntesis cambian el orden. Hacerlo leyendo de izquierda a derecha no funciona: hay que reorganizar la expresión.
La solución clásica, del informático Edsger Dijkstra, es el algoritmo de la estación de maniobras (shunting-yard): pasa la expresión a notación postfija, en la que los operadores van detrás de sus operandos (3 4 2 1 - * +) y ya no hacen falta paréntesis ni prioridades. Evaluar la postfija es muy sencillo con una pila: cada número se apila y cada operador desapila dos, opera y apila el resultado.
Tu calculadora trabajará con números enteros (long), recordará variables y explicará cada error en lugar de fallar: es la parte de un intérprete que se ocupa de las expresiones.
Qué tiene que hacer el programa
- Cada línea no vacía es una expresión, una asignación
nombre = expresióno la ordenVARIABLES. Los nombres de variable empiezan por letra o_y siguen con letras, cifras o_; distinguen mayúsculas. - Las expresiones usan enteros sin signo, variables, paréntesis,
+,-,*,/(división entera, como en Java) y%(resto, como en Java), con los espacios que se quiera.*,/y%tienen más prioridad que+y-, y operadores de la misma prioridad se aplican de izquierda a derecha. Un-al principio, tras(o tras otro operador es un menos unario, que tiene la mayor prioridad. - Para una expresión correcta escribe
línea → postfija → resultado: la línea tal como se ha leído (sin espacios al principio ni al final), la postfija con sus elementos separados por un espacio (el menos unario se escribe~) y el valor. En una asignación el resultado esnombre = valor, y la variable queda guardada. - Si hay un error al separar la expresión o al pasarla a postfija, escribe
línea → Error: mensaje; si el error aparece al evaluarla,línea → postfija → Error: mensaje(sin la postfija si está vacía). Los mensajes son:carácter no válido 'c',paréntesis sin abrir,paréntesis sin cerrar,expresión incompleta(falta un operando o un operador),división entre cero,variable desconocida nombre,número demasiado grande(no cabe en un long),número no válido texto(empieza por cifra pero tiene letras) ydesbordamiento(el resultado de una operación no cabe en un long). Una asignación con error no cambia la variable. VARIABLESescribeVariables: a = 1, b = 2con todas las variables por orden alfabético, oVariables: ninguna.
Entrada
Una expresión, asignación u orden VARIABLES por línea.
Ejemplos de ejecución
Tu programa debe escribir exactamente esta salida para estas entradas. Las pruebas del editor incluyen estos ejemplos y otros casos ocultos.
Prioridades, menos unario y variables
Entrada
3 + 4 * (2 - 1) (3 + 4) * 2 - 10 / 3 x = 2 * -5 y = x * x % 7 -(x + 3) * y VARIABLES
Salida por consola
3 + 4 * (2 - 1) → 3 4 2 1 - * + → 7 (3 + 4) * 2 - 10 / 3 → 3 4 + 2 * 10 3 / - → 11 x = 2 * -5 → 2 5 ~ * → x = -10 y = x * x % 7 → x x * 7 % → y = 2 -(x + 3) * y → x 3 + ~ y * → 14 Variables: x = -10, y = 2
Errores
Entrada
8 / (4 - 2 * 2) (1 + 2 1 + 2) 3 + 5 $ 2 z + 1 4 5
Salida por consola
8 / (4 - 2 * 2) → 8 4 2 2 * - / → Error: división entre cero (1 + 2 → Error: paréntesis sin cerrar 1 + 2) → Error: paréntesis sin abrir 3 + → 3 + → Error: expresión incompleta 5 $ 2 → Error: carácter no válido '#x27; z + 1 → z 1 + → Error: variable desconocida z 4 5 → 4 5 → Error: expresión incompleta
Guía paso a paso
Intenta resolverlo por tu cuenta y abre un paso solo cuando te atasques: cada uno te acerca a la solución sin dártela entera.
1. Separar en elementos (tokens)
Recorre la cadena carácter a carácter: los espacios se saltan, una racha de letras, cifras o _ es un número o una variable, y cada uno de +-*/%() es un elemento por sí solo. Cualquier otro carácter lanza tu excepción ErrorExpresion.
2. La estación de maniobras
Los números y variables van directos a la salida. Un ( se apila. Un ) desapila hacia la salida hasta encontrar su (. Un operador saca antes de la pila los que tienen más prioridad (o la misma, si es binario) y después se apila. Al final se vacía la pila: si aparece un (, faltaba un ).
while (!pila.isEmpty() && !pila.peek().equals("(")
&& prioridad(pila.peek()) >= prioridad(op)) {
salida.add(pila.pop());
}
pila.push(op);3. El menos unario
El - de -5 o 2 * -3 no resta: cambia el signo. Distínguelo por lo que tiene delante (nada, ( u otro operador) y conviértelo en otro operador, ~, con la mayor prioridad y asociativo por la derecha, para que --4 sea 4.
4. Evaluar la postfija
Con una ArrayDeque<Long> como pila: un número se apila; ~ desapila uno; un operador binario desapila b y luego a (¡en ese orden!) y apila a op b. Si falta algún operando, o al final no queda exactamente un valor, la expresión estaba incompleta.
5. Errores sin romper el programa
Define class ErrorExpresion extends Exception y lánzala con el mensaje adecuado. Math.addExact, subtractExact, multiplyExact y negateExact lanzan ArithmeticException si el resultado no cabe en un long, y Long.parseLong lanza NumberFormatException con números enormes: atrápalas y conviértelas en tu excepción.
Resuélvelo aquí
El editor trae el esqueleto del programa. Pulsa «Ejecutar» para comprobarlo con los ejemplos y con 2 casos ocultos que buscan los errores típicos.
Ejemplo
3 + 4 * (2 - 1) (3 + 4) * 2 - 10 / 3 x = 2 * -5 y = x * x % 7 -(x + 3) * y VARIABLES
3 + 4 * (2 - 1) → 3 4 2 1 - * + → 7 (3 + 4) * 2 - 10 / 3 → 3 4 + 2 * 10 3 / - → 11 x = 2 * -5 → 2 5 ~ * → x = -10 y = x * x % 7 → x x * 7 % → y = 2 -(x + 3) * y → x 3 + ~ y * → 14 Variables: x = -10, y = 2
Solución explicada
Ver la solución completa
1import java.util.ArrayDeque;
2import java.util.ArrayList;
3import java.util.Deque;
4import java.util.List;
5import java.util.Map;
6import java.util.Scanner;
7import java.util.TreeMap;
8
9public class Main {
10 /** Error de una expresión, con el mensaje que se muestra. */
11 static class ErrorExpresion extends Exception {
12 ErrorExpresion(String mensaje) { super(mensaje); }
13 }
14
15 // TreeMap: las variables salen siempre por orden alfabético
16 static final Map<String, Long> variables = new TreeMap<>();
17
18 static boolean esOperador(String t) {
19 return t.equals("+") || t.equals("-") || t.equals("*") || t.equals("/") || t.equals("%") || t.equals("~");
20 }
21
22 static int prioridad(String op) {
23 return switch (op) {
24 case "~" -> 3;
25 case "*", "/", "%" -> 2;
26 case "+", "-" -> 1;
27 default -> 0;
28 };
29 }
30
31 /** «x * (2 - 15)» → [x, *, (, 2, -, 15, )]. */
32 static List<String> separar(String texto) throws ErrorExpresion {
33 List<String> tokens = new ArrayList<>();
34 int i = 0;
35 while (i < texto.length()) {
36 char c = texto.charAt(i);
37 if (Character.isWhitespace(c)) {
38 i++;
39 } else if (Character.isDigit(c) || Character.isLetter(c) || c == '_') {
40 int j = i;
41 while (j < texto.length() && (Character.isLetterOrDigit(texto.charAt(j)) || texto.charAt(j) == '_')) j++;
42 tokens.add(texto.substring(i, j));
43 i = j;
44 } else if ("+-*/%()".indexOf(c) >= 0) {
45 tokens.add(String.valueOf(c));
46 i++;
47 } else {
48 throw new ErrorExpresion("carácter no válido '" + c + "'");
49 }
50 }
51 return tokens;
52 }
53
54 /** Algoritmo de la estación de maniobras (shunting-yard): notación infija → postfija. */
55 static List<String> aPostfija(List<String> tokens) throws ErrorExpresion {
56 List<String> salida = new ArrayList<>();
57 Deque<String> pila = new ArrayDeque<>();
58 String anterior = null;
59 for (String t : tokens) {
60 if (t.equals("(")) {
61 pila.push(t);
62 } else if (t.equals(")")) {
63 while (!pila.isEmpty() && !pila.peek().equals("(")) salida.add(pila.pop());
64 if (pila.isEmpty()) throw new ErrorExpresion("paréntesis sin abrir");
65 pila.pop();
66 } else if (esOperador(t)) {
67 // Un menos al principio, tras «(» o tras otro operador cambia el signo: es el operador unario ~
68 boolean unario = t.equals("-") && (anterior == null || anterior.equals("(") || esOperador(anterior));
69 String op = unario ? "~" : t;
70 // Los binarios son asociativos por la izquierda (sacan los de igual prioridad); ~ por la derecha
71 while (!pila.isEmpty() && !pila.peek().equals("(")
72 && (unario ? prioridad(pila.peek()) > prioridad(op) : prioridad(pila.peek()) >= prioridad(op))) {
73 salida.add(pila.pop());
74 }
75 pila.push(op);
76 t = op;
77 } else {
78 salida.add(t); // número o variable
79 }
80 anterior = t;
81 }
82 while (!pila.isEmpty()) {
83 String op = pila.pop();
84 if (op.equals("(")) throw new ErrorExpresion("paréntesis sin cerrar");
85 salida.add(op);
86 }
87 return salida;
88 }
89
90 static long evaluar(List<String> postfija) throws ErrorExpresion {
91 Deque<Long> pila = new ArrayDeque<>();
92 try {
93 for (String t : postfija) {
94 if (t.equals("~")) {
95 if (pila.isEmpty()) throw new ErrorExpresion("expresión incompleta");
96 pila.push(Math.negateExact(pila.pop()));
97 } else if (esOperador(t)) {
98 if (pila.size() < 2) throw new ErrorExpresion("expresión incompleta");
99 long b = pila.pop(), a = pila.pop();
100 if ((t.equals("/") || t.equals("%")) && b == 0) throw new ErrorExpresion("división entre cero");
101 pila.push(switch (t) {
102 case "+" -> Math.addExact(a, b);
103 case "-" -> Math.subtractExact(a, b);
104 case "*" -> Math.multiplyExact(a, b);
105 case "/" -> a / b;
106 default -> a % b;
107 });
108 } else if (Character.isDigit(t.charAt(0))) {
109 if (!t.matches("\\d+")) throw new ErrorExpresion("número no válido " + t);
110 pila.push(Long.parseLong(t));
111 } else {
112 Long valor = variables.get(t);
113 if (valor == null) throw new ErrorExpresion("variable desconocida " + t);
114 pila.push(valor);
115 }
116 }
117 } catch (NumberFormatException e) {
118 throw new ErrorExpresion("número demasiado grande");
119 } catch (ArithmeticException e) {
120 throw new ErrorExpresion("desbordamiento");
121 }
122 if (pila.size() != 1) throw new ErrorExpresion("expresión incompleta");
123 return pila.pop();
124 }
125
126 public static void main(String[] args) {
127 Scanner sc = new Scanner(System.in);
128 while (sc.hasNextLine()) {
129 String linea = sc.nextLine().trim();
130 if (linea.isEmpty()) continue;
131 if (linea.equalsIgnoreCase("VARIABLES")) {
132 List<String> lista = new ArrayList<>();
133 variables.forEach((nombre, valor) -> lista.add(nombre + " = " + valor));
134 System.out.println("Variables: " + (lista.isEmpty() ? "ninguna" : String.join(", ", lista)));
135 continue;
136 }
137 // «nombre = expresión» es una asignación
138 String nombre = null, expresion = linea;
139 if (linea.matches("[A-Za-z_]\\w*\\s*=.*")) {
140 int igual = linea.indexOf('=');
141 nombre = linea.substring(0, igual).trim();
142 expresion = linea.substring(igual + 1);
143 }
144 try {
145 List<String> postfija = aPostfija(separar(expresion));
146 String textoPostfija = String.join(" ", postfija);
147 try {
148 long valor = evaluar(postfija);
149 if (nombre != null) variables.put(nombre, valor);
150 System.out.println(linea + " → " + textoPostfija + " → " + (nombre != null ? nombre + " = " : "") + valor);
151 } catch (ErrorExpresion e) {
152 System.out.println(linea + " → " + (textoPostfija.isEmpty() ? "" : textoPostfija + " → ") + "Error: " + e.getMessage());
153 }
154 } catch (ErrorExpresion e) {
155 System.out.println(linea + " → Error: " + e.getMessage());
156 }
157 }
158 }
159}El programa sigue las fases de un intérprete real: análisis léxico (separar), análisis sintáctico (aPostfija) y evaluación (evaluar). Cada fase puede fallar con un mensaje propio, y por eso el main sabe si mostrar la postfija o no según en qué fase se produjo el error.
El algoritmo de la estación de maniobras usa la pila para «aparcar» operadores hasta saber si pueden salir: un operador solo sale cuando llega otro de menor o igual prioridad o un paréntesis de cierre. La diferencia entre >= y > es toda la diferencia entre asociatividad por la izquierda (20 - 5 - 3 = 12) y por la derecha (--4 = 4).
Evaluar la postfija con otra pila es lineal y no necesita prioridades: el orden ya está resuelto. Hay que desapilar el segundo operando antes que el primero, o 10 - 3 daría -7.
La excepción propia convierte todos los fallos (tokens raros, paréntesis, operandos que faltan, divisiones entre cero, desbordamientos) en un único tipo de error con mensaje. El TreeMap mantiene las variables ordenadas sin tener que ordenarlas al mostrarlas.
Para ir más allá
- Añade la potencia
^, asociativa por la derecha y con más prioridad que*. - Admite funciones como
max(a, b)yabs(x)en la estación de maniobras. - Cambia
longporBigIntegerpara que no haya desbordamientos, o porBigDecimalpara admitir decimales exactos.