Trabajo Práctico 1

Fecha de entrega: Lunes 23 de junio

Introducción

Objetivo

El objetivo del presente trabajo práctico es implementar una calculadora que opere con sintaxis natural y precisión arbitraria.

El trabajo consiste en la resolución de un problema mediante el diseño y uso de TDAs y en la reutilización de algunos de los tipos, funciones y conceptos desarrollados a lo largo del curso en trabajos anteriores.

Alcances

Mediante el presente TP se busca que el estudiante adquiera y aplique conocimientos sobre los siguientes temas:

  • Encapsulamiento en TDAs,

  • Pilas y colas,

  • Tablas de búsqueda,

  • Punteros a funciones,

  • Modularización,

  • Técnicas de abstracción,

además de los temas ya evaluados en trabajos anteriores.

Nota

Este trabajo es un trabajo integrador de final de cursada. En el mismo se van a aplicar todos los temas aprendidos y además se va a evaluar el diseño de la aplicación.

Es imprescindible entender los temas de TDA y modularización antes de empezar con el trabajo.

Es imprescindible diseñar el trabajo como etapa previa a la implementación.

Cualquier abordaje que pretenda empezar a codificar sin haber ordenado el trabajo primero está condenado a fracasar contra la complejidad del problema.

Notaciones algebraicas

La notación algebraica con la que estamos familiarizados es la llamada notación infija. Por ejemplo sin ( max ( 2, 3 ) ÷ 3 × π ) (se explicitan los diferentes símbolos separándolos con un espacio).

Me da vergüenza ajena esto, pero una búsqueda en Google de "viral matemática" devuelve un montón de resultados, estos son los primeros:

Sí, viste bien, el último es de TyC Sports... y sí, viste bien, 8 × 3 + 12 ÷ 4 − 7 es un desafío matemático sólo apto para genios (si yo mirara TN me sentiría ofendido)...

Ahora bien, lo que está subyacente en todos estos "retos" virales (más allá de la epidemia de pelotudez en las redes sociales) es que la notación infija necesita un procesamiento adicional y además definir una prioridad para esas operaciones, la prioridad que definamos será la que determinará el resultado. (Y también la asociatividad, en menor medida, por ejemplo 3 ÷ 2 ÷ 5 dará 0,3 o 7,5 según qué operación resolvamos primero.) Y para alterar esas prioridades además necesitamos utilizar paréntesis.

Existe otra forma de notación que es la notación postfija, o polaca reversa, que antepone operandos a operadores, por ejemplo, mientras que en infija escribimos 3 + 2 en postfija escribimos 3 2 +, donde 3 2 + evalúa a 6 y puede ser utilizado en una cuenta posterior, por ejemplo 3 2 + 1 + da como resultado 7 y opera (3 + 2) + 1, con ese orden de precedencia y asociatividad. En la notación postfija el orden de las operaciones está totalmente definido sin usar paréntesis de ningún tipo.

El primer ejemplo que dimos de infija se representaría como 2 3 max 3 ÷ π × sin (asumiendo que la división tiene más precedencia que la multiplicación).

Notación postfija

Dijimos que la notación postfija resulta de interés por no requerir paréntesis ni precedencias, pero en realidad lo más importante de esta notación es que es muy sencillo construir una máquina que pueda operar sobre ella.

El algoritmo de evaluación de una expresión postfija es el siguiente:

  1. Se tiene una pila, la misma empieza siendo vacía

  2. Mientras queden símbolos, para cada símbolo:

    1. Si es un número se apila en la pila.

    2. Si es un operador, se sacan de la pila tantos operandos como la aridad del mismo, se realiza la operación y el resultado se apila en la pila.

  3. Terminada la iteración en la pila debería haber un solo elemento: El resultado.

En el ejemplo:

  1. Expresión: {2, 3, max, 3, ÷, π, ×, sin}, Pila: {}.

  2. Evaluamos el símbolo 2, es un número, lo ponemos en la pila. Expresión {3, max, 3, ÷, π, ×, sin}, Pila: {2}.

  3. Símbolo: 3, número. Expresión {max, 3, ÷, π, ×, sin}, Pila: {3, 2} (tope de la pila a izquierda).

  4. Símbolo max, es un operador, es binario, retiramos dos elementos de la pila b = 3, a = 2, operamos max(a, b), resultado 3, lo apilamos. Expresión {3, ÷, π, ×, sin}, Pila: {3}.

  5. Símbolo: 3, número. Expresión {÷, π, ×, sin}, Pila: {3, 3}.

  6. Símbolo ÷, binario, b = 3, a = 3, operamos a ÷ b evalúa a 1. Expresión {π, ×, sin}, Pila: {1}.

  7. Símbolo π, número. Expresión {×, sin}, Pila: {π, 1}.

  8. Símbolo ×, operador binario, b = π, a = 1, a × b evalúa a π. Expresión {sin}, Pila: {π}.

  9. Símbolo sin, operador unario, a = π, sin(π) evalúa a 0. Expresión {}, Pila: {0}.

  10. No quedan más símbolos, hay un solo elemento en la pila, el resultado es cero.

Si bien en este ejemplo nunca llegaron a haber más de dos números en la pila, una expresión como 2 × 3 + 4 × 5, que se expresa en postfija como 2 3 × 4 5 × + apila más elementos, y otras expresiones pueden apilar indefinidos elementos.

No se mencionó de forma explícita, pero notar que la pila será siempre de números. Y no se mencionó de forma explícita, pero ¿qué pasaría si tengo un operador n-ario y no hay n elementos en la pila?, claramente la expresión estaba mal formada. La cantidad de elementos en la pila tiene que estar compensada con los operadores y al final tiene que quedar sólo un elemento siempre.

No se mencionó de forma explícita tampoco, pero los símbolos de la expresión se consumen en el orden original en el que llegaron, sacando de a uno por vez del comienzo... es decir, la expresión se representa como una cola de símbolos.

Notación infija

Muy bonita la notación postfija (en realidad no), pero no podemos torturar a un usuario a ingresar las operaciones en ese formato (a menos que seamos HP comercializando las infames calculadoras HP 48 que eran un estándar para cualquier alumno que rindiera Análisis de Circuitos hace unos años). Un usuario quiere escribir en notación infija... pero la notación infija es difícil de computar (es un desafío matemático sólo apto para genios) a diferencia de la postfija. ¿Entonces qué hacemos?

Lo usual es programar nuestro motor de cómputo en forma postfija y realizar un preprocesamiento de la entrada del usuario para convertir de infija a postfija.

Presentamos el algoritmo de shunting yard (playa de maniobras) desarrollado por Edsger Dijktra.

El mismo tiene como entrada una cola de entrada donde viene la expresión infija, una cola de salida donde se genera la expresión postfija y una pila auxiliar.

Tenemos que tener definidos los operadores y además sus prioridades.

Para cada símbolo en la cola de entrada:

  1. Si es un número va a la salida.

  2. Si es un paréntesis que se abre va a la pila.

  3. Si es un paréntesis que se cierra mande a la salida todo lo que haya en la pila hasta encontrar un paréntesis que se abre (y descarte ambos paréntesis).

  4. Si es un operador:

    1. Mientras sobre la pila haya algún operador de mayor o igual precedencia: Desapilar y a la salida.

    2. Apilar el operador.

Y, finalmente, vaciar completa la pila en la cola de salida.

Por ejemplo, supongamos que tenemos la expresión A + B × C - D, donde las letras son números y tenemos dos niveles de prioridad: 1 para la suma y la resta y 2 para la multiplicación (es decir, la multiplicación tiene prioridad más alta que la suma y la resta, entonces se debe computar antes).

Entonces: Cola de entrada: {A, +, B, ×, C, -, D}, y la cola de salida y la pila estarán vacías al empezar.

  1. Sacamos A, es un número. Entrada: {+, B, ×, C, -, D}, Salida: {A}, Pila: {}.

  2. Sacamos + es un operador, no hay nada en la pila, así que pasamos al paso 4.b, lo apilamos. Entrada: {B, ×, C, -, D}, Salida: {A}, Pila: {+}.

  3. Sacamos B, número. Entrada: {×, C, -, D}, Salida: {A, B}, Pila: {+}.

  4. Sacamos ×, operador. El operador × tiene prioridad mayor al + que ya está en la pila, así que pasamos a 4.b. Entrada: {C, -, D}, Salida: {A, B}, Pila: {×, +}.

  5. Sacamos C, número. Entrada: {-, D}, Salida: {A, B, C}, Pila: {×, +}.

  6. Sacamos -, operador. Tenemos que sacar de la pila todos los operadores de precedencia igual o mayor y luego apilar: Entrada: {D}, Salida: {A, B, C, ×, +}, Pila: {-}.

  7. Sacamos D, número. Entrada: {}, Salida: {A, B, C, ×, +, D}, Pila: {-}.

  8. No quedan más símbolos, desapilamos todos los elementos y los encolamos a la salida. Salida: {A, B, C, ×, +, D, -}.

En el artículo de Wikipedia https://en.wikipedia.org/wiki/Shunting_yard_algorithm está completo el algoritmo para este ejemplo con dibujos gráficos. Además está completa la secuencia del algoritmo de shunting yard para el primer ejemplo de este enunciado.

Multiplicación de enteros largos

Cambiamos de tema, volviendo al EJ2, en dicha oportunidad no se implementó una función de multiplicación. En el EJ3 se proveyó una implementación que se aclaró que era mala. Cuando hablamos de mala hablamos de que si el entero \(x\) tiene \(n\) dígitos (de 32 bits cada uno) y el entero \(y\) tiene \(m\) dígitos, entonces en la implementación provista la operación \(x \times y\) anida una iteración por cada uno de los dígitos de un número para cada uno de los números del otro, es decir, tiene complejidad computacional \(\mathcal O(nm)\), es decir, asumiendo que los números sean de tamaño comparable, es una solución cuadrática.

Volviendo tanto al EJ2 como el EJ3 tanto la implementación de la división como la de la multiplicación dada hacen operaciones de desplazamiento de a 32 bits por vez, es decir, operaciones que NO deberían resolverse desplazando bits sino que son corrimientos dentro del vector de enteros.

En primer lugar, agregar al TDA entero_t primitivas para desplazar los dígitos del número en i unidades. Es decir, un desplazamiento de i * 32 en bits. Estas operaciones no requieren manejo de bits de ningún tipo.

Dicho esto, teniendo dos números de \(n\) dígitos cada uno, siempre podemos partir ese número en dos partes de esta forma:

\[x = x_1 B^m + x_0,\]
\[y = y_1 B^m + y_1.\]

En nuestro caso, la base \(B = 2^{32}\). La primera parte del número tendrá los dígitos entre [0, m) mientras que la segunda parte los dígitos entre [m, n). Obviamente \(m < n\).

Si operamos \(x \times y\) y agrupamos los términos vamos a obtener:

\[xy = z_2 B^{2m} + z_1 B^m + z_0,\]

con:

\[\begin{split}z_2 = x_1y_1, \\ z_1 = x_1y_0 + x_0y_1, \\ z_0 = x_0y_0.\end{split}\]

Hasta acá la cantidad de operaciones de producto que necesitamos resolver el producto son 4, por lo que no mejoramos nada al algoritmo que ya teníamos.

Ahora bien Anatoly Karatsuba observó que si computáramos:

\[z_3 = (x_1 + x_0) (y_1 + y_0),\]

podríamos reescribir

\[z_1 = z_3 - z_2 - z_0.\]

Es decir, pasamos de requerir 4 productos a requerir sólo 3. El resto de las operaciones son sumas y restas, que son mucho más económicas de operar.

Notar que tanto la operación de partir los números, como las operaciones de multiplicar por \(B^p\) son los desplazamientos que dijimos que se podían computar simplemente moviendo enteros dentro del vector de dígitos.

Volviendo a la operatoria general, habíamos dicho que los números que estábamos multiplicando tenían \(n\) dígitos, en ese caso tendría sentido elegir a \(m \approx n / 2\), es decir, partirlo al medio. De esta forma, las partes \(x0, x1, y0, y1\) tendrán más o menos la mitad de los dígitos. Entonces, ¿cómo hacemos las operaciones de \(z_3, z_2, z_1, z_0\)? ¿no es obvio? El algoritmo de la multiplicación de \(n\) dígitos requiere de multiplicación de \(n / 2\) dígitos lo cual se puede hacer recursivo mientras que \(n > 1\).

¿Y cuando \(n = 1\)?, ahí tenemos que multiplicar dos números de un dígito uint32_t cada uno de ellos, los cuales podemos operar en 64 bits sobre un uint64_t y recuperar el resultado.

Se puede demostrar que el algoritmo de Karatsuba aplicado de forma recursiva partiendo al medio los números tiene una complejidad computacional \(\mathcal O(n^{\log_2 3}) \approx \mathcal O(n^{1.58})\).

Trabajo

Se desarrollará una calculadora que le pida expresiones al usuario y las procese imprimiendo su resultado. Cada expresión será una línea y el usuario ingresará tantas expresiones como quiera hasta finalizar la entrada.

Las expresiones se ingresarán en su forma infija.

Internamente el programa utilizará números racionales basados en enteros largos para computar todas las operaciones, si bien el usuario usará notación de punto decimal para ingresarlas.

Se deben utilizar los siguientes TDAs:

  • racional_t, como fue desarrollado en el EJ3.

  • entero_t, como fue desarrollado en el EJ2, agregando las funciones de corrimiento de \(i*32\) bits y la multiplicación con el algoritmo de Karatsuba (y modificando la operación de división a la firma del EJ3).

  • pila_t, tal como es provista por la cátedra.

  • cola_t, tal como es provista por la cátedra.

Además de desarrollar los que se consideren necesarios.

Expresiones

Ampliaremos la definición de los símbolos dentro de las expresiones. La entrada del usuario es una sucesión de símbolos que son: números, funciones, operadores o paréntesis. Cada uno de estos símbolos puede estar separado por un espacio o no.

Números:

Los números son una secuencia consecutiva de dígitos (isdigit()), las cual puede contener opcionalmente un punto.

Funciones:

Las funciones son una secuencia de letras (isalpha()).

Paréntesis:

Abrir o cerrar un paréntesis: ( o ) (un único carácter).

Operadores:

Los operadores son de un único carácter, ninguno de los anteriores (no son números, letras ni paréntesis.

Se reitera, los símbolos pueden o no estar separados por espacios. Si los hubiera no formarán parte del símbolo. Un símbolo terminará donde empieza el siguiente.

Entonces, si por ejemplo el usuario ingresara la siguiente secuencia: "5+3* 2 + (2.25 - fact(3)) / fact42" en la misma estarían los siguientes símbolos: {5, +, 3, *, 2, +, (, 2.25, -, fact, (, 3, ), ), /, fact, 42}. Donde los símbolos {5, 3, 2, 2.25, 3, 42} son números, {+, *, -, /} son operadores, {(, )} son paréntesis y {fact} es una función.

Notar que una vez separada la expresión en símbolos, todos tienen al menos un carácter y la clase del primer carácter permite distinguir qué tipo de símbolo es.

Como parte de este trabajo se debe tener la capacidad de procesar una línea y extraer cada uno de los símbolos de la expresión y generar una cola con los mismos.

(Notar que no hay comas entre nuestros símbolos, por lo que nuestras funciones serán de un solo parámetro.)

Infijo a postfijo

Ya presentamos el algoritmo de shunting yard en la introducción, vamos a profundizar un poco dado que ahora conocemos nuestros símbolos y además vamos a explicitar las condiciones que no pueden darse.

La entrada del algoritmo de shunting yard es una cola de símbolos en notación infija y la salida del algoritmo es una cola de símbolos en notación postfija. Dado que la notación postfija no los requiere, la salida no tendrá paréntesis, sólo números, operadores y funciones.

El algoritmo utiliza una pila de símbolos como estructura auxiliar. En esa pila sólo habrá operadores, funciones y paréntesis que se abran.

El algoritmo entonce será, para cada símbolo de la cola de entrada:

  • Si es un número: Se encola en la salida.

  • Si es una función: Se apila.

  • Si es un operador:

    • Mientras en el tope de la pila no haya un paréntesis o un operador de menor precedencia (es decir en el tope hay o una función o un operador de mayor o igual precedencia):

      • Pasar de la pila a la cola.

    • Apilar el operador.

    La pila podría estar vacía o vaciarse durante el primer proceso.

  • Si es una apertura de paréntesis ((): Se apila.

  • Si es un cierre de paréntesis ()):

    • El símbolo se descarta.

    • Mientras en el tope de la pila no haya un paréntesis que se abra:

      • Pasar de la pila a la cola.

      Durante esta operación la pila no se puede vaciar. Si la pila se vaciara significa que los paréntesis están desbalanceados, es decir, se está cerrando un paréntesis que nunca se abrió.

    • Ahora sobre la pila hay un paréntesis que se abra: Se descarta.

    • Si en el tope de la pila hay una función: Se pasa de la pila a la cola.

Al terminar todos los símbolos de la entrada puede haber operadores y funciones remanentes en la pila:

  • Mientras queden elementos en la pila se pasan a la cola. En este proceso no puede haber ningún paréntesis en la pila, esto significaría que un paréntesis quedó sin ser cerrado.

Durante este proceso se debe validar que la entrada sea correcta. La entrada será correcta si existen los operadores y las funciones que forman parte de los símbolos y para ser correcta además deberá estar balanceada de paréntesis. Es decir, no puede vaciarse la pila al desapilar buscando el paréntesis de cierre y no puede haber paréntesis en la pila luego de vaciada la cola de entrada.

Cómputo del postfijo

Para el cómputo del postfijo la entrada es una cola de números, operadores y funciones, la computada por shunting yard. La operatoria se realiza sobre una pila. La salida del algoritmo será el único valor que tiene que tener la pila al finalizar el mismo.

La operatoria es la ya descripta. Para cada símbolo de la cola de entrada:

  • Si el símbolo es un número, se apila.

  • Si el símbolo es un operador o una función se desapilan tantos números como parámetros, se computa la operación y se apila el resultado.

Al finalizar el procedimiento debe haber exactamente un elemento en la pila, el resultado final. Si la pila se vaciara en algún momento del algoritmo o no hubiera exactamente un número al finalizar, entonces la expresión era incorrecta (Por ejemplo: "(1 + ) * 2").

Estaba dicho ya en la introducción, pero supongamos que tenemos el operador / de división. Este es un operador binario, entonces tendremos que desapilar dos elementos de la pila. El primer elemento que desapilemos será el segundo parámetro del operador.

Es decir:

racional_t *b = pila_desapilar(pila);
racional_t *a = pila_desapilar(pila);
racional_t *r = racional_dividir(a, b);
pila_apilar(r);

En ese orden.

Racionales y decimales

Se dijo que el usuario ingresaría números con decimales, ¿cómo se compatibiliza esto con los racionales?

El número "1234" no contiene punto, por lo que es un racional que se puede incializar con ese numerador y 1 de denominador.

El número "1234.56" tiene punto. Hay dos dígitos después del punto. El mismo puede representarse como el racional con numerador 123456 y denominador 100, donde \(100 = 10^2\), siendo el 2 la cantidad de dígitos decimales.

Inversamente, si quisiera expresarse el número 617/228 con 4 decimales, entonces podemos multiplicar 617 por \(10^4 = 10000\) y efectuar la división entera de 6170000 / 228 = 27061. Simplemente escribiremos un punto a 4 posiciones del final: "2.7061".

Ahora bien, ¿qué pasa si el denominador fuera mayor que el numerador? Por ejemplo, si tenemos 5/142 y queremos expresarlo con 4 decimales, computaremos 50000 / 142 = 352. Como el número dió con 3 dígitos tendremos que antemponer "0." y un cero por cada dígito hasta completar los 4 requeridos, en este caso uno: "0.0352".

(No nos olvidemos que nosotros los enteros los operamos siempre a través de BCD por lo que la cantidad de dígitos es sabida en todo momento.)

De igual manera, si un número fuera ya entero (denominador 1) o todos sus decimales fueran cero a partir de cierto punto, entonces deberemos truncar la salida. Es decir, el número "123.0000" se imprime "123" dado que es entero y el número "123.4000" se imprime "123.4" sin importar que hayamos decidido operar con 4 decimales.

Operadores y funciones

Con todo lo dicho hasta el momento deberíamos saber que los operadores tienen una precedencia y una aridad (también podrían tener una asociatividad, pero simplificamos shunting yard para que todo sea de izquierda a derecha) definidas.

Las funciones también podrían tener distinto número de parámetros. En este trabajo sólo consideraremos funciones de 0 y 1 parámetro. (Si no, habría que agregar las comas a nuestros símbolos y al cómputo de shunting yard.)

Implementar funciones en C sobre racionales es algo tedioso, por lo que en nuestra calculadora vamos a incluir funciones que ya tenemos implementadas y funciones que son sencillas de implementar. Si bien en este trabajo se exigirán pocas funciones, el trabajo debe ser desarrollado teniendo en mente que podamos extenderlo a muchas más funciones.

Operadores:

Símbolo

Aridad

Prioridad

Operación

+

2

1

Suma.

-

2

1

Resta.

*

2

2

Producto.

/

2

3

División.

^

2

4

Potencia, el segundo operando debe tener denominador 1.

_

1

5

Cambio de signo (en C sería el - unario).

Funciones:

Nombre

Parámetros

Operación

fact

1

Factorial, se aplica a numerador y denominador.

abs

1

Valor absoluto del parámetro.

inv

1

Inverso multiplicativo

pi

0

Devuelve el número "3.1416"

e

0

Devuelve el número "2.7182"

phi

0

Devuelve el número "1.618"

Notar del ejemplo de expresiones que los paréntesis son opcionales cuando las funciones tienen un único símbolo como parámetro, por lo que una expresión que diga "pi + 1" estará bien formada, al igual que una que diga "pi() + 1". Análogamente "fact abs(1 - 3)" será equivalente a "fact(abs(1 - 3))".

(Sobre la operación de factorial, notar que al tratarse de la división de dos factoriales puede simplificarse la operación para no tener que computar ambos y luego dividirlos.)

Al respecto de los operadores y funciones, es obligatorio implementar una tabla de búsqueda con todos ellos y utilizar punteros a funciones. La adición de un nuevo operador tiene que limitarse a agregar un registro en la tabla y la función correspondiente.

Dado que operadores y funciones tienen la misma lógica se sugiere implementar una única tabla de búsqueda para ambas.

Cada registro de la tabla debe tener además una pequeña descripción del operador para ser mostrado en la ayuda.

Aplicación

Se debe implementar un programa ./calculadora que permita que el usuario ingrese líneas que representen expresiones, hasta agotar la entrada. Se debe imprimir el resultado de cada una de las expresiones a medida que se introducen.

Si se invocara el programa como ./calculadora ayuda se deberá imprimir la lista de operadores y funciones disponibles con su respectiva descripción.

Por omisión los resultados se expresarán en forma decimal con 8 decimales. Ahora bien, el programa podrá configurarse para trabajar con otra cantidad de decimales o con salida en racional. La invocación ./calculadora racional imprimirá los racionales con el formato de racional_imprimir(). Si se invocara como ./calculadora <n> con <n> cualquier número positivo o cero se imprimirán los resultados con esa cantidad de decimales.

A continuación se muestra un ejemplo de uso:

[santisis@hp]20251_tp1$ ./calculadora ayuda
Calculadora TA130
Uso: ./calculadora [OPCIONES]
OPCIONES:
    ayuda: Muestra esta ayuda.
    racional: Selecciona salida racional.
    <n>: Salida con <n> dígitos de precisión.
OPERADORES:
    a+b: Suma
    a-b: Resta
    a*b: Multiplicación
    a/b: División
    a^b: Potencia entera
    _a: Inverso aditivo
    fact(a): Factorial
    abs(a): Valor absoluto
    inv(a): Inverso multiplicativo
    pi: Número π
    e: Número de Euler
    phi: Número de oro
[santisis@hp]20251_tp1$ ./calculadora
>>> 1/3
0.33333333
>>>
[santisis@hp]20251_tp1$ ./calculadora racional
>>> 1/3
+1/3
>>>
[santisis@hp]20251_tp1$ ./calculadora 20
>>> 1/3
0.33333333333333333333
>>>
[santisis@hp]20251_tp1$ ./calculadora
>>> 1/3
0.33333333
>>> 1/2
0.5
>>> 20/10
2
>>> 4-5
-1
>>> 1 + 2 + 3 + 4
10
>>> 1 + 2 * 3 + 4
11
>>> (1 + 2) * (3 + 4)
21
>>> fact 5
120
>>> fact 5 + 1
121
>>> fact(5 + 1)
720
>>> fact5+1
121
>>> 1 / fact 4
0.04166666
>>> inv fact 4
0.04166666
>>> sqrt 2
Operador inválido "sqrt"!
>>> 1 + 2 +
Cantidad inválida de parámetros para los operadores!
>>> 1 2 + 3
Cantidad inválida de parámetros para los operadores!
>>> (1 + 2
Falta cerrar un paréntesis!
>>> 1 + 2)
Se está cerrando un paréntesis que nunca se abrió!
>>> pi
3.1416
>>> pi + 1
4.1416
>>> pi + e
5.8598
>>> pi / (e + phi)
0.72450532
>>> inv(pi / e)
0.8652279
>>> abs(6-20)
14
>>> 5+3* 2 + (2.25 - fact(3)) / fact42
10.99999999
>>>
[santisis@hp]20251_tp1$ ./calculadora racional
>>> 5+3* 2 + (2.25 - fact(3)) / fact42
+4_121_351_278_741_781_035_726_551_644_983_900_605_146_726_399_999_999/374_668_298_067_434_639_611_504_694_998_536_418_649_702_400_000_000
>>>
[santisis@hp]20251_tp1$ ./calculadora 100
>>> 5+3* 2 + (2.25 - fact(3)) / fact42
10.9999999999999999999999999999999999999999999999999973309724757657102582239982906364178490296995547074
>>>

Estem...

../_images/20251_tp1.jpg

Estem...

[santisis@hp]20251_tp1$ python3
Python 3.6.9 (default, Mar 10 2023, 16:46:00)
[GCC 8.4.0] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> def fact(n):
...     f = 1
...     for i in range(2, n + 1):
...             f *= i
...     return f
...
>>> 5+3* 2 + (2.25 - fact(3)) / fact(42)
11.0
>>>

Valió la pena.

Una última:

[santisis@hp]20251_tp1$ ./calculadora
>>> 8 * 3 + 12 / 4 - 7
20

Vayamos a TN a exigir el título de genios...

Por último notar que lo que implementamos no es un analizador sintáctico para expresiones, sólo un traductor de expresiones correctas para ser computadas. Puede haber expresiones inválidas que sean computables. Siempre y cuando la cantidad de paréntesis y la cantidad de operadores con respecto a los operandos sea válida esto va a funcionar:

[santisis@hp]20251_tp1$ ./calculadora
>>> + 1 2
3
>>> 1 2 3 + +
6

Entregables

Deberá entregarse:

  1. El código fuente del trabajo.

  2. El archivo Makefile para compilar el proyecto.

Nota

El programa debe:

  • estar programado en C,

  • estar completo,

  • compilar...

  • sin errores...

  • sin warnings,

  • correr...

  • sin romperse...

  • sin fugar memoria...

  • resolviendo el problema pedido...

Trabajos que no cumplan con lo anterior no serán corregidos.

La entrega se realiza a través del sistema de entregas.

El ejercicio es grupal permitiéndose grupos de hasta 2 integrantes.

Si elegís hacer el trabajo en grupo te pedimos que nos avises por Discord quién es tu compañero de grupo así lo cargamos en el sistema de entregas. (Si el grupo sufriera alteraciones avisanos también.)