Sua tarefa é escrever um programa em C que lê uma expressão Booleana em Notação Polonesa Reversa (RPN, sigla do nome em Inglês) e gera a tabela verdade para aquela expressão.
A expressão é composta por um conjunto finito de variáveis lógicas (letras 'a' até 'z') e pelos operadores '&' (e-comercial, AND), '|' (barra vertical, OR) e '~' (til, NOT), A expressão termina com um ';' (ponto e vírgula) e tem formatação livre.
Para uma expressão com N variáveis, seu programa deve avaliar a expressão para todos os 2N mintermos. A avaliação da expressão para cada mintermo deve resultar em '1' ou '0'.
Seu programa deve ler a expressão Booleana da entrada padrão, avaliá-la conforme a Notação Polonesa Reversa RPN, e imprimir a tabela verdade na saída padrão.
Em caso de erro (expressão inválida), seu programa deve emitir uma mensagem de erro na saída de erro e terminar. Na media do possível, a mensagem de erro deve apontar o 'local' do erro.
Para testar seu código, use o programa shunt, que lê na entrada padrão uma expressão com operadores infixados e produz na saída padrão a expressão correspondente em RPN. shunt (executável para Linux x86) pode ser obtido com
wget http://www.inf.ufpr.br/roberto/ci067/shuntshunt -v mostra os passos da tradução da expressão infixada para RPN. A precedência nas expressões infixadas (entrada de shunt) é NOT, AND, OR, e pode ser alterada por parênteses.
// saída do shunt para quatro variáveis, sem repetições
// as aspas simples são necessárias para proteger expressão da shell
echo '(a&b) | (c&d);' | shunt
a b & c d & | ;
// saída do shunt para cinco variáveis, sem repetições, veja as aspas simples
echo '((((((( a | b | c&(d|e) ) ) ) ) ) ) );' | ./shunt
a b | c d e | & | ;
// seu programa é chamado rpn2tv -- veja as aspas simples na expressão
echo 'a&b|c&d;' | shunt | rpn2tv
abcd
0000 0
0001 0
0010 0
0011 1
0100 0
...
1110 1
1111 1
// com variáveis repetidas -- veja as aspas simples na expressão
echo 'a&b|b&a;' | shunt | rpn2tv
ab
00 0
01 0
10 0
11 1
Enviar por e-mail para 'rhexsel @ gmail . com' dois arquivos com o código fonte de seu programa, rpn2tv.h e rpn2tv.c.
Primeiro, escreva uma versão do avaliador que aceita expressões cujas variáveis estão num segmento contínuo do alfabeto, tal como {a,b,c,d,e,f} numa expressão com seis variáveis. Esta versão vale 70% da nota.
Isso funcionando, estenda a primeira versão para que o avaliador aceite qualquer subconjunto do alfabeto, tal como {p,q,r,x,y,z} numa expressão com seis variáveis. Esta extensão vale 30% da nota.
Além da corretude (50%), seu código será avaliado quanto à legibilidade (30%, endentação, espaçamento) e quanto à qualidade dos comentários (20%, comentários inteligentes e elucidativos mas não verborrágicos).
Ganha cinco pontos na média quem escrever um avaliador de equivalência entre expressões: dadas duas expressões E1 e E2, o programa retorna '1' se as duas expressões são logicamente equivalentes, ou '0' em caso contrário. E1 e E2 são em RPN.
O separador de expressões é '=' e o programa avalia 'E1=E2'.
O método de avaliação de equivalência deve usar força bruta: para N variáveis, o programa deve executar 2N comparações.
echo 'a b ~ & a ~ b & | = a b & ~ a ~ b ~ & ~ &' | equiv
1