Uma sequência de operações inserção (I) e eliminação (E) numa pilha é dita válida se ela tem igual número de Is e Es e todas as operações podem ser efetuadas na pilha, ou seja, a eliminação só pode acontecer se a pilha não estiver vazia. Formule uma regra que permita determinar se uma sequência (ex: IIEE) é válida ou não.

Passo 1

O enunciado pede uma condição para decidir se uma sequência de operações na pilha é válida, onde “I” representa push e “E” representa pop, sabendo que não podemos desempilhar de uma pilha vazia e que no fim devemos ter empilhado e desempilhado o mesmo número de vezes.

Passo 2

Para facilitar, a gente faz uma analogia com parênteses: trate cada “I” como “(” e cada “E” como “)”. A validade passa a ser a mesma de uma palavra bem formada de parênteses.

Passo 3

Definimos uma variável chamada balance iniciada em zero. Ao ler cada símbolo da sequência, fazemos: se for “I”, incrementamos balance; se for “E”, decrementamos balance. Se em algum momento balance ficar negativo, significa que houve um pop em pilha vazia, então a sequência é inválida.

Passo 4

No final da leitura, se balance for exatamente zero (ou seja, tivemos igual número de “I” e “E”), e nunca ficou negativo durante o processo, então a sequência é válida. Caso contrário, é inválida.

Resposta

Uma sequência S de I’s e E’s é válida se e somente se, para todo prefixo S’ de S, o número de “I” em S’ for sempre maior ou igual ao número de “E” em S’ (nunca desempilhar pilha vazia) e, ao final, o total de “I” for igual ao total de “E” (balance final = 0).

Exercícios relacionados