CI-1322 Autómatas y compiladores
Tarea #2
Ejecución de una Calculadora
Realizado por :
Roberto Hernández M. A11727Jorge Villalta A. A13959
Descripción del
problema
En esta tarea se presenta un
programa el cual es una calculadora que evalúa expresiones complejas,
con paréntesis (su código fue obtenido de la dirección http://www.di-mare.com/adolfo/cursos/2004-1/ac-ta-2.htm).
Dicho programa la limitación de que trabaja con números de un solo dígito.
El trabajo a realizar sobre dicho código consite en modificar este programa para que pueda procesar expresiones con números de varios dígitos limitándose a trabajar en los métodos "aparea()", "num()" y "Evaluar()".
Procedimiento
El procedimiento para alcanzar el fin de dicha tarea fue el siguiente:
1. Primero, se trabajó sobre el procedimiento denominado num, el cual originalmente tenía esta estructura:
void Calculadora::num() {
// num ==> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
if (isdigit(preAnalisis)) {
{{ _posfijo += preAnalisis; }}
aparea(preAnalisis);
} else {
error("El token no es dígito");
}
} // Calculadora::num()
Dicha estructura fue modificada a otra que si reconoce números enteros de más de un dígito:
void Calculadora::num() {
// num ==> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
//char temp;
if (isdigit(preAnalisis)) {
while(isdigit(preAnalisis))
{
_posfijo += preAnalisis;
preAnalisis = _infijo[++_cursor];
}
_posfijo += ' ';
preAnalisis = _infijo[--_cursor];
aparea(preAnalisis);
} else {
error("El token no es dígito");
}
} // Calculadora::num()
Los cambios consisten simplemente en que se hace un while que cuando encuentra un dígito, sigue buscando dígitos que estén a la derecha del dígito, y si no hay más devuelve el _cursor al inmediato anterior para no perder lexemas.
2. Luego se trabajó sobre el procedimiento llamado Evaluar, el cual originalmente consistía en algo como esto:
long Calculadora::Evaluar() {
/* resultado
Evalúa la expresión contenida en "*this".
*/
Pila<long> P; // pila usada para evaluar _posfijo
size_t len = strlen(_posfijo);
if (len==0) {
return 0;
}
for (size_t i=0; i < len; ++i) { // recorre toda
la expresión
long op1, op2;
if (isdigit(_posfijo[i])) {
// si es un dígito lo mete en la pila
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 {
P.Push(0);
error("División por cero");
}
}
}
return P.Pop();
} // Calculadora::Evaluar()
Dicha estructura fue modificada a otra que si reconoce números enteros de más de un dígito y los puede evaluar en la pila de long:
long Calculadora::Evaluar() {
/* resultado
Evalúa la expresión contenida en "*this".
*/
Pila<long> P; // pila usada para evaluar _posfijo
size_t len = strlen(_posfijo);
if (len==0) {
return 0;
}
char
* posfi = new char[200];
char
* sig = new char[50];
for (size_t i=0; i < len;
++i) { // recorre toda la
expresión
long
op1, op2;
if(isdigit(_posfijo[i])){
int
k =0;
while(isdigit(_posfijo[i]))
{
// si es un dígito lo mete en la pila
posfi[k] = _posfijo[i];
i++;
k++;
}
posfi[k]
= '\0';
P.Push(atoi(posfi));
}
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 {
P.Push(0);
error("División por cero");
}
}
}
return P.Pop();
} // Calculadora::Evaluar()
Los cambios en esta parte del código consisten en hacer un while para guardar el número leído de la variable _posfijo en una variable char* y luego se pasa a un entero con el procedimiento de la clase String atoi y finalmente se mete en la pila de enteros long para ser evaluado.
Es importante recalcar que se consideró que no era necesario hacer cambios en el procedimiento aparea, puesto que dicho procedimiento no tiene un rol relevante en el reconocimiento de los números, simplemente se come los espacios hasta el siguiente lexema.
Datos
de Prueba del Programa
Los datos de prueba utilizados en el programa fueron:
1. (532 * 343)
2. (100 + 20) * (30 - 44 / 58)
3. (( (((((14 + 12))))) * ((((30 - 10 - 12)))) ))
4. 1 / ( 3 - (2+1) )
5. )
6. 1++
7. 1+2*)
8. (1++
9. (x +
Y los resultados se pueden ver en la siguiente captura de la ventana:
Código
Fuente
CLC.cpp
// CLC.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__) // Compilando con Borland C++
#include <bool.h> // Define bool
para
#endif
#include "Astring.h" // class
string
#include <String.h>
#include <iostream.h>
#include <cctype>
#include <stdio.h>
template <class T>
class Pila {
public:
Pila() { _top = 0; }
void Push(T d);
T Pop();
T top() { return
_vec[_top]; }
private:
enum { Capacidad = 132 };
int _top; // tope de la pila
T _vec[Capacidad]; // vector para la pila
}; // Pila
template <class T>
inline void Pila<T>::Push(T d) {
_vec[_top] = d;
_top++;
}
template <class T>
inline T Pila<T>::Pop() {
_top--;
return _vec[_top];
}
typedef char Token; // OJO: Astring sólo funciona para "char"
class Calculadora {
public:
Calculadora(const char* exp=0) : _infijo (exp) { Trabaje(); }
void operator = (const char* exp) { _infijo = exp; Trabaje(); }
long Evaluar();
// expr ==> term r1
private:
// r1 ==> + term r1
void expr();
// r1 ==> - term r1 | £
void r1();
//
void term();
// term ==> factor r2
void r2();
// r2 ==> * factor r2 | £
void factor(); // r2 ==> / factor r2
void num();
//
// factor ==> ( expr ) |
num
//
void aparea(Token); // num ==> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7
| 8 | 9
void Trabaje();
void error(const char * msg);
private:
Token preAnalisis; // siguiente token
Astring _infijo; // hilera inicial
Astring _posfijo; // hilera resultado
size_t _cursor; // posición en _infijo
}; // Calculadora
void Calculadora::Trabaje() {
/* resultado
Traduce a notación posfija la exrpesión almancenada
en *this.
- Para evaluarla, hay que invocar a Calculadora::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] == ' ') { // ignora blancos al inicio
_cursor++;
}
preAnalisis = _infijo[_cursor]; // inicializa preAnalisis
expr(); // reconocer la expresión _infijo
} // Calculadora::Trabaje()
void Calculadora::error(const char * msg) {
/* resultado
Graba en "cout" un mensaje de error.
- Indica la posición actual de proceso en al hilera de entrada.
*/
cout << "ERROR(" << 1+_cursor << ")";
if (msg != 0) { // +1 porque _cursor comienza en 0
if (msg[0] != 0) {
cout << ": " << msg;
}
}
cout << endl;
} // Calculadora::error()
void Calculadora::expr() {
// expr ==> term r1
term();
r1();
} // Calculadora::expr()
void Calculadora::r1() {
// r1 ==> + term r1
// r1 ==> - term r1
// r1 ==> £
if (preAnalisis == '+')
{
// r1 ==> + term r1
aparea('+');
term(); {{ _posfijo += '+'; }}
r1();
} else if (preAnalisis == '-')
{
// r1 ==> - term r1
aparea('-');
term(); {{ _posfijo += '-'; }}
r1();
} else { }
// r1 ==> £
} // Calculadora::r1()
void Calculadora::term() {
// term ==> factor r2
factor();
r2();
} // Calculadora::term()
void Calculadora::r2() {
// r2 ==> * factor r2
// r2 ==> / factor r2
// r2 ==> £
if (preAnalisis == '*')
{
// r2 ==> * factor r2
aparea('*');
factor(); {{ _posfijo += '*'; }}
r2();
} else if (preAnalisis ==
'/') {
// r2 ==> / factor r2
aparea('/');
factor(); {{ _posfijo += '/'; }}
r2();
} else { } // r2 ==> £
} // Calculadora::r2()
void Calculadora::factor() {
// factor ==> ( expr )
// factor ==> num
if (preAnalisis == '(')
{
// factor ==> ( expr )
aparea('(');
expr();
aparea(')');
} else if (isdigit(preAnalisis)) { // factor ==> num
num();
} else {
error("El factor no es dígito ni '('");
}
} // Calculadora::factor()
void Calculadora::num() {
// num ==> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
//char temp;
if (isdigit(preAnalisis)) {
//inician cambios, simplemente se hace un while que cuando encuentra un dígito, sige buscando dígitos
//que esten a la derecha del dígito, y si no hay más devuelve el _cursor al inmediato anterior para
//no perder lexemas
/*****************************************************************************************************************/
while(isdigit(preAnalisis))
{
_posfijo += preAnalisis;
preAnalisis = _infijo[++_cursor];
}
_posfijo += ' ';
preAnalisis = _infijo[--_cursor];
aparea(preAnalisis);
/*****************************************************************************************************************/
} else {
error("El token no es dígito");
}
} // Calculadora::num()
void Calculadora::aparea(Token ch) {
/* resultado
Consume el terminal, y avanza al siguiente lexema.
- Si "ch" no coincide con el valor de "preAnalisis"
emite un error.
*/
if (preAnalisis != ch) {
error("Token inesperado");
}
preAnalisis = _infijo[++_cursor];
while (_infijo[_cursor] == ' ') { // ignora blancos
preAnalisis = _infijo[++_cursor];
}
} // Calculadora::aparea()
long Calculadora::Evaluar() {
/* resultado
Evalúa la expresión contenida en "*this".
*/
Pila<long> P; // pila usada para evaluar _posfijo
size_t len = strlen(_posfijo);
if (len==0) {
return 0;
}
//inician cambios, estas son sólo dos variables locales usadas para almacenar partes del posfijo
/*****************************************************************************************************************/
char
* posfi = new char[200];
char
* sig = new char[50];
/*****************************************************************************************************************/
for (size_t i=0; i < len; ++i)
{ // recorre toda la
expresión
long
op1, op2;
if(isdigit(_posfijo[i])){
//inician cambios, lo unico que se hace es un while para guardar el número en una variable char*
//luego se pasa a un entero con atoi y finalmente se mete en la pila de long para ser evaluado
/*****************************************************************************************************************/
int
k =0;
while(isdigit(_posfijo[i]))
{
// si es un número lo mete en la pila
posfi[k] = _posfijo[i];
i++;
k++;
}
posfi[k]
= '\0';
P.Push(atoi(posfi));
/*****************************************************************************************************************/
}
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 {
P.Push(0);
error("División por cero");
}
}
}
return P.Pop();
} // Calculadora::Evaluar()
int main() {
char str[200];
Calculadora C;
long V;
cout << endl <<
endl;
strcpy(str, "(532 *
343)");
C = str;
V = C.Evaluar();
cout << V << " == " << str
<< endl;
strcpy(str, "(100 + 20)
* (30 - 44 / 58)");
C = str;
V = C.Evaluar();
cout << V << " == " << str
<< endl;
strcpy(str, "(( (((((14 + 12))))) * ((((30
- 10 - 12)))) ))" );
C = str;
V = C.Evaluar();
cout << V << " == " << str
<< endl;
strcpy(str, "1 / ( 3 -
(2+1) )");
C = str;
cout << str <<
" == " << endl;
V = C.Evaluar();
cout << "==
" << V << endl;
strcpy(str, ")" );
cout << str << endl;
C = str;
strcpy(str, "1++"
);
cout << str <<
endl;
C = str;
strcpy(str, "1+2*)" );
cout << str <<
endl;
C = str;
strcpy(str, "(1++"
);
cout << str <<
endl;
C = str;
strcpy(str, "(x +"
);
cout << str <<
endl;
C = str;
return 0;
} // main()
// EOF: CLC.cpp
Astring.cpp
// Astring.cpp (c) 2001 adolfo@di-mare.com
/* programador: Adolfo Di Mare
*/
/* invariante
this->_s == 0 ==> la hilera está vacía
this->_s != 0 ==> *(_s) es un vector en memoria dinámica de n+1 chars,
con n == strlen(_s)
Astring::null == 0 siempre ==> ésta es la hilera nula ""
*/
#include "Astring.h"
char Astring::null = 0;
Astring& Astring::operator =
(const char *str) {
/* resultado
Cambia el valor de "*this" para que sea igual a "str".
*/
if (_s != 0) { // borra el valor anterior
delete [] _s;
_s =
0;
}
if (str != 0) {
// no está vacía y...
if
(str[0] != 0) { // no es la
hilera nula
_s = new char [1 + strlen(str)];
strcpy( _s, str );
}
}
return *this;
}
Astring& Astring::operator +=
(const char * str) {
/* resultado
Le agrega al final a "*this" el valor de "str".
*/
if (str == 0) {
return *this; // no hay nada que agregar
}
if (str[0] == 0) {
return *this;
}
if (_s == 0) { // copia directo la hilera
size_t len_str = strlen(str);
_s =
new char [1 + len_str];
memcpy( _s, str, len_str );
_s[len_str] = 0;
}
else {
size_t len_s =
strlen(_s);
size_t len_str = strlen(str);
char
* tmp = new char [len_s + len_str + 1];
memcpy(tmp, _s, len_s);
memcpy(tmp+len_s, str, len_str);
tmp[len_s +
len_str] = 0;
delete []_s;
_s =
tmp;
}
return *this;
}
// EOF: Astring.cpp
Astring.h
// Astring.h (c) 2001 adolfo@di-mare.com
/* resultado
Implementa algunas de las operaciones principales para la
clase "Astring" de hileras.
- La implementación es muy simple y funciona, pero no es muy eficiente
(es adecuada para los estudiantes).
*/
/* programador: Adolfo Di Mare
*/
#ifndef Astring_h
#define Astring_h // evita la inclusión múltiple
#if defined(__BORLANDC__) // Compilando con Borland C++
#include <bool.h> // Define bool para BC++ v3.1 o inferior
#endif
#include <cstdlib>
#include <cstring>
class ostream; class istream; //
para operator << y operator >>
class Astring {
private:
char * _s;
static char null; // "" == hilera nula
public:
Astring()
: _s(0) { } // constructor
de vector
Astring(Astring&
str) : _s(0) { *this =
str._s; }
Astring(const char* str) :
_s(0) { *this = str; }
Astring(char c) : _s(0) {
char v[2]; v[0] = c; v[1] = 0;
*this = v; }
~Astring() { if (_s != 0) {
delete [] _s; } } // destructor
Astring& operator = (const char *);
Astring& operator = (const Astring& str) { return
*this = str._s; }
Astring& operator +=
(const Astring& str) { return *this += str._s; }
Astring& operator +=
(const char *);
char& operator[] (size_t
i) { return _s[i]; }
friend Astring operator +
(const Astring&, const Astring&);
operator const char* ()
const { return (_s==0 ? (&null) : _s); }
friend bool operator ==
(const Astring&, const Astring&);
friend bool operator
< (const Astring&, const
Astring&);
friend bool operator !=
(const Astring&, const Astring&);
friend bool operator <=
(const Astring&, const Astring&);
friend bool operator >=
(const Astring&, const Astring&);
friend bool operator
> (const Astring&, const
Astring&);
friend ostream& operator
<< (ostream &, const Astring& );
friend istream& operator
>> (istream &,
Astring& );
friend double real (const Astring& ); // Conversión a real
friend long integer(const Astring& ); // Conversión a long
// excluidos porque producen ambigüedad con operadores aritméticos
// operator double () { return double(_s) /
double(_den); }
// operator long () { return
_s / _den
; }
}; // Astring
inline bool operator == (const
Astring &x, const char * y) {
return strcmp((const
char*)x, y) == 0;
} // operator ==
inline bool operator < (const Astring &x, const char *
y) {
return strcmp((const
char*)x, y) < 0;
} // operator <
inline bool operator == (const
Astring &x, const Astring &y) {
return strcmp((const
char*)x, (const char*)y) == 0;
} // operator ==
inline bool operator < (const
Astring &x, const Astring &y) {
return strcmp((const
char*)x, (const char*)y) < 0;
} // operator <
inline bool operator > (const
Astring &x, const Astring &y) {
return (y < x);
} // operator >
inline bool operator != (const
Astring& x, const Astring& y) {
return !(x == y);
} // operator !=
inline bool operator <= (const
Astring& x, const Astring& y) {
return !(y < x);
} // operator <=
inline bool operator >= (const
Astring& x, const Astring& y) {
return !(x < y);
} // operator >=
#endif // Astring_h
// EOF: Astring.h