Clases:
h
Nodo:
class nodo {
public:
nodo(char
* val) {insertav(val); inicializahijos();}
void imprimenodo(ofstream& a);
//imprime el valor del nodo
int eshoja()
{if(hijos[0]==NULL){return
1;} else{return 0;}}
//devuelve 1 si es hoja y dos si no
int insertarhijo(nodo
*n); //devuelve 1 si se insertó el hijo
y 0 si el vector de hijos estaba lleno
nodo * gethijo(int
numhijo);
private:
char info[2];
nodo * hijos[3];
nodo * padre;
void insertav(char * val) {strcpy(info, val);}//inserta el valor
del nodo(solo lo usa el constructor)
void inicializahijos();//inicializa
todos los hijos del nodo
int obtenerValor(char*);
}; // nodo
void
nodo::imprimenodo(ofstream&
a){
int inf
= obtenerValor(info);
switch (inf){
case -1:
a<<"'"<<info<<"'"<<"\n";
cout<<"'"<<info<<"'"<<"\n";
break;
case 0:
a<<"expresión"<<"\n";
cout<<"expresion"<<"\n";
break;
case 1:
a<<"término"<<"\n";
cout<<"termino"<<"\n";
break;
case 2:
a<<"factor"<<"\n";
cout<<"factor"<<"\n";
break;
case 3:
a<<"término_resto"<<"\n";
cout<<"termino_resto"<<"\n";
break;
case 4:
a<<"resto_factor"<<"\n";
cout<<"resto_factor"<<"\n";
break;
case 5:
a<<"épsilon"<<"\n";
cout<<"epsilon"<<"\n";
break;
}
}
int
nodo::obtenerValor(char*
c){
char* letras[6] =
{"E","T","F","r1","r2","ep"};
int val= -1;
for(int i=0; i<6;i++){
if(strcmp(letras[i],c)==0){
val = i;
}
}
return val;
}
int
nodo::insertarhijo(nodo *n){
int pos =0;
while(hijos[pos]
!= NULL){pos++;}
if(pos
< cant)
{hijos[pos]= n;
hijos[pos]->padre
= this;
return pos;}
else{return -1;}
}
nodo* nodo::gethijo(int
numhijo){
return
hijos[numhijo];
}
void
nodo::inicializahijos(){
for (int i=0; i<4; i++)
{
hijos[i]=NULL;
}
}
h Arbol:
class
Arbol {
public:
Arbol() {raiz = NULL;archivo.open("salida.txt");}
//constructor por defecto
~Arbol(){delete this->raiz;}
Arbol(nodo
* n) {setraiz(n);archivo.open("salida.txt");}
nodo * getraiz() {return raiz;}//devuelve un
puntero a la raiz
void setraiz(nodo
* n) {raiz = n;}
int insnodo(nodo
* padre, nodo *hijo); //devuelve 1 si lo
inserta el nodo y cero si no
void imprimearbol();
private:
ofstream archivo;
nodo * raiz;
void imprimearbolr(int tabulado, nodo * act);
}; // Arbol
int
Arbol::insnodo(nodo *
padre, nodo *hijo){
if(padre != NULL){
int
pos = padre->insertarhijo(hijo);
return pos;
}
else{return -1;}
}
void
Arbol::imprimearbol(){
int tab = 1;
int cuenta = 0;
raiz->imprimenodo(archivo);
cout << "\n";
while((raiz->gethijo(cuenta) != NULL)
&& (cuenta < cant)){
imprimearbolr(tab, raiz->gethijo(cuenta));
cuenta++;
}
archivo.close();
}
void
Arbol::imprimearbolr(int tabulado, nodo * act){
int cuenta = 0;
for(int i = 1; i <= tabulado; i++)
{archivo<<" ";
cout << " ";}
tabulado++;
act->imprimenodo(archivo);
while((act->gethijo(cuenta) != NULL) && (cuenta < cant)){
imprimearbolr(tabulado,
act->gethijo(cuenta));
cuenta++;
}
}
h
Calculadora:
class Calculadora {
public:
Calculadora(const char* exp=0) : _infijo
(exp) {
Trabaje(); }
void operator = (const char* exp) { _infijo = exp; Trabaje(); }
long Evaluar();
Arbol * aas;
nodo * padre;
// 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
padre = new nodo("E");
aas = new
Arbol(padre);
expr(); // reconocer la expresión _infijo
aas->imprimearbol();
} // 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
nodo * abuelo = padre;
if(aas->getraiz()->eshoja()==0){
nodo
* n = new nodo("E");
int pos = aas->insnodo(padre,n);
padre = padre->gethijo(pos);
}
term();
r1();
padre = abuelo;
} // Calculadora::expr()
void
Calculadora::r1() {
//
r1 ==> + term r1
//
r1 ==> - term r1
// r1
==> £
nodo * abuelo = padre;
nodo* n = new nodo("r1");
int pos = aas->insnodo(padre,n);
padre = padre->gethijo(pos);
if (preAnalisis == '+') { // r1 ==> + term r1
nodo* h = new nodo("+");
aas->insnodo(padre,h);
aparea('+');
term(); {{ _posfijo += '+'; }}
r1();
} else if (preAnalisis == '-') { //
r1 ==> - term r1
aparea('-');
term(); {{ _posfijo += '-'; }}
r1();
} else { // r1 ==> £
nodo*
h = new nodo("ep");
aas->insnodo(padre,h);
padre = abuelo;
}
padre = abuelo;
} // Calculadora::r1()
void
Calculadora::term() {
// term ==> factor r2
nodo * abuelo = padre;
nodo * n = new nodo("T");
int
pos = aas->insnodo(padre,n);
padre = padre->gethijo(pos);
factor();
r2();
padre = abuelo;
} // Calculadora::term()
void
Calculadora::r2() {
// r2
==> * factor r2
// r2
==> / factor r2
// r2
==> £
nodo* n = new
nodo("r2");
nodo* abuelo = padre;
int pos = aas->insnodo(padre,n);
padre = padre->gethijo(pos);
if (preAnalisis == '*') { // r2 ==> * factor r2
aparea('*');
factor(); {{ _posfijo += '*'; }}
r2();
} else if (preAnalisis == '/') { //
r2 ==> / factor r2
aparea('/');
factor(); {{ _posfijo += '/'; }}
r2();
} else { //
r2 ==> £
nodo* h = new nodo("ep");
aas->insnodo(padre,h);
padre = abuelo;
}
} // Calculadora::r2()
void
Calculadora::factor() {
// factor ==> ( expr )
// factor ==> num
nodo * n = new
nodo("F");
nodo * abuelo = padre;
int pos = aas->insnodo(padre,n);
padre = padre->gethijo(pos);
if (preAnalisis == '(') { // factor ==> ( expr
)
nodo * h = new nodo("(");
aas->insnodo(padre,h);
aparea('(');
expr();
aparea(')');
nodo * h2 = new
nodo(")");
aas->insnodo(padre,h2);
} else if (isdigit(preAnalisis)) { //
factor ==> num
num();
} else {
error("El factor no es dígito ni '('");
}
padre = abuelo;
} // Calculadora::factor()
void
Calculadora::num() {
// num ==> 0 | 1 | 2 | 3 | 4 | 5 |
6 | 7 | 8 | 9
if (isdigit(preAnalisis)) {
{{ _posfijo += preAnalisis; }}
char * numero;
numero[0] = preAnalisis;
numero[1] = 0;
nodo* h = new nodo(numero);
aas->insnodo(padre,h);
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;
}
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()
Programa de prueba:
int main() {
char str[200];
Calculadora
C;
long V;
cout<<"++++++++++++++++++++++++++++++++++++++++++++++++++++\n";
cout<<"+ CALCULO DEL ARBOL DE ANALISIS
SINTACTICO +\n";
cout<<"++++++++++++++++++++++++++++++++++++++++++++++++++++\n";
cout<<"\nDigite la expresion:";
cin>>str;
cout<<
"\nEl arbol de analisis sintactico para la expresion "<<str<<"
es:\n";
C = str;
V = C.Evaluar();
return 0;
} // main()