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 q1quando 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. ####################################################*/
  7. #include <stdio.h>
  8. #include <string.h>
  9. int delta(int M[3][2],int estado,char ch){
  10.         if (estado==-1)
  11.                 return 1;
  12.         if(ch >=‘0’ && ch <=‘9’)
  13.                 return(M[estado][0]);
  14.         if(ch==‘+’)
  15.                 return(M[estado][1]);
  16. return (1);
  17. }
  18. int main(){
  19.         int M[3][2]={
  20.                         {0,1},{0,2},{2,2}
  21.                     }; 
  22.         char s[15];
  23.         int estado=0,i,res=0,flag=0;
  24.        
  25.         printf(“Introduza a String de calculo!n);
  26.         scanf(“%s”,s);
  27.        
  28.        
  29.         for(i=0;i<strlen(s);i++){
  30.                
  31.                 estado=delta(M,estado,s[i]);
  32.                        
  33.                 if(estado==-1)
  34.                                 break;
  35.                 switch(estado){
  36.                         case 0:
  37.                                 if(flag==0){
  38.                                         res+=atoi(&s[i]);
  39.                                         flag=1;
  40.                                 }
  41.                                
  42.                         break;
  43.                         case 1:
  44.                                 flag=0;
  45.                         break;
  46.                 }
  47.         }
  48.        
  49.         if(estado==0){
  50.                 printf(“aceite!n);
  51.                
  52.                 printf(“A soma ‘e: %dn,(res));
  53.                
  54.         }
  55.         else if(estado==-1)
  56.                 printf(“Expressao mal construida – Nao aceiten);
  57.         else{
  58.                 printf(“Expressao mal construida – Nao aceiten);     
  59.         }
  60. return(0);
  61. }



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>
  9. int delta(int M[3][2],int estado,char ch){
  10.         if (estado==-1)
  11.                 return 1;
  12.         if(ch >=‘0’ && ch <=‘9’)
  13.                 return(M[estado][0]);
  14.         if(ch==‘+’ || ch==‘-‘ || ch==‘*’ || ch==‘/’)
  15.                 return(M[estado][1]);
  16. return (1);
  17. }
  18. int main(){
  19.         int M[3][2]={
  20.                         {0,1},{0,2},{2,2}
  21.                     }; 
  22.         char s[15];
  23.         int estado=0,i,res=0,flag=0;
  24.         char op=‘x’;
  25.        
  26.         printf(“Introduza a String de calculo!n);
  27.         scanf(“%s”,s);
  28.        
  29.        
  30.         for(i=0;i<strlen(s);i++){
  31.                
  32.                 estado=delta(M,estado,s[i]);
  33.                        
  34.                 if(estado==-1)
  35.                                 break;
  36.                 switch(estado){
  37.                         case 0:
  38.                                 if(flag==0){
  39.                                         if(op!=‘x’){                                   
  40.                                                 if(op==‘+’){
  41.                                                         res+=atoi(&s[i]);
  42.                                                         flag=1;
  43.                                                 }
  44.                                                 else if(op==‘-‘){
  45.                                                         res-=atoi(&s[i]);
  46.                                                         flag=1;
  47.                                                 }
  48.                                                 else if(op==‘*’){
  49.                                                         res=(res*atoi(&s[i]));
  50.                                                         flag=1;
  51.                                                 }
  52.                                                 else if(op==‘/’){
  53.                                                         res=(res/atoi(&s[i]));
  54.                                                         flag=1;
  55.                                                 }
  56.                                                
  57.                                         }
  58.                                         else{
  59.                                                 res+=atoi(&s[i]);
  60.                                                 flag=1;
  61.                                         }
  62.                                 }
  63.                                
  64.                         break;
  65.                         case 1:
  66.                                 flag=0;
  67.                                 if(s[i]==‘+’)
  68.                                         op=‘+’;
  69.                                 else if (s[i]==‘-‘)
  70.                                         op=‘-‘;
  71.                                 else if (s[i]==‘/’)
  72.                                         op=‘/’;
  73.                                 else if (s[i]==‘*’)
  74.                                         op=‘*’;
  75.                         break;
  76.                 }
  77.         }
  78.        
  79.         if(estado==0){
  80.                 printf(“aceite!n);
  81.                
  82.                 printf(“O resultado e’: %dn,(res));
  83.                
  84.         }
  85.         else if(estado==-1)
  86.                 printf(“Expressao mal construida – Nao aceiten);
  87.         else{
  88.                 printf(“Expressao mal construida – Nao aceiten);     
  89.         }
  90. return(0);
  91. }