Contato

• Jean Paulo Martins (jeanmartins utfpr edu br)
• Sala 105, Bloco S (UTFPR - Campus Pato Branco)

Conteúdo

• Exercícios
  • Validação parentética
  • Validação de expressões
  • Verificação de palíndromo
  • Verificar concatenação de palíndromos
  • Underflow
• Referências -pdf

Exercícios

Validação parentética

Agora que defimos uma pilha e indicamos as operações que podem ser executadas sobre ela, vejamos como podemos usar a pilha na solução de problemas. Examine uma expressão matemática que inclui vários conjuntos de parênteses agrupados. Por exemplo:

Queremos garantir que os parênteses estejam corretamente agrupados, ou seja, desejamos verificar se:

1. Existe um número igual de parênteses esquerdos e direitos.
2. Todo parêntese da direita está precedido por um parêntese da esquerda.

#include "stack.h"
// Funções auxiliares para identificar o caractere sendo lido. 
// [!] É necessário implementá-las para que o exemplo funcione. 
bool abreEscopo(char c);
bool fechaEscopo(char c);
bool escopoCorreto(char a, char b);
int verificaExpressao(const char* expressao, int esize) {
	stack* p = new_stack();	
	for (int i = 0; i < esize; ++i) {
		char atual = expressao[i];
		if ( abreEscopo(atual) ) {
			stack_push(p, atual);
		} else if ( fechaEscopo(atual) ) {
			if (stack_empty(p)) return i;
			if ( !escopoCorreto(stack_pop(p), atual) ) return i;
		}
	}	
	if (!stack_empty(p)) return esize;
	free_stack(p);
	return esize+1;
}

Validação de expressões

Adapte o código do validador para que funcione com expressões mais complexas, contendo os demais delimitadores

Verificação de palíndromo

Escreva um algoritmo para determinar se uma string de caracteres de entrada é da forma:

onde $x,y$ são strings e $y$ é o inverso de $x$. O caractere $C$ delimita o fim de $x$. Somente um caractere da string pode ser lido de cada vez.

Verificar concatenação de palíndromos

Escreva um algoritmo para determinar se uma string de caracteres de entrada é da forma:

onde cada string $a, b, c,\dots,z$, é da forma da string definida no exercício anterior, isto é, $a = xCy$

Underflow

Que conjunto de critérios é necessário e suficiente para que uma sequência de operações push e pop sobre uma única pilha (inicialmente vazia) deixe a pilha vazia e não provoque underflow?

Referências -pdf