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. }



 

Pedro Tavares

Pedro Tavares is a professional in the field of information security working as an Ethical Hacker/Pentester, Malware Researcher and also a Security Evangelist. He is also a founding member at CSIRT.UBI and Editor-in-Chief 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, exploitation, hacking, IoT and security in Active Directory networks.  He is also Freelance Writer (Infosec. Resources Institute and Cyber Defense Magazine) and developer of the 0xSI_f33d – a feed that compiles phishing and malware campaigns targeting Portuguese citizens. Read more here.