Departamento de Ciência da Computação - IME - USP

MAC2166 Introdução à Computação

Escola Politécnica - Primeiro Semestre de 2015

Prova 3

QUESTÃO 1

Nesta questão considere expressões na forma posfixa como no EP4, porém formada apenas por números inteiros e pelos operadores '+', '-', '*', '/', '%', '^' e '!' (os mesmos operadores do EP4, a menos do operador de atribuição pois não temos variáveis nesta questão).

Uma expressão é bem formada se há operandos para todos os operadores e vice-versa.

Item (a)

Escreva a seguinte função: 

  def verifica(exp):
    ''' (str) -> bool

    Recebe um string exp contendo uma expressão na forma posfixa.
    Retorna True caso exp esteja bem formada e, em caso contrário,
    retorna False.
    '''

Exemplos de execuções da função verifica(): 

  
>>> verifica( '+' )
False

>>> verifica( '12' )
True

>>> verifica( '2 3' )
False

>>> verifica( '1+3' )
False

>>> verifica( '365 18*150+' )
True

>>> verifica( '21    6 +345*789-!!' )
True
\end{verbatim}

SOLUÇÃO 1 

DIGITOS = '0123456789'
BINARIOS = '+-*/%^'
UNARIOS  = '!'

        
def verifica(exp):
    ''' (str) -> bool

    Recebe um string exp contendo uma expressão na forma posfixa.
    Retorna True caso exp esteja bem formada e, em caso contrário,
    retorna False. 
    '''

    # acrecente um espaço no final da expressão para analisar
    # o último token ainda dentro do laço for.
    exp += ' '
    numero_str = '' # para armazenar um número
    topo = 0 # simula o número de operandos na pilha de execução
    
    for car in exp:
        if car in DIGITOS:
            numero_str += car
        else:
            # estávamos contruindo um número?
            if numero_str != '':
                # simule empilhamento do número na pilha de execução
                topo += 1
                numero_str = ''

            if car in BINARIOS:
                # simule desempilhamento de 2 operandos e empilhamento do resultado
                if topo < 2:
                    return False
                topo -= 1
                    
            elif car in UNARIOS:
                # simule desempilhamento de 1 operando e empilhamento do resultado
                if topo < 1:
                    return False

    # mais de um operando na pilha de excução        
    if topo != 1:
        return False
    return True

SOLUÇÃO 2 

def verifica(exp):
    ''' (str) -> bool

    Recebe um string exp contendo uma expressão na forma posfixa.
    Retorna True caso exp esteja bem formada e, em caso contrário,
    retorna False. 
    '''

    n = len(exp)
    topo = 0 # simula o número de operandos na pilha de execução
    i = 0
    while i < n:
        if exp[i] in DIGITOS:
            # simule empilhamento do número
            topo += 1
            
            # pule o número 
            while i < n and exp[i] in DIGITOS:
                i += 1 # vá para o próximo caractere
                
            # volte, pois no final do while i é sempre incrementado    
            i -= 1
            
        elif exp[i] in BINARIOS:
            # simule desempilhamento de 2 operandos e empilhamento do resultado
            if topo < 2:
                return False
            topo -= 1

        elif exp[i] in UNARIOS:
            # simule desempilhamento de 1 operando e empilhamento do resultado
            if topo < 1:
                return False
            
        i += 1 # vá para o próximo caractere
        
    # mais de um operando na pilha de excução?        
    if topo != 1:
        return False
    return True
Item (a)

Escreva um programa (função main()) que permite ao usuário testar várias expressões posfixas como definidas no item anterior, utilizando, obrigatoriamente, a função verifica(). Você pode utilizar a função mesmo que não a tenha escrito. A cada expressão digitada pelo usuário, o programa deve imprimir se ela é válida ou inválida. O programa deve terminar quando o usuário digitar a palavra fim.

Exemplo de execução do programa: 

exp>> !
Inválida

exp>> 1 2 +
Válida

exp>> 00112+765
Inválida

exp>> 210 345678
Inválida

exp>> 00112  4 56  7890+-!*!!!
Válida

exp>> fim
Obrigado por usar o programa

SOLUÇÃO 

PROMPT = 'exp>> '
FIM    = 'fim'

def main():
    exp = input(PROMPT)
    while exp != FIM:
        if verifica(exp):
            print("Válida\n")
        else:
            print("Inválida\n")
        exp = input(PROMPT)

QUESTÃO 2

Considere a seguinte versão simplificada de um jogo de bingo que chamaremos de BIN.

Em um jogo de BIN cada jogador possui uma cartela. Alguns exemplos de cartelas de BIN são mostrados abaixo: 

    Cartela 1:       Cartela 2:        Cartela 3:
     B 3 7 1          B 3 6 2           B 5 0 1
     I 3 8 0          I 4 5 8           I 5 0 1
     N 9 7 5          N 2 6 1           N 7 0 5

Cada linha da cartela, identificadas pelas letras 'B', 'I', e 'N', possui 3 números entre 0 e 9, sem repetição. Note, entretanto, que um número pode se repetir em linhas distintas da cartela.

Em um jogo de BIN, um mestre de cerimônias anuncia uma combinação após a outra sem repetições, como, por exemplo, 'B2', 'I7', |'N4'|, ... Portanto, cada combinação é composta por uma letra que identifica a linha ('B', |'I'|, ou 'N') e um número (entre 0 e 9).

Cada jogador deve marcar na sua cartela as combinações anunciadas que estejam presentes na cartela. Uma cartela é vencedora se todas as suas 9 combinações estiverem marcadas.

Nesta questão você deverá escrever um programa (função main()) que simula um jogo de BIN. Cada cartela deverá ser representada no programa por dicionário nativos do Python. No dicionário as chaves deverão ser as combinações presentes na cartela e o \textbf{valor} associado deverá indicar se a combinação está ou não marcada.

Item (a)

Escreva uma classe Cartela que: