Autómato Soma (Calculadora) – C

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

Pedro Tavares

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.