Universidad de Costa Rica
Escuela de Ciencias de la
Computación e Informática
Profesor Adolfo Di Mare
CI-1322
II Semestre 2003
[<=] [home] [<>] [\/] [=>]
CI-1322 Autómatas y compiladores

Tarea #2 [solución]

Ejecución de la Calculadora

      El programa de la Figura 1 es una calculadora que evalúa expresiones complejas, con paréntesis. Tiene la limitación de que trabaja con dígitos simples.

      Ejecute paso a paso este programa y muestre cómo se comportan los campos de la variable "C", que es una instancia de la clase Calculadora. Explique qué está ocurriendo y por qué el programa calcula correctamente las expresiones aritméticas.

      Para la ejecución de este programa use las siguientes expresiones:

     

// 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 BC++ v3.1 o inferior
#endif

#include "Astring.h"       // class string

#include <iostream.h>
#include <cctype>


template <class T>
class Pila {
public:
    Pila() { _top = 0; }
    void   Push(T d);
    T      Pop();
    T      Top() { return _vec[_top-1]; }
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 expresió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();      // reconoce 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

    if (isdigit(preAnalisis)) {
        {{ _posfijo += preAnalisis; }}
        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.c_str());
    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()

int main() {
    char str[200];
    Calculadora C;
    long        V;

    cout << endl << endl;
    strcpy(str, "(5 * 3)");
    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;

    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
Figura 1

      Entregue su tarea por correo electrónico, como lo hizo anteriormente.

[mailto:] Entrega de Tareas

Tiempo de entrega: 1 semana
Modalidad: En parejas

Soluciones

[mailto:] Adolfo Di Mare <adolfo@di-mare.com>.
Copyright © 2003
Derechos de autor reservados © 2003
[home] <> [/\]