#lang racket

(define (weights n graph) ;retorna todos os custos do nó atual n
   (map third ;pega o terceiro parâmetro de cada parênteses
        (filter (lambda (edge) (equal? n (first edge))) ;procura os parênteses que possuem o primeiro parâmetro igual ao nó passado por parâmetro
                graph)))

(define (kids n graph) ;retorna todos os filhos do nó n passado por parâmetro
   (map second ;pega o terceiro parâmetro de cada parênteses
        (filter (lambda (edge) (equal? n (first edge))) ;procura os parênteses que possuem o primeiro parâmetro igual ao nó passado por parâmetro
                graph)))

(define (next custo lista1 lista2) ;custo é o "x" ou "y" do grafo(lido na fórmula), lista1 será a lista com os todos os custos de um nó(todos os custos de "A" por exemplo, lista2 será a lista com todos filhos de um nó(todos os filhos de "A" por exemplo)
  (cond
    [(or(null? lista1) (null? lista2)) null] ;se uma das listas for null, então não é possível andar no grafo com o custo
    [else(if(equal? custo (first lista1)) (first lista2) (next custo (rest lista1) (rest lista2)))])) ;compara o custo com o primeiro elemento da lista1, caso true retorna o nó de destino usando o custo, senão chama a função next com o restante das listas 1 e 2

(define (acharCaminho custo lista) ;procura se o custo passado por parâmetro existe na lista1 que é uma lista de todos os custos de um nó ("A" por exemplo)
  (cond
    [(null? lista) #f] ;se o nó for folha = não há custos para sair daquele nó, logo o custo passado por parâmetro não será encontrado
    [else(if(equal? custo (first lista)) #t (acharCaminho custo (rest lista)))])) ;se achou o custo, retorna true. Senão, percorre a lista.


(define (proximo destino graph) ;retorna o grafo com o primeiro parênteses possuindo o primeiro parâmetro = destino (Grafo a partir de "B" por exemplo)
  (cond
    [(null? graph) null] ;se o grafo é null, então qualquer grafo seguinte será null
    [else(if(equal? destino (first(map first graph))) graph (proximo destino (rest graph)))])) ;se achou o primeiro elemento = destino, retorna o grafo. Senão, percorre o grafo.

(define (constroiLista n elemento lista) ;constroi uma lista com base no elemento e a quantidade de vezes que aquele elemento vai ser inserido na lista
  (if(= 0 n) lista
     (constroiLista (- n 1) elemento (cons elemento lista))
  ))

(define (pulaParenteses formula custos parenteses falso) ;caso o grafo seja null, verifica se a formula é incompatível
  (cond[(null? finicio) (set! finicio formula)]) ;guarda a formula antes de ser percorrida
  (cond
    [(null? formula) #t] ;caso o grafo e a formula sejam null, são compatíveis
    [else (if (equal? ")" (first formula)) ; ) indica o fim de uma expressão entre ()
              (if(and (< 0 falso) (equal? "U" (first (rest formula)))) ;se não achou um elemento da formula, indicando que ela é falsa, mas achou uma disjunção
                 (analise (rest (rest formula)) inicio custos parenteses) ;verifica se o segundo lado da disjunção é verdadeiro
                 (if (equal? ")" (first (rest formula))) ;caso ainda haja outra expressão entre (), faz a recursão com o restante da formula
                     (pulaParenteses (rest formula) custos parenteses falso)
                     (if (equal? "U" (first (rest formula))) ;caso ache uma disjunção
                        #t ;primeira parte da disjunção é verdadeira, logo a formula e o grafo são compativeis
                        (display finicio)))) ;se não achou nenhum dos casos acima, então há incompatibilidade da formula inicial guardada em finicio
              (if(or (equal? "?" (first formula)) (equal? "U" (first formula))) ;caso seja uma condicional ou disjunção, a fórmula pode ser compatível com o grafo
                 (analise (rest formula) inicio custos parenteses) ;verifica se é compatível
                 (begin
                   (cond[(= 0 falso)(set! finicio formula)]) ;caso ache qualquer elemento diferente de ? e U, é um elemento inválido e guarda o inicio da formula invalida
                   (pulaParenteses (rest formula) custos parenteses (+ 1 falso)))))])) ;faz a recursão com o restante da formula, sabendo que achou um elemento invalido

(define vezes 0) ;quantidade de ( que se anula com a quantidade de )

(define inicio null) ;lista auxiliar que guarda o grafo antes de entrar na expressão entre ()

(define finicio null) ;lista auxiliar que guarda a formula assim que se começa a verificação de compatibilidade dela

(define (analise formula grafo custos parenteses)
  (cond
    [(null? grafo) (if (null? formula) #t (if (null? (rest formula)) (if (equal? ")" (first formula)) #t (display formula)) (if(> vezes 0) (pulaParenteses formula custos parenteses 0) (display formula))))] ;Casos listados para quando o grafo for null: formula null, formula com 1 char, formula faltando fechar parenteses ou formula com parenteses fechados(inválida)
    [(null? formula) (display formula)] ;se o grafo não for null e a formula for null, incompatibilidade
    [(equal? "(" (first formula)) ;caso ache uma expressão entre ()
     (begin
          (cond
            [(= 0 vezes) (set! inicio grafo)]) ;salva o grafo antes de entrar na expressão entre parênteses e vezes guarda o numero de (
          (set! vezes (add1 vezes))
          (if(equal? "(" (first(rest formula))) ; se o char seguinte for outro (, chama analise com o restante da formula em que o primeiro é (
               (analise (rest formula) grafo custos parenteses)
               (if(equal? #t (acharCaminho (first (rest formula)) (weights (first (map first grafo)) grafo))) ;se não for (, procura um caminho no grafo. Caso ache, chama analise com o primeiro elemento da formula sendo o custo verificado e armazena o nó inicial e o custo inicial para o caso de iterações
                  (analise (rest formula) grafo (constroiLista vezes (first (rest formula)) custos) (constroiLista vezes (next (first (rest formula)) (weights (first (map first grafo)) grafo) (kids (first (map first grafo)) grafo)) parenteses)) ;parenteses recebe constroiLista que recebe o estado depois do custo inicial e qtd de parenteses abertos
                  (percorreFormula formula (- vezes 1) 0 custos parenteses))))] ;caso a expressão entre () seja inválida, ainda há chances de ser compatível
    [(equal? ")" (first formula)) ;caso ache o fim da expressão entre ()
     (begin
       (set! vezes (sub1 vezes)) ;vezes diminui até a qtd de ) ser igual a de (
       (if(null? (rest formula)) ;se a formula for um unico char
          (analise (rest formula) grafo (rest custos) (rest parenteses)) ;chama a analise com a formula null e faz o rest de custos e parenteses, deixando ambos com o valor null pois ) será o último da expressão
          (if(equal? "*" (first(rest formula))) ;caso ache uma iteração depois do )
             (if(equal? #t (acharCaminho (first custos) (weights (first (map first grafo)) grafo))) ;procura o caminho armazenado em custos no nó atual do grafo
                (if(equal? (first parenteses) (next (first custos) (weights (first (map first grafo)) grafo) (kids (first (map first grafo)) grafo))) ;verifica se o destino é o mesmo armazenado na lista parenteses
                   (analise (rest(rest formula)) (rest grafo) (rest custos) (rest parenteses)) ;achou a iteração e chama a analise com a formula depois de * e o grafo saindo da iteração
                   (display formula)) ;achou o caminho mas não faz iteração, então é incompatível
                (percorreFormula (rest formula) (- vezes 1) 0 custos parenteses)) ;se o caminho para a iteração não existe, ainda há uma chance da formula ser compatível
             (if(equal? "?" (first(rest formula))) ;se encontra uma condicional depois do ?
                (analise (rest(rest formula)) inicio (rest custos) (rest parenteses)) ;chama analise com a formula depois de ? e retira o primeiro elemento de custos e parenteses
                (analise (rest formula) grafo (rest custos) (rest parenteses))))))] ;não achou nada que torna a fórmula inválida por enquanto, chama a analise com o restante da formula, custos e parenteses
    [(null? (rest formula)) (if(equal? #t (acharCaminho (first formula) (weights (first (map first grafo)) grafo))) (if(null? (kids (next (first formula) (weights (first (map first grafo)) grafo) (kids (first (map first grafo)) grafo)) grafo)) #t (display formula)) (display formula))] ;verifica a última letra da fórmula, se ela é um custo válido e verifica se o nó que se chega a partir do custo é folha. Se for folha, grafo e fórmula são correspondetes.
    [else (if(equal? #t (acharCaminho (first formula) (weights (first (map first grafo)) grafo))) ;verifica se a primeira casa da fórmula atual(muda através da recursão) é um custo válido pro primeiro nó do grafo atual
             (if(equal? ";" (first(rest formula))) ;Se a próxima casa da fórmula é ;
             (analise (rest (rest formula)) (proximo (next (first formula) (weights (first (map first grafo)) grafo) (kids (first (map first grafo)) grafo)) grafo) custos parenteses) ;Seta o inicio da proxima formula para o elemento depois de ; e, o grafo resultante é aquele gerado depois de tomar o caminho com o custo da primeira casa da fórmula atual
             (if(equal? "?" (first(rest formula))) ;Se a próxima casa da fórmula é ?
                (analise (rest (rest formula)) grafo custos parenteses) ;Início da proxima formula é o primeiro elemento depois de ?. Se o inicio da primeira formula é um custo válido, então executará o comando com custo depois de ?, se ele existir no grafo
                (if(equal? "U" (first(rest formula))) ;Se a próxima casa da fórmula é U
                   (analise (rest (rest (rest formula))) (proximo (next (first formula) (weights (first (map first grafo)) grafo) (kids (first (map first grafo)) grafo)) grafo) custos parenteses) ;Se a primeira casa da formula existe, não precisa checar a casa depois de U. O inicio da proxima formula é setado para depois do elemento que se localiza depois de U. O grafo resultante realiza o movimento com o custo da primeira casa da formula.
                   (if(equal? "*" (first(rest formula))) ;Se a próxima casa da fórmula é *
                      (if(equal? (first (map first grafo)) (next (first formula) (weights (first (map first grafo)) grafo) (kids (first (map first grafo)) grafo))) ;Se o primeiro nó do grafo atual possui o custo(primeira casa da fórmula) e se o destino desse caminho é o próprio nó
                         (analise (rest (rest formula)) (rest grafo) custos parenteses) ;Foi checado que a iteração existe, então o inicio da fórmula é o elemento depois de * e o grafo resultante corta o caminho que aponta para o mesmo nó para não ficar preso em um loop
                         (percorreFormula formula (- vezes 1) 0 custos parenteses)) ;Se o custo do primeiro elemento da fórmula não tiver como destino o primeiro nó do grafo atual, então a fórmula e o grafo não são correspondentes
                      (if(equal? ")" (first(rest formula))) ;caso o proximo elemento da formula indique o fim de uma expressão entre ()
                         (analise (rest formula) (proximo (next (first formula) (weights (first (map first grafo)) grafo) (kids (first (map first grafo)) grafo)) grafo) custos parenteses) ;faz a recursão com o restante da formula e percorre o grafo partindo do custo inicial da formula atual
                         (display formula)))))) ;se encontrou algum elemento inválido na fórmula
             (if(equal? "U" (first(rest formula))) ;Se não achou o primeiro elemento da disjunção, checa o segundo elemento
                (if(equal? #t (acharCaminho (first (rest (rest formula))) (weights (first (map first grafo)) grafo))) ;Se o segundo elemento da disjunção for um custo válido para o primeiro nó do grafo atual
                   (analise (rest (rest (rest formula))) (proximo (next (first (rest (rest formula))) (weights (first (map first grafo)) grafo) (kids (first (map first grafo)) grafo)) grafo) custos parenteses) ;A disjunção é válida e o inicio da formula se localiza depois do fim da disjunção e o caminho do segundo custo é feito no grafo atual, gerando um novo grafo
                   (if(equal? "(" (first (rest (rest formula)))) ;caso o segundo elemento da disjunção seja uma expressão entre ()
                      (analise (rest (rest formula)) grafo custos parenteses) ;faz a recursão com a formula depois de U
                      (display formula))) ;Se o segundo custo da disjunção também não existe, o grafo e a fórmula não são correspondentes
                (if(> vezes 0) ;se não tiver U na casa seguinte, pode ser uma expressão entre () que não terminou ainda
                   (percorreFormula formula (- vezes 1) 0 custos parenteses) ;ainda há chance de ser compatível
                   (display formula));Se não fizer parte de uma disjunção, então o grafo e a fórmula não são correspondentes
          ))]))

(define (percorreFormula formula condicao passou custos parenteses) ;sabe-se que uma parte da formula é inválida, percorrendo expressões entre () até chegar na condicao
  (cond
    [(null? formula) (display formula)] ;grafo não é null e formula é, logo incompatibilidade
    [(null? (rest formula)) (if(equal? ")" (first formula)) #t (display formula))] ;se a formula for um unico char, será compativel se indicar o fim de uma expressão entre () e será incompatível caso contrário
    [(= condicao vezes) (if(equal? "U" (first formula)) ;chegou na condicao de parada e verifica se achou uma disjunção
            (percorreFormula (rest formula) condicao 1 custos parenteses) ;procura o proximo elemento depois de U
            (if(equal? "?" (first formula)) ;verifica se achou uma condicional
               (percorreFormula (rest formula) condicao 1 custos parenteses) ;procura o proximo elemento depois de ?
               (if(= 1 passou) ;já achou U ou ?
                  (analise formula inicio null null) ;verifica se a formula pode ser valida
                    (display formula))))] ;formula e grafo incompativeis
    [(equal? "U" (first formula)) ;se o primeiro elemento da formula já indicar disjunção
             (analise (rest formula) inicio null null)] ;verifica se a formula é compativel
    [else (if(equal? ")" (first formula)) ;fim de uma expressão entre ()
            (begin
            (set! vezes (sub1 vezes)) ;diminui a quantidade de (
            (percorreFormula (rest formula) condicao passou custos parenteses)) ;faz a recursão com o restante da formula
            (if(equal? ";" (first (rest formula))) ;verifica se é uma sequencia de valores
               (pulaParenteses formula custos parenteses 1) ;chama BuscaParenteses já encontrando um valor invalido, mas ainda pode ser uma formula compativel
               (percorreFormula (rest formula) condicao passou custos parenteses)))])) ;caso não tenha encontrado nem ) e nem ;, faz a recursão com o restante da formula

(define (percorreCustos custos) ;percorre a lista de custos até chegar ao final dela
  (cond
    [(null? (rest custos)) custos]
    [else (percorreCustos (rest custos))]))

(define (percorreParenteses parenteses) ;percorre a lista de parenteses até chegar no final dela
  (cond
    [(null? (rest parenteses)) parenteses]
    [else (percorreParenteses (rest parenteses))]))

(define (formula str) ;transforma uma string em uma lista
  (map string (string->list str)))


;EXEMPLOS
;DESCOMENTAR UMA LINHA DE FORMULA E UMA LINHA DE GRAFO DE CADA EXEMPLO PARA VER A EXECUÇÃO DE CADA
;RUN E ESCREVER NO CONSOLE (analise x Graph null null) para chamar a função analise que checa se o grafo e a fórmula são compatíveis
;analise RETORNARÁ #t SE FOREM COMPATÍVEIS OU RETORNARÁ O PONTO DE INÍCIO DA DESCOMPATIBILIDADE NA FÓRMULA

;PRIMEIRO EXEMPLO
;(define x (formula "x;y"))
;(define Graph '(("A" "B" "x") ("B" "D" "y")))
;(define Graph '(("A" "B" "x")))
;(define Graph '(("A" "B" "y") ("B" "D" "x")))
;(define Graph '(("A" "B" "x") ("C" "D" "y")))

;SEGUNDO EXEMPLO
;(define x (formula "x?y"))
;(define Graph '(("A" "B" "x") ("A" "C" "y")))
;(define Graph '(("A" "B" "x")))
;(define Graph '(("A" "C" "y")))

;TERCEIRO EXEMPLO
;(define x (formula "x*"))
;(define Graph '(("A" "A" "x")))
;(define Graph '(("A" "B" "x")))
;(define Graph '(("A" "A" "y")))

;QUARTO EXEMPLO
;(define x (formula "xUy"))
;(define Graph '(("A" "B" "x")))
;(define Graph '(("A" "C" "y")))
;(define Graph '(("A" "B" "x") ("A" "C" "y")))
;(define Graph '(("A" "B" "z")))

;QUINTO EXEMPLO
;(define x (formula "(x;y)?z"))
;(define Graph '(("A" "B" "x") ("A" "C" "z") ("B" "C" "y") ))
;(define Graph '(("A" "B" "x") ("A" "C" "z") ))
;(define Graph '(("A" "C" "z") ("B" "C" "y") ))
;(define Graph '(("A" "B" "x") ("B" "C" "y") ))

;SEXTO EXEMPLO
;(define x (formula "(x;y)Uz"))
;(define Graph '(("A" "B" "x") ("A" "C" "z") ("B" "C" "y") ))
;(define Graph '(("A" "B" "x") ("A" "C" "z") ))
;(define Graph '(("A" "C" "z") ("B" "C" "y") ))
;(define Graph '(("A" "B" "x") ("B" "C" "y") ))

;SÉTIMO EXEMPLO
;(define x (formula "(x;y)*"))
;(define Graph '(("A" "B" "x") ("B" "C" "y") ("C" "B" "x")))
;(define Graph '(("A" "B" "x")))
;(define Graph '(("A" "B" "x") ("B" "C" "y")))

;OITAVO EXEMPLO
;(define x (formula "x?(y;z)*"))
;(define Graph '(("A" "B" "x") ("A" "C" "y") ("C" "D" "z") ("D" "C" "y")))
;(define Graph '(("A" "B" "x") ("A" "C" "y") ("C" "D" "z") ("D" "C" "y") ("D" "E" "x")))
;(define Graph '(("A" "C" "y") ("C" "D" "z") ("D" "C" "y")))
;(define Graph '(("A" "B" "x") ("C" "D" "z") ("D" "C" "y")))
;(define Graph '(("A" "B" "x") ("A" "C" "y") ("D" "C" "y")))

;NONO EXEMPLO
;(define x (formula "x?(x;y)*"))
;(define Graph '(("A" "B" "x") ("B" "D" "y") ("D" "B" "x")))
;(define Graph '(("B" "D" "y") ("D" "B" "x")))
;(define Graph '(("A" "B" "x") ("B" "D" "y")))
;(define Graph '(("A" "B" "x") ("D" "B" "x")))

;ÚLTIMO EXEMPLO
;(define Graph '(("A" "B" "x") ("B" "C" "y") ("C" "D" "z")))
;(define x (formula "(w;z;r)U(x;y;z)"))
;(define x (formula "wU(x;y;z)"))
;(define x (formula "wUx"))
;(define x (formula "x;y;z"))