-
Notifications
You must be signed in to change notification settings - Fork 0
/
main.rkt
125 lines (106 loc) · 6.24 KB
/
main.rkt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
#lang racket
#| -----------------------------------------------------Programa e grafo------------------------------------------------------ |#
;Recebe o programa.
(define programa (list"(" "|" 1 ";" 2 ")" "U" "(" "||" 3 ";" 4 ";" "E" ")"))
;Recebe o grafo.
(define grafo (list 1 "(" "I" "a" ")" 2 "(" "a" "b" ")" 3 "(" "I" "c" ")" 4 "(" "c" "d" ")" "X" "X" "X"))
#| ----------------------------------------------------------Funcoes---------------------------------------------------------- |#
#| Le um programa e retorna todos os pares ordenados com as possiveis transições do programa. Onde:
* 'anteriorS' eh o simbolo anterior;
* 'anterior' eh o numero (programa) anterior;
* 'relacoes' eh a lista com as possiveis transicoes do programa;
* 'anteriorU' eh o simbolo ou programa anterior dentro da uniao atual;
* 'fimU1'/'fimU2' representam os finais de respectivamente primeiro e segundo termos da uniao atual;
* 'pares-uniao' representa uma lista com todos os pares associados por uma uniao (U). |#
(define (processar-programa entrada anterior anteriorS relacoes anteriorU fimU1 fimU2 pares-uniao)
;(printf "Ant: ~a - AntS: ~a - Rel.: ~a - AntU: ~a - FimU1: ~a - FimU2: ~a - Uniao: ~a\n" anterior anteriorS relacoes anteriorU fimU1 fimU2 pares-uniao)
(define item (first entrada))
;Verifica se o item atual da lista é um numero, se for faz um par ordenado dele com o anterior e salva ele no anterior
(cond [(number? item)
(cond [(equal? anteriorS "||") (set! relacoes (append relacoes(list (list anteriorU item))))
(set! anterior item)]
[(equal? anteriorS "B") (set! relacoes (append relacoes(list (list fimU1 item))))
(set! relacoes (append relacoes(list (list fimU2 item))))
(set! anterior item)]
[else (set! relacoes (append relacoes(list (list anterior item))))
(set! anterior item)])]
;Se nao for um numero:
[else
;verifica se eh o caracter uniao
(cond [(equal? item "|") (set! anteriorU anterior)])
(cond [(equal? item "U") (set! fimU1 anterior)])
(cond [(equal? item "E") (set! fimU2 anterior)])
;verifica se eh o caracter *
(cond [(equal? item "*")
;verifica se o caracter * vem depois de um ), se nao, adiciona uma transicao do anterior pra o anterior
(cond [(equal? anteriorS ")") (set! anteriorS item)]
[else (set! relacoes(append relacoes(list(list anterior anterior))))])])
(set! anteriorS item)])
;verifica se o programa esta vazio, ou seja, foi todo percorrrido, se sim entao retorna, se nao chama a proxima instancia para a tail
(cond[(empty? (rest entrada)) relacoes]
[else (processar-programa (rest entrada) anterior anteriorS relacoes anteriorU fimU1 fimU2 pares-uniao)]))
; Cria a matriz de incidencia do grafo.
(define (criar-matriz-grafo grafo gt grafof result)
(define vf 0)
(define final "")
(set! vf (first grafo))
(set! final (first(rest(rest(rest grafo)))))
(set! result (append result(processar-grafo grafof gt vf 0 final "")))
(cond [(equal? (first(rest(rest(rest(rest(rest grafo)))))) "X") result]
[else (criar-matriz-grafo (rest(rest(rest(rest(rest grafo))))) gt grafof result)]))
; Inicia o processamento do grafo de entrada dado.
(define (processar-grafo grafo gt vf vi final inicial)
(cond[(empty? grafo) gt]
[else (cond [(number? (first grafo)) (set! vi (first grafo))
(set! inicial (first (rest(rest grafo))))
(cond[(equal? final inicial)
(set! gt (append gt (list(list vf vi))))])])
(processar-grafo (rest grafo) gt vf vi final inicial)]))
; Elimina da matriz de incidencia do grafo as ocorrencias do simbolo 'I'.
(define (eliminar-I mtz-prog resp)
(cond[(empty? mtz-prog) resp]
[else
(cond[(equal? (first(first mtz-prog)) "I")]
[else (set! resp(append resp(list (first mtz-prog))))])
(eliminar-I (rest mtz-prog) resp)]))
; Elimina os pares iguais existentes na matriz do grafo. Recebe a matriz de incidencia do grafo.
(define (eliminar-iguais mtz-graf resp)
(cond[(empty? mtz-graf) resp]
[else
(cond[(equal? (busca (first mtz-graf) resp 1) 0)]
[else (set! resp(append resp(list (first mtz-graf))))])
(eliminar-iguais (rest mtz-graf) resp)]))
; Verifica se um grafo eh modelo de um programa. Recebe as matrizes de incidencia correspondentes a ambos e as compara utilizando funcoes auxiliares.
(define (eh-modelo? mtz-prog mtz-graf)
(cond[(equal? (length mtz-prog) (length mtz-graf))
(eh-modelo-aux? mtz-prog mtz-graf)]
[else "false"]))
; Busca todos os pares da matriz de incidencia do programa na matriz de incidencia do grafo. Usada para verificar se o grafo
; eh modelo do programa (usada pelas funcoes 'eh-modelo?').
(define (busca origem destino resp)
(cond[(empty? destino) resp]
[else
(cond[(equal? (first origem) (first(first destino)))
(cond[(equal? (first(rest origem)) (first(rest(first destino))))(set! resp 0)]
)])
(busca origem (rest destino) resp)]))
; Funcao auxiliar de eh-'modelo'?. Executa a funcao de busca para cada par da matriz do programa.
(define (eh-modelo-aux? mtz-prog mtz-graf)
(cond[(empty? mtz-prog)
"true"]
[else (cond [(equal? (busca (first mtz-prog) mtz-graf 1) 0)
(eh-modelo-aux? (rest mtz-prog) mtz-graf)]
[else "false"])]))
#| ---------------------------------------------------------Execucao---------------------------------------------------------- |#
; Inicializacao de variaveis do relacionada as relacoes do programa, grafo e suas matrizes correspondentes.
;Cria a lista de relacoes.
(define relacoes (list ))
(define gt (list ))
(define result (list ))
(set! relacoes(processar-programa programa "I" "" relacoes "I" "" "" '()))
(set! result (criar-matriz-grafo grafo gt grafo result))
(define mtz-programa (eliminar-I relacoes (list )))
(define mtz-grafo (eliminar-iguais result (list )))
(printf "Programa -> ~a\n" programa)
(printf "Grafo -> ~a\n" grafo)
(printf "Grafo eh modelo do programa? ~a\n" (eh-modelo? mtz-programa mtz-grafo))