Vamos ver neste artigo como programar um autómato de soma (em anexo pode fazer download do autómato calculadora), ou seja é pedida uma expressão ao utilizador:

:> 12+3


A ideia é o autómato verificar se 12+3 é uma expressão correcta e bem formada para se efectuar a operação soma, e no final mostrar no ecrã o resultado da operação, neste caso 15.

Então como começar?

Já foi visto anteriormente num poste como abordar este tipo de problemas (ver aqui), mas volto a lembrar que os passos essenciais são:

 

  •  Desenhar o nosso autómato
  •  Fazer a representação da tabela de transição de estados
  •  Computacionar o autómato

 

 

Então, pensando um pouco no autómato que devo implementar, sei que vou ter dígitos, o carácter soma e mais dígitos, mais carácter soma, mais dígitos…

Algo assim:

1+1+1+1+1+1+1 ou assim 12+3+1+500 ou assim 500+104

Hum, ok, já começo a encadear e sincronizar as ideias, então vou precisar de um autómato assim:

 
 
 

Em que vou recebendo dígitos em q0, quando receber o carácter ‘+’ vou para q1 e quando receber mais dígitos volto para q0 aplicando “n” vezes o mesmo passo.


Bem, se bem nos lembramos tendo isto, temos quase 50% do trabalho concluído, vá 40%, agora com a construção da tabela ficamos com 70%, em que 30% que falta fica para a passagem do autómato para código máquina. Como vêm não é nada difícil.

Vamos então à tabela de transição de estados:



O q2 é um estado que não está representado no autómato, mas é um estado de erro, se nenhuma daquelas condições se verificar então o autómato passara para o estado q2, que é um poço sem saída.


Pronto, tendo isto basta só computacionar o autómato, vamos a isso, à ultima fase.

Quais os passos a implementar?

  • Pedir ao utilizador uma string (a string de analise)
  • Declarar uma variável (estado actual) para percorrer o autómato
  • Basicamente o nosso autómato vai ser definido por uma matriz, muito parecido com a tabela a cima.


Muito simples, vamos pedir ao utilizar para inserir uma string, e valida-la.

:> 12+3

Temos uma função que recebe como parâmetros a nossa matriz, que é o nosso autómato, e passamos também como parâmetro o “estado actual” e o elemento a analisar (neste caso o 12, ou o +, ou o 3 depende onde já vamos.)

Em seguida nessa função se estamos imaginamos no estado 1, então sabemos anteriormente foi passado o carácter da soma -> ‘+’ e posteriormente terá que ser passado um digito.

Verificamos e retornamos o novo estado, como se fosse uma máquina de estados, onde entra qualquer coisa e sai qualquer coisa, simples não? Vamos dar uma olhadela no código.



Neste caso entra um estado (diz sempre respeito à linha da matriz, e vamos ver a saída possível para o carácter (ch)).




Neste caso percorremos todos os caracteres da string, e vamos andando no automato.

Inicialmente o estado=0, logo vamos a 1º linha da matriz, se entrar um número entra estado=0, então 1->q0, ficamos em q0 espera de mais numero e parece que está a correr bem.


Uma outra variação que este autómato vai ter em relação ao do artigo anterior é que temos de ir guardando os valores e soma-los para que no final possamos apresentar o
resultado.

Para tal, após a analise de cada (ch) ou seja cada caracter da string e a posterior obtenção do novo estado fazemos essa verificação.

 

Observando o pedaço de código reparamos que temos o bloco iterativo “for” que permite obter o estado do autómato e logo de seguida o bloco condicionar “case” que irá fazer algo se algo acontecer.

Muito bem, se o estado actuar for q0, vamos somar valores 12+12+12. 

É utilizada uma flag porque os nossos inteiros estão guardados numa string e se verificarmos o seguinte:


String[0] > 12
String[1]2


O que quero dizer com isto é que é preciso tomar cuidado na análise de string com dígitos, daí aquele meu “case” com a flag, porque somente me interessa a 1º posição da composição do número, porque o próprio número esta guardado conforma a tabela
ascii e após a conversão algo extraordinário pode acontecer, é preciso tomar cuidado.

Ok, então se eu em String quiser colocar 300 como ficaria?

String[0]->301
String[1]->0
String[2]->1

Ah, percebido.


Última parte do nosso programa é verificar que o estado, é realmente o estado final do autómato, em caso afirmativo temos uma string que é válida.

Como se pode observar, foi algo muito simples.

Deixo então em anexo o código relativo ao autómato soma e calculadora.


Código autómato soma:

  1. /*###################################################
  2. #      Automato Calculadora de Somar                #  
  3. #             Code by Pedro Tavares                 #
  4. #                                                   #
  5. #                                                   #
  6. ####################################################*/
  8. #include <stdio.h>
  9. #include <string.h>
  12. int delta(int M[3][2],int estado,char ch){
  14.         if (estado==-1)
  15.                 return –1;
  17.         if(ch >=‘0’ && ch <=‘9’)
  18.                 return(M[estado][0]);
  20.         if(ch==‘+’)
  21.                 return(M[estado][1]);
  22. return (–1);
  23. }
  27. int main(){
  29.         int M[3][2]={
  30.                         {0,1},{0,2},{2,2}
  31.                     }; 
  33.         char s[15];
  34.         int estado=0,i,res=0,flag=0;
  35.        
  37.         printf(“Introduza a String de calculo!n“);
  38.         scanf(“%s”,s);
  39.        
  40.        
  41.         for(i=0;i<strlen(s);i++){
  42.                
  43.                 estado=delta(M,estado,s[i]);
  44.                        
  45.                 if(estado==-1)
  46.                                 break;
  48.                 switch(estado){
  51.                         case 0:
  52.                                 if(flag==0){
  53.                                         res+=atoi(&s[i]);
  54.                                         flag=1;
  55.                                 }
  56.                                
  57.                         break;
  60.                         case 1:
  61.                                 flag=0;
  62.                         break;
  64.                 }
  66.         }
  67.        
  68.         if(estado==0){
  69.                 printf(“aceite!n“);
  70.                
  71.                 printf(“A soma ‘e: %dn“,(res));
  72.                
  73.         }
  74.         else if(estado==-1)
  75.                 printf(“Expressao mal construida – Nao aceiten“);
  76.         else{
  77.                 printf(“Expressao mal construida – Nao aceiten“);     
  78.         }
  82. return(0);
  84. }



Código autómato calculadora:

  1. /*###################################################
  2. #      Automato Calculadora de Somar                #  
  3. #             Code by Pedro Tavares                 #
  4. #                                                   #
  5. #                                                   #
  6. ####################################################*/
  7. #include <stdio.h>
  8. #include <string.h>
  11. int delta(int M[3][2],int estado,char ch){
  13.         if (estado==-1)
  14.                 return –1;
  16.         if(ch >=‘0’ && ch <=‘9’)
  17.                 return(M[estado][0]);
  19.         if(ch==‘+’ || ch==‘-‘ || ch==‘*’ || ch==‘/’)
  20.                 return(M[estado][1]);
  21. return (–1);
  22. }
  26. int main(){
  28.         int M[3][2]={
  29.                         {0,1},{0,2},{2,2}
  30.                     }; 
  32.         char s[15];
  33.         int estado=0,i,res=0,flag=0;
  34.         char op=‘x’;
  35.        
  37.         printf(“Introduza a String de calculo!n“);
  38.         scanf(“%s”,s);
  39.        
  40.        
  41.         for(i=0;i<strlen(s);i++){
  42.                
  43.                 estado=delta(M,estado,s[i]);
  44.                        
  45.                 if(estado==-1)
  46.                                 break;
  48.                 switch(estado){
  51.                         case 0:
  52.                                 if(flag==0){
  53.                                         if(op!=‘x’){                                   
  54.                                                 if(op==‘+’){
  55.                                                         res+=atoi(&s[i]);
  56.                                                         flag=1;
  57.                                                 }
  58.                                                 else if(op==‘-‘){
  59.                                                         res-=atoi(&s[i]);
  60.                                                         flag=1;
  61.                                                 }
  62.                                                 else if(op==‘*’){
  63.                                                         res=(res*atoi(&s[i]));
  64.                                                         flag=1;
  65.                                                 }
  66.                                                 else if(op==‘/’){
  67.                                                         res=(res/atoi(&s[i]));
  68.                                                         flag=1;
  69.                                                 }
  70.                                                
  71.                                         }
  72.                                         else{
  73.                                                 res+=atoi(&s[i]);
  74.                                                 flag=1;
  75.                                         }
  76.                                 }
  77.                                
  78.                         break;
  81.                         case 1:
  82.                                 flag=0;
  84.                                 if(s[i]==‘+’)
  85.                                         op=‘+’;
  86.                                 else if (s[i]==‘-‘)
  87.                                         op=‘-‘;
  88.                                 else if (s[i]==‘/’)
  89.                                         op=‘/’;
  90.                                 else if (s[i]==‘*’)
  91.                                         op=‘*’;
  92.                         break;
  94.                 }
  96.         }
  97.        
  98.         if(estado==0){
  99.                 printf(“aceite!n“);
  100.                
  101.                 printf(“O resultado e’: %dn“,(res));
  102.                
  103.         }
  104.         else if(estado==-1)
  105.                 printf(“Expressao mal construida – Nao aceiten“);
  106.         else{
  107.                 printf(“Expressao mal construida – Nao aceiten“);     
  108.         }
  112. return(0);
  114. }