Reading Time: 8 minutes

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:
http://pastebin.com/1RTdtd3n

  1. /*###################################################
  2. #      Automato Calculadora de Somar                #  
  3. #             Code by Pedro Tavares                 #
  4. #                                                   #
  5. #          web: http://infptavares.blogspot.com     #
  6. #                                                   #
  7. ####################################################*/
  9. #include <stdio.h>
  10. #include <string.h>
  13. int delta(int M[3][2],int estado,char ch){
  15.         if (estado==-1)
  16.                 return –1;
  18.         if(ch >=‘0’ && ch <=‘9’)
  19.                 return(M[estado][0]);
  21.         if(ch==‘+’)
  22.                 return(M[estado][1]);
  23. return (–1);
  24. }
  28. int main(){
  30.         int M[3][2]={
  31.                         {0,1},{0,2},{2,2}
  32.                     }; 
  34.         char s[15];
  35.         int estado=0,i,res=0,flag=0;
  36.        
  38.         printf(“Introduza a String de calculo!n“);
  39.         scanf(“%s”,s);
  40.        
  41.        
  42.         for(i=0;i<strlen(s);i++){
  43.                
  44.                 estado=delta(M,estado,s[i]);
  45.                        
  46.                 if(estado==-1)
  47.                                 break;
  49.                 switch(estado){
  52.                         case 0:
  53.                                 if(flag==0){
  54.                                         res+=atoi(&s[i]);
  55.                                         flag=1;
  56.                                 }
  57.                                
  58.                         break;
  61.                         case 1:
  62.                                 flag=0;
  63.                         break;
  65.                 }
  67.         }
  68.        
  69.         if(estado==0){
  70.                 printf(“aceite!n“);
  71.                
  72.                 printf(“A soma ‘e: %dn“,(res));
  73.                
  74.         }
  75.         else if(estado==-1)
  76.                 printf(“Expressao mal construida – Nao aceiten“);
  77.         else{
  78.                 printf(“Expressao mal construida – Nao aceiten“);     
  79.         }
  83. return(0);
  85. }



Código autómato calculadora:
http://pastebin.com/NKNUFPSm

  1. /*###################################################
  2. #      Automato Calculadora de Somar                #  
  3. #             Code by Pedro Tavares                 #
  4. #                                                   #
  5. #          web: http://infptavares.blogspot.com     #
  6. #                                                   #
  7. ####################################################*/
  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==‘+’ || ch==‘-‘ || ch==‘*’ || 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.         char op=‘x’;
  36.        
  38.         printf(“Introduza a String de calculo!n“);
  39.         scanf(“%s”,s);
  40.        
  41.        
  42.         for(i=0;i<strlen(s);i++){
  43.                
  44.                 estado=delta(M,estado,s[i]);
  45.                        
  46.                 if(estado==-1)
  47.                                 break;
  49.                 switch(estado){
  52.                         case 0:
  53.                                 if(flag==0){
  54.                                         if(op!=‘x’){                                   
  55.                                                 if(op==‘+’){
  56.                                                         res+=atoi(&s[i]);
  57.                                                         flag=1;
  58.                                                 }
  59.                                                 else if(op==‘-‘){
  60.                                                         res-=atoi(&s[i]);
  61.                                                         flag=1;
  62.                                                 }
  63.                                                 else if(op==‘*’){
  64.                                                         res=(res*atoi(&s[i]));
  65.                                                         flag=1;
  66.                                                 }
  67.                                                 else if(op==‘/’){
  68.                                                         res=(res/atoi(&s[i]));
  69.                                                         flag=1;
  70.                                                 }
  71.                                                
  72.                                         }
  73.                                         else{
  74.                                                 res+=atoi(&s[i]);
  75.                                                 flag=1;
  76.                                         }
  77.                                 }
  78.                                
  79.                         break;
  82.                         case 1:
  83.                                 flag=0;
  85.                                 if(s[i]==‘+’)
  86.                                         op=‘+’;
  87.                                 else if (s[i]==‘-‘)
  88.                                         op=‘-‘;
  89.                                 else if (s[i]==‘/’)
  90.                                         op=‘/’;
  91.                                 else if (s[i]==‘*’)
  92.                                         op=‘*’;
  93.                         break;
  95.                 }
  97.         }
  98.        
  99.         if(estado==0){
  100.                 printf(“aceite!n“);
  101.                
  102.                 printf(“O resultado e’: %dn“,(res));
  103.                
  104.         }
  105.         else if(estado==-1)
  106.                 printf(“Expressao mal construida – Nao aceiten“);
  107.         else{
  108.                 printf(“Expressao mal construida – Nao aceiten“);     
  109.         }
  113. return(0);
  115. }