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
- /*###################################################
- # Automato Calculadora de Somar #
- # Code by Pedro Tavares #
- # #
- # web: http://infptavares.blogspot.com #
- # #
- ####################################################*/
- #include <stdio.h>
- #include <string.h>
- int delta(int M[3][2],int estado,char ch){
- if (estado==-1)
- return –1;
- if(ch >=‘0’ && ch <=‘9’)
- return(M[estado][0]);
- if(ch==‘+’)
- return(M[estado][1]);
- return (–1);
- }
- int main(){
- int M[3][2]={
- {0,1},{0,2},{2,2}
- };
- char s[15];
- int estado=0,i,res=0,flag=0;
- printf(“Introduza a String de calculo!n“);
- scanf(“%s”,s);
- for(i=0;i<strlen(s);i++){
- estado=delta(M,estado,s[i]);
- if(estado==-1)
- break;
- switch(estado){
- case 0:
- if(flag==0){
- res+=atoi(&s[i]);
- flag=1;
- }
- break;
- case 1:
- flag=0;
- break;
- }
- }
- if(estado==0){
- printf(“aceite!n“);
- printf(“A soma ‘e: %dn“,(res));
- }
- else if(estado==-1)
- printf(“Expressao mal construida – Nao aceiten“);
- else{
- printf(“Expressao mal construida – Nao aceiten“);
- }
- return(0);
- }
Código autómato calculadora:
http://pastebin.com/NKNUFPSm
- /*###################################################
- # Automato Calculadora de Somar #
- # Code by Pedro Tavares #
- # #
- # web: http://infptavares.blogspot.com #
- # #
- ####################################################*/
- #include <stdio.h>
- #include <string.h>
- int delta(int M[3][2],int estado,char ch){
- if (estado==-1)
- return –1;
- if(ch >=‘0’ && ch <=‘9’)
- return(M[estado][0]);
- if(ch==‘+’ || ch==‘-‘ || ch==‘*’ || ch==‘/’)
- return(M[estado][1]);
- return (–1);
- }
- int main(){
- int M[3][2]={
- {0,1},{0,2},{2,2}
- };
- char s[15];
- int estado=0,i,res=0,flag=0;
- char op=‘x’;
- printf(“Introduza a String de calculo!n“);
- scanf(“%s”,s);
- for(i=0;i<strlen(s);i++){
- estado=delta(M,estado,s[i]);
- if(estado==-1)
- break;
- switch(estado){
- case 0:
- if(flag==0){
- if(op!=‘x’){
- if(op==‘+’){
- res+=atoi(&s[i]);
- flag=1;
- }
- else if(op==‘-‘){
- res-=atoi(&s[i]);
- flag=1;
- }
- else if(op==‘*’){
- res=(res*atoi(&s[i]));
- flag=1;
- }
- else if(op==‘/’){
- res=(res/atoi(&s[i]));
- flag=1;
- }
- }
- else{
- res+=atoi(&s[i]);
- flag=1;
- }
- }
- break;
- case 1:
- flag=0;
- if(s[i]==‘+’)
- op=‘+’;
- else if (s[i]==‘-‘)
- op=‘-‘;
- else if (s[i]==‘/’)
- op=‘/’;
- else if (s[i]==‘*’)
- op=‘*’;
- break;
- }
- }
- if(estado==0){
- printf(“aceite!n“);
- printf(“O resultado e’: %dn“,(res));
- }
- else if(estado==-1)
- printf(“Expressao mal construida – Nao aceiten“);
- else{
- printf(“Expressao mal construida – Nao aceiten“);
- }
- return(0);
- }
Pedro Tavares is a professional in the field of information security, working as an Ethical Hacker, Malware Analyst, Cybersecurity Analyst 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, hacking, cybersecurity, IoT and security in computer networks. He is also Freelance Writer.
Read more here.