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

  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>
  10. int delta(int M[3][2],int estado,char ch){
  11.         if (estado==-1)
  12.                 return 1;
  13.         if(ch >=‘0’ && ch <=‘9’)
  14.                 return(M[estado][0]);
  15.         if(ch==‘+’)
  16.                 return(M[estado][1]);
  17. return (1);
  18. }
  19. int main(){
  20.         int M[3][2]={
  21.                         {0,1},{0,2},{2,2}
  22.                     }; 
  23.         char s[15];
  24.         int estado=0,i,res=0,flag=0;
  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.                                         res+=atoi(&s[i]);
  40.                                         flag=1;
  41.                                 }
  42.                                
  43.                         break;
  44.                         case 1:
  45.                                 flag=0;
  46.                         break;
  47.                 }
  48.         }
  49.        
  50.         if(estado==0){
  51.                 printf(“aceite!n);
  52.                
  53.                 printf(“A soma ‘e: %dn,(res));
  54.                
  55.         }
  56.         else if(estado==-1)
  57.                 printf(“Expressao mal construida – Nao aceiten);
  58.         else{
  59.                 printf(“Expressao mal construida – Nao aceiten);     
  60.         }
  61. return(0);
  62. }



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



Pedro Tavares is a professional in the field of information security, currently working as IT Security Engineer. He is also a founding member and Pentester at CSIRT.UBI and founder of the security computer blog seguranca-informatica.pt.

In recent years he has invested in the field of information security, exploring and analyzing a wide range of topics, such as pentesting (Kali Linux), malware, hacking, cybersecurity, IoT and security in computer networks.  He is also Freelance Writer.

Read more here.