El programa dado es una calculadora que evalúa expresiones complejas, con paréntesis. Tiene la limitación de que trabaja con dígitos simples. El trabajo consiste en modificar este programa para que pueda procesar expresiones con números de varios dígitos.

La solución de este proyecto se encuentra en siguiente página, desde donde también se puede conseguir el código fuente.

https://mauricioulate.tripod.com/Automatas/tarea1/t1sol983660.html

Descripción del problema a resolver

Objetivos

Se debe modificar la clase Compilador para que cuando compile, lo haga en un formato en el que se pueda trabajar con números de múltiples dígitos.

Planteo

La entrada de la expresión debe hacerse sin errores, es decir, el programa no es capaz de analizar la expresión a ver si contiene errores (como de no cerrar todos los paréntesis). La expresión es compilada insertando un caracter limítrofe para indicar el fin de un número, para así lograr el soporte de números de varios dígitos. Luego, al evaluar, se utiliza el caracter límite para poder diferenciar un número de otro.

Requerimientos

Se requiere que el programa sea capaz de realizar sumas, restas, multiplicaciones en forma de expresiones y sub-expresiones separadas por paréntesis.

Abstracción

Especificación de la clase

Clase Compilador

Esta clase recibe una expresión y la compila, dejando el resultado en un formato compatible con la operación evaluar

class Compilador {

public:

Compilador(const char* exp=0) : _infijo (exp) { Trabaje(); }

void operator = (const char* exp) { _infijo = exp; Trabaje(); }

long Evaluar();

private: // expr ==> term r1

void expr(); // r1 ==> + term r1

void r1(); // r1 ==> - term r1 | œ

void r2(); //

void term(); // term ==> factor r2

void factor(); // r2 ==> * factor r2

void aparea(); // r2 ==> / factor r2 | œ

void num(); //

// factor ==> ( expr )

// factor ==> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

void Trabaje();

void error(const char * msg);

private:

char preAnalisis; // siguiente token

Astring _infijo; // hilera inicial

Astring _posfijo; // hilera resultado

size_t _cursor; // posici¢n en _infijo

}; // Compilador

Operaciones

Las operaciones del ADT Compilador se dividen en dos. El primer grupo se encarga de compilar la expresión y el segundo de evaluarla.

Operaciones de compilación:

Trabaje();

Operación invocada para realizar la compilación.

void expr(); // expr ==> term r1

Llama a las operaciones TERM y R1 para poder ir analizando cada parte de una expresión. TERM toma términos, es decir un número o números unidos por operandos de multiplicación o división. Luego R1 busca una suma o resta.

void term(); // term ==> factor r2

Operación que une número o expresiones a la izquierda de un operador de suma o resta, lo cual corresponde a un término.

void r1(); // r1 ==> - term r1 | œ

Operación que se encarga de buscar el final de un término con el símbolo de una suma o una resta.

void r2();

Operación que se encarga de buscar la unión entre números de un término de una expresión con el símbolo de multiplicación o de división.

void factor(); // r2 ==> * factor r2

Operación que se encarga de revisar si un factor de una operación es por sí misma una expresión.

void aparea(); // r2 ==> / factor r2 | œ

Operación que suprime los espacios en el análisis de una expresión.

void num(); //

// factor ==> ( expr )

// factor ==> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Este método sirve para reconocer números. Método modificado para que inserte el caracter límite $ al encontrarse con un fin de número.

error(const char * msg);

Graba un mensaje de error y cancela el programa.

Operaciones de evaluación

Evaluar() {

Evalúa la expresión contenida en _postfijo.

Arquitectura del programa

Cuando el programa recibe una expresión, la recibe en forma infija, esto es, la operación está escrita entre los 2 operandos. Ej.: (2 + 3) * 4. En el caso de la multiplicación, un operando es el 4 y el otro es la expresión (2 + 3). Es la forma más común de representar una expresión.

A la hora de compilar una expresión, el compilador convierte esa expresión a formato postfijo, esto es, primero los dos operandos y luego la operación. Ej.: 2 + 3 se escribiría 23+, esto según el algoritmo inicial del programa, con la limitante de que no puede diferenciar si el 2 es un número o tan solo un dígito de un número más grande. Con el algoritmo corregido la expresión se escribiría 2$3$+. Esto permite escribir expresiones como 10 + 50 como 10$50$+ diferenciando un operando del otro por el caracter límite $.

Implementación

Modelo de la clase

El modelo del ADT es un diagrama de la estructura de datos usado para implementarlo. Los campos del REP de la clase no es posible modelarlos en un diagrama, por lo que se presenta como cuadro:

Rep

preAnalisis

_infijo

_posfijo

_cursor

Los campos _infijo y _posfijo son de tipo Astring que son un tipo de hilera de caracteres. El campo preAnalisis es un caracter. El _cursor es un número tipo size_t.

Arquitectura interna del programa

A la hora de compilar una expresión,

Compilador usado

Se utilizó Microsoft Visual Studio 6.0 para compilar el programa, pero se puede utilizar cualquier compilador que contenga las bibliotecas actualizadas (en lugar de stdlib.h tiene cstlib.h y que contenga bool.h).

¿Cómo compilar el programa?

Como los datos de prueba están contenidos en el proceso principal (main()) del programa, no se tiene que incluir ningún parámetro a la hora de compilar.

Guía de uso del programa

El programa no es utilizable por un usuario en el sentido que los datos de prueba están dentro del main y no son recibidos como parámetro del programa, por lo que sólo pueden ser modificados dentro del código fuente, para luego ser recompilado.

Se asume que el usuario escribe la expresión siempre de forma correcta.

Entradas vs. Salidas esperadas

A continuación se presenta un ejemplo de salida del programa.

Código fuente

// Parser.cpp (C) adolfo@di-mare.com

/* resultado

Eval£a expresiones aritm‚ticas simples en que los

operandos son n£meros del 0 al 9.

#if defined(__BORLANDC__) // Definida para Borland C++

#if (__BORLANDC__ <= 0x0410) // Versi¢n v3.1 o inferior

#include <bool.h> // Define tipo bool

#endif

#include "Astring.h" // class string

#include <iostream.h>

#include <cctype>

class Pila {

public:

Pila() { _top = 0; }

void Push(long d);

long Pop();

long top() { return _vec[_top]; }

private:

enum { Capacidad = 132 };

int _top; // tope de la pila

long _vec[Capacidad]; // vector para la pila

}; // Pila

inline void Pila::Push(long d) {

_vec[_top] = d;

_top++;

}

inline long Pila::Pop() {

_top--;

return _vec[_top];

}

class Compilador {

public:

Compilador(const char* exp=0) : _infijo (exp) { Trabaje(); }

void operator = (const char* exp) { _infijo = exp; Trabaje(); }

long Evaluar();

private: // expr ==> term r1

void expr(); // r1 ==> + term r1

void r1(); // r1 ==> - term r1 | œ

void r2(); //

void term(); // term ==> factor r2

void factor(); // r2 ==> * factor r2

void aparea(); // r2 ==> / factor r2 | œ

void num(); //

// factor ==> ( expr )

// factor ==> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

void Trabaje();

void error(const char * msg);

private:

char preAnalisis; // siguiente token

Astring _infijo; // hilera inicial

Astring _posfijo; // hilera resultado

size_t _cursor; // posici¢n en _infijo

}; // Compilador

void Compilador::Trabaje() {

/* resultado

Traduce a notaci¢n posfija la expresi¢n almancenada

en *this.

- Para evaluarla, hay que invocar a Compilador::Evaluar().

/* requiere

- La expresi¢n almacenada no debe tener errores de sintaxis.

_posfijo = "";

if (_infijo == "") { // No se digit¢ ninguna expresi¢n

return;

}

_cursor = 0;

while (_infijo[_cursor] == ' ') { // ignorar blancos al inicio

_cursor++;

}

preAnalisis = _infijo[_cursor]; // iniciar preAnalisis

expr(); // reconocer la expresi¢n _infijo

}

void Compilador::error(const char * msg) {

/* resultado

Graba un mensaje de error y cancela el programa.

if (msg != 0) {

if (msg[0] != 0) {

cout << "ERROR: " << msg;

}

else {

cout << "ERROR";

}

else {

cout << "ERROR";

}

exit(1); // cancela el programa

}

void Compilador::expr() {

// expr ==> term r1

term();

r1();

}

void Compilador::r1() {

// r1 ==> + term r1

// r1 ==> - term r1

// r1 ==> œ

if (preAnalisis == '+') {

aparea();

term(); {{ _posfijo += '+'; }}

r1();

} else if (preAnalisis == '-') {

aparea();

term(); {{ _posfijo += '-'; }}

r1();

} else { } // r1 ==> œ

}

void Compilador::term() {

// term ==> factor r2

factor();

r2();

}

void Compilador::r2() {

// r2 ==> * factor r2

// r2 ==> / factor r2

// r2 ==> œ

if (preAnalisis == '*') {

aparea();

factor(); {{ _posfijo += '*'; }}

r2();

} else if (preAnalisis == '/') {

aparea();

factor(); {{ _posfijo += '/'; }}

r2();

} else { } // r2 ==> œ

}

void Compilador::factor() {

// factor ==> ( expr )

// factor ==> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

if (preAnalisis == '(') {

aparea();

expr();

if (preAnalisis == ')' ) {

aparea();

}

} else if (isdigit(preAnalisis)) {

num();

} else { //

error("El factor no es par‚ntesis ni d¡gito");

}

void Compilador::aparea() {

/* resultado

Consume el terminal, y avanza al siguiente lexema.

if (preAnalisis != _infijo[_cursor]) {

error(0);

}

preAnalisis = _infijo[++_cursor];

while (_infijo[_cursor] == ' ') { // ignora blancos

preAnalisis = _infijo[++_cursor];

}

void Compilador::num() {

/* resultado

Este m‚todo sirve para reconocer n£meros.

Regla: num -> digito num '.' digito num

if (isdigit(preAnalisis)) {

aparea();

num();

} else {

// Cambio por Mauricio Ulate

/* Caracter $ indica fin de número.

Agrega soporte para números de múltiples dígitos.

}

long Compilador::Evaluar() {

/* resultado

Eval£a la expresi¢n contenida en "*this"

Pila P; // pila usada para evaluar _posfijo

size_t len = strlen(_posfijo);

// Cambio por Mauricio Ulate

size_t factor = 0;

// Fin cambio por Mauricio Ulate

if (len==0) {

return 0;

}

for (size_t i=0; i < len; ++i) { // recorre toda la expresi¢n

// Corrección al código fuente del profe

// Mauricio Ulate

long op1, op2;

if (isdigit(_posfijo[i])) {

// si es un d¡gito lo mete en la pila

// Cambio por Mauricio Ulate

factor *= 10;

factor += _posfijo[i] - '0';

// Fin cambio por Mauricio Ulate

//P.Push( _posfijo[i] - '0');

} else if (_posfijo[i] == '+') { // Si es +, saca los operandos

op1 = P.Pop(); // de la pila y los suma

op2 = P.Pop();

P.Push(op2 + op1); // mete el resultado intermedio en la pila

} else if (_posfijo[i] == '-') { // Si es - resta

op1 = P.Pop();

op2 = P.Pop();

P.Push(op2 - op1); // lo mete en la pila

} else if (_posfijo[i] == '*') {

op1 = P.Pop();

op2 = P.Pop();

P.Push(op2 * op1);

} else if (_posfijo[i] == '/') {

op1 = P.Pop();

op2 = P.Pop();

if (op1 != 0) { // para no dividir entre 0

P.Push(op2 / op1);

} else {

error("No se puede dividir entre cero");

}

// Cambio por Mauricio Ulate

} else if (_posfijo[i] == '$') {

P.Push( factor );

factor = 0;

}

// Fin Cambio por Mauricio Ulate

}

return P.Pop();

}

int main() {

char str[200];

Compilador C;

long V;

strcpy(str, "(5 * 35) + 5");

C = str;

V = C.Evaluar();

cout << V << " == " << str << endl;

strcpy(str, "(1 + 2) * (3 - 4 - 5)");

C = str;

V = C.Evaluar();

cout << V << " == " << str << endl;

strcpy(str, "(( (((((1 + 2))))) * ((((3 - 4 - 5)))) ))" );

C = str;

V = C.Evaluar();

cout << V << " == " << str << endl;

return 0;

}

// EOF: Parser.cpp

Parser.cpp

Bibliografía

· Stroustrup, Bjarne. The C++ Programming Language, Special Edition. Addison-Wesley, 2000.

· Aho, Alfred, et al. Compiladores: Principios, técnicas y herramientas. Addison-Wesley Iberoamericana, 1990.

Sitios

Documentación:

https://mauricioulate.tripod.com/Automatas/tarea1/t1sol983660.html

Archivo .ZIP con solución:

https://mauricioulate.tripod.com/Automatas/tarea1/983660.zip