Estruturas de dados
Por: lucasherb • 6/5/2016 • Trabalho acadêmico • 995 Palavras (4 Páginas) • 256 Visualizações
Estruturas de Dados, trabalhos de casa 5, Respostas
1. Carrano, capítulo 5, Exercício 2: Considere a linguagem que o seguinte
gramática define:
<S> = $ | <W> | $ <S>
<W> = abb | um <W> bb
Escreve todas as cadeias que estão no idioma e que contêm sete ou menos
personagens.
$, $$, $$$, $$$$, $$$$$, $$$$$$, $$$$$$$,
abb, $ abb, $$ abb, $$$ abb, $$$$ abb,
aabbbb, $ aabbbb
2. Carrano, capítulo 5, Exercício 7: Considere a gramática a seguir:
<word> = R | <D> | <D> <word> <S>
<D> = Q | P
<S> = 1
Escrever pseudocódigo para uma função recursiva que retorna verdadeiro é uma string é
nesta língua e retorna FALSE caso contrário.
Solução:
isInLanguage (em r: string): boolean {
if (st tem apenas um caractere)
if ((r é R) ou (r é Q) ou (r é P))
return true
outro
return false
outro
if ((primeiro caractere de st é Q ou P)
e (último caractere de st é 1))
voltar isInLanguage (st menos o seu primeiro e
e últimos caracteres)
outro
return false
}
Página 2
3. Carrano Capítulo 6, Exercício 4: A seção "Reconhecendo Cordas em um
Language "descreve um algoritmo de reconhecimento para a linguagem
L = {w $ w: w é uma cadeia possivelmente vazio de outras de US $ personagens, w = reverse (w)}
Implementar este algoritmo.
Solução:
bool isInLanguage (string aString) {
Stack <char> aStack;
int i = 0;
while (aString [i]! = '$') {
aStack.push (ch);
i ++;
} // Enquanto fim
i ++;
while (i <aString.length ()) {
Char stackTop;
Se (aStack.isEmpty ())
return false;
outro{
aStack.pop (stackTop);
if (stackTop == aString [i])
i ++;
outro
return false;
} // End else
} // Enquanto fim
regresso aStack.isEmpty ();
}
4. Carrano Capítulo 6, Exercício 12: Avaliar a seguinte expressão postfix
usando o algoritmo dado neste capítulo. Mostrar o estado da pilha
após cada passo do algoritmo. Consideram-se os seguintes valores para o
identificadores: a = 7; b = 3; c = 12; d = -5; E = 1.
(a) abc + -
Solução: O estado da pilha é dado abaixo de cada personagem depois
ele é processado.
uma
7
b
3
7
c
12
3
7
+
15
7
-
-8
página 3
Portanto, a resposta é -8.
(b) abc-d * +
Solução:
uma
7
b
3
7
c
12
3
7
-
-9
7
d
-5
-9
7
*
45
7
+
52
...