Agradeço comentários, sugestões ou correcções. O meu endereço de correio electrónico é < delfim@mat.ua.pt > . Desde já obrigado.
Um dos conceitos mais úteis em ciências da computação, é o conceito de pilha. Uma pilha é uma coleção ordenada de dados, na qual os dados podem ser inseridos e retirados apenas de uma das extremidades. A essa extremidade chamamos topo da pilha. Neste capítulo fazemos uso desta estrutura de dados que, em Prolog, é trivialmente implementada por uma lista.
Consideremos a soma de A e B, que representamos usualmente por A+B. Esta representação particular é chamada de infixa. Existem contudo duas notações alternativas. Estas são
| |||||||||||||
Na notação préfixa o operador precede os operandos enquanto na pósfixa o operador vem depois dos operandos. As notações préfixa e pósfixa não são tão inusuais como podem parecer à primeira vista. Por exemplo, se estivermos a usar um predicado Prolog para a soma de dois argumentos A e B, invocamos qualquer coisa como soma(A,B,R). O operador soma precede os operandos A e B!
O cálculo da expressão A+B*C, escrita na notação usual, infixa, requer conhecimento de qual das duas operações, + ou *, deve ser realizada em primeiro lugar: ``sabemos'' que a multiplicação deve ser feita antes da adição. Assim A+B*C é interpretado como A+( B*C) . Dizemos que a multiplicação tem precedência sobre a adição. Suponhamos que queremos escrever A+B*C na notação pósfixa. Aplicando as regras de precedência, convertemos em primeiro lugar a porção da expressão que é calculada em primeiro lugar: a multiplicação. Fazendo esta conversão por etapas obtemos:
| |||||||||||||||
As únicas regras a lembrar, durante o processo de conversão, é que as operações com maior precedência são convertidas em primeiro lugar; e que depois de uma porção da expressão ter sido convertida para a notação pósfixa, ela é tratada como um único operando. Consideremos o mesmo exemplo com a precedência dos operadores invertida pelo uso deliberado de parêntesis:
| |||||||||||||||
As regras para a conversão da notação infixa para pósfixa são simples, desde que saibamos à priori a ordem de precedência dos vários operadores.
Consideramos, nos exemplos que se seguem, cinco operações binárias: adição, subtracção, multiplicação, divisão e exponenciação que representaremos respectivamente pelos símbolos +, -, *, / e \symbol94. O valor da expressão A\symbol94B é A levantado a B, de tal modo que 3\symbol942 é 9. Para estas operações temos a seguinte ordem de precedência (maior para menor):
| ||||||||||||||||||
Usando parêntesis, podemos mudar as precedências por defeito. Damos os seguintes exemplos adicionais de conversão infixa para pósfixa. Avancem apenas quando os conseguirem fazer por voçês próprios. Notar que, na ausência de parêntesis, os operadores da mesma precedência são considerados da esquerda para a direita, com a única excepção da exponenciação onde a ordem é assumida como da direita para a esquerda. Assim, A+B+C significa (A+B) +C enquanto A\symbol94B\symbol94C significa A\symbol94 ( B\symbol94C) .
| ||||||||||||||||||||||||
Notar que na notação pósfixa de uma expressão não há parêntesis: a ordem dos operadores na forma pósfixa determina a ordem das operações no cálculo do valor das expressões. Perdemos assim a capacidade de notar de imediato que operandos estão associados com um particular operador, mas ganhamos uma forma não ambígua sem o uso incómodo de parêntesis.
Pretendemos ter um método que nos permita concluir, por exemplo, que 3 4 5*+ = 23 e 3 4+5* = 35. Por outras palavras, desejamos um algoritmo para o cálculo de expressões pósfixas.
Cada operador numa ``string'' pósfixa deve ser aplicado aos operandos que imediatamente lhe antecedem. Esses operandos podem por sua vez resultar da aplicação de um ou mais operadores. Suponhamos que, de cada vez que lemos um operando, fazemos push desse operando para uma pilha. Quando chegarmos a um operador, os seus operandos estarão no topo da pilha: fazemos um número de pop's correspondente ao número de argumentos do operador em questão. Depois de efectuada a operação, fazemos push do resultado para a pilha, de modo a que ele esteja disponível para uso como operando do próximo operador. Vamos ilustrar este algoritmo com o exemplo 6 2 3+-3 8 2 /+* 2\symbol943+
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Vamos agora apresentar um algoritmo para converter uma expressão infixa numa pósfixa.
Já vimos que as subexpressões dentro dos parêntesis mais interiores, devem ser convertidas para a notação pósfixa em primeiro lugar, de modo a puderem ser tratadas como operandos. Deste modo, os parêntesis podem ser sucessivamente eliminados até toda a expressão ser convertida. O último par de parêntesis a ser aberto dentro de um grupo de parêntesis, contém a primeira subexpressão dentro desse grupo a ser transformada. Este comportamento sugere imediatamente o uso de uma pilha.
Consideremos as duas expressões infixas A+B*C e (A+B)*C e as correspondentes versões pósfixas A B C*+ e A B+C*. Em cada um dos casos a ordem dos operandos é a mesma que na expressão original infixa. Ao ``varrermos'' a primeira expressão, A+B*C, o primeiro operando A pode ser imediatamente inserido na expressão pósfixa. Óbviamente, o símbolo + não pode ser inserido até ao seu segundo operando, que ainda não foi lido, ser inserido. Por conseguinte, temos de o armazenar à parte (numa pilha) para mais tarde inseri-lo na sua posição correcta. Quando o operando B é lido, ele é inserido imediatamente após o A. Agora, contudo, dois operandos foram lidos. O que impede o símbolo +, armazenado na pilha, de ser inserido? A resposta é, como resulta claro, o facto do símbolo * que se segue ter precedência sobre o +. (No caso da segunda expressão os parêntesis indicam que a operação + deve ser realizada em primeiro lugar.) Lembrar que na notação pósfixa o operador que aparece mais cedo na string é a que a deve ser aplicada em primeiro lugar.
Vamos assumir a existência de um predicado prcd(Op1,Op2) que nos indica que Op1 tem precedência sobre Op2 quando Op1 nos aparece à esquerda de Op2 numa expressão infixa sem parêntesis. Por exemplo prcd(*,+) e prcd(+,+) devem constar da BC enquanto prcd(+,*) não! Assim, na ausência de parêntesis, o nosso algoritmo de conversão infixa- > pósfixa pode ser descrito nos seguintes termos: vamos lendo os símbolos da expressão infixa. Sempre que o símbolo é um operando coloca-mo-lo de imediato na expressão pósfixa. No caso de um operador das duas uma: ou existe um operador no topo da pilha (que no início está vazia) com precedência sobre ele: caso em que retiramos o operador do topo da pilha para a expressão pósfixa; ou não: neste caso não podemos colocar o operador na expressão pósfixa até termos lido o próximo operador, que poderá ter precedência. Coloca-mo-lo então na pilha. Quando acabarmos de ler toda a expressão infixa, resta-nos retirar todos os operadores que restam na pilha para a expressão pósfixa.
Propomos que simulem o algoritmo acima para as expressões infixas 2*3+4*5 e 1+2*2\symbol943\symbol942 (onde o símbolo \symbol94 representa a exponenciação e prcd(\symbol94,\symbol94) não deve constar da base de conhecimento!) para se convencerem que ele está correcto. Notar que em cada ponto da simulação, um operador na Pilha tem uma precedência inferior em relação a todos os operadores abaixo dele. Isto é verdade porque a pilha inicialmente está vazia (o que trivialmente satisfaz a condição) e sempre que é feito ``push'' de um operador, isso significa que o operador correntemente no topo da pilha tem precedência inferior em relação ao operador a vir para a pilha.
Falta-nos responder à seguinte questão: que modificações devem ser feitas ao algoritmo para podermos lidar com parêntesis? A resposta é animadora: pouco! Sempre que um parêntesis é aberto, ele deve ser colocado no topo da pilha. Isto pode ser conseguido de um modo automático pelo nosso algoritmo se encararmos '(' como um operador.
Quando um parêntesis ')' é lido, todos os operadores até ao primeiro '(' devem ser retirados do topo da pilha para a expressão pósfixa. Isto pode ser conseguido colocando na base de conhecimento prcd(Op,')') para todos os operadores Op que não o '('. Quando estes operadores tiverem sido retirados da pilha devemos ter o cuidado de retirar o parêntesis '(' e desprezá-lo conjuntamente com o seu par ')' (não devemos colocá-los na expressão pósfixa!).
|
| |||||||||||||||||||||||||||||||||||||||||||
|
| ||||||||||||||||||||||||||||||||||||||||||||||||
|
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Delfim F. Marado Torres
% Ultima Alteracao: 21/Abril/1999
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Opera,c~oes sobre listas
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% primeiros(N,Lista,Primeiros_N_da_Lista,Resto_da_Lista)
primeiros(0,L,[],L).
primeiros(N,[X|L],[X|R],Sobra) :-
N1 is N - 1,
primeiros(N1,L,R,Sobra).
concatena([],L,L).
concatena([X|R],L,[X|C]) :-
concatena(R,L,C).
inverte([],[]).
inverte([X|L],I) :-
inverte(L,LI),
concatena(LI,[X],I).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Opera,c~oes matem'aticas. O primeiro argumento
% corresponde sempre ao resultado
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%mais/3
mais(R,X,Y) :- R is X + Y.
%menos/3
menos(R,X,Y) :- R is X - Y.
%vezes/3
vezes(R,X,Y) :- R is X * Y.
%dividir/3
dividir(R,X,Y) :- R is X / Y.
%pow/3
pow(1,_,0).
pow(R,X,N) :-
N1 is N - 1,
pow(R1,X,N1),
R is X * R1.
%factorial/2
factorial(1,0).
factorial(F,N) :-
N1 is N - 1,
factorial(F1,N1),
F is N * F1.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Tabela de correspond^encia s'imbolos -> predicados
%
% tabela(Simbolo,Nome_Predicado,Aridade_Predicado)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
tabela(+,mais,3).
tabela(-,menos,3).
tabela(*,vezes,3).
tabela(/,dividir,3).
tabela(^,pow,3).
tabela(!,factorial,2).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Tabela de preced^encias
%
% prcd(Op1,Op2) significa que Op1 tem preced^encia sobre Op2
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
prcd(+,+).
prcd(-,-).
prcd(*,*).
prcd(/,/).
prcd(*,+).
prcd(/,+).
prcd(*,-).
prcd(/,-).
prcd(^,*).
prcd(^,/).
prcd(^,+).
prcd(^,-).
prcd(!,*).
prcd(!,/).
prcd(!,+).
prcd(!,-).
prcd(!,^).
prcd(Op,')') :-
tabela(Op,_,_).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% C'alculo do valor de express~oes num'ericas na nota,c~ao postfix
%
% Exemplos:
% ?- postfix([2,3,5,*,+],Valor).
% Valor = 17
%
% ?- postfix([6,2,3,+,-,3,8,2,/,+,*,2,^,3,+],Valor).
% Valor = 52
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
postfix(L,V) :-
calcula_postfix(L,V,[]). % No in'icio a pilha est'a vazia
calcula_postfix([],V,[V]). % Quando a express~ao acabou, o resultado
% 'e o 'unico elemento da pilha.
calcula_postfix([S|R],V,P) :-
number(S),
calcula_postfix(R,V,[S|P]). % Faz push para a pilha
calcula_postfix([S|R],V,P) :-
tabela(S,Op,Ar), % Se n~ao 'e n'umero 'e operador
N is Ar - 1,
primeiros(N,P,Nums,RP),
inverte(Nums,Numeros),
C =.. [Op,Res|Numeros],
call(C),
calcula_postfix(R,V,[Res|RP]).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Convers~ao de uma express~ao em infix para postfix
%
% Exemplos:
%
% ?- infix_to_postfix([1,+,2,*,3],P).
% P = [1,2,3,*,+]
%
% ?- infix_to_postfix(['(',1,+,2,')',*,3],P).
% P = [1,2,+,3,*]
%
% ?- infix_to_postfix(['(','(',1,-,'(',2,+,3,')',')',*,4,')',^,'(',5,+,6,')'],P).
% P = [1,2,3,+,-,4,*,5,6,+,^]
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
infix_to_postfix(I,PF) :-
inf_to_post(I,[],[],PF).
inf_to_post([],S,P,PF) :-
inverte(S,SI),
concatena(SI,P,PF).
inf_to_post([X|I],S,P,PF) :-
number(X),
inf_to_post(I,[X|S],P,PF).
inf_to_post(I,S,[')'|P],PF) :-
inf_to_post(I,S,P,PF).
inf_to_post([X|I],S,[Y|P],PF) :-
prcd(Y,X),
inf_to_post([X|I],[Y|S],P,PF).
inf_to_post([')'|I],S,[_|P],PF) :-
inf_to_post(I,S,P,PF).
inf_to_post([X|I],S,P,PF) :-
inf_to_post(I,S,[X|P],PF).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Convers~ao de uma string para uma lista
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
str_list(S,L) :-
name(S,LA),
converte(LA,L).
converte([],[]).
converte([32|CA],C) :- % despreza espa,cos
converte(CA,C).
converte([XA|CA],[X|C]) :-
name(X,[XA]),
converte(CA,C).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% PREDICADO PRINCIPAL %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% C'alculo do valor de express~oes
%
% Exemplos:
% ?- valor('((1 - (2+3))*4)^5 + 3!',V).
% V = -1048570
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
valor(String,Val) :-
str_list(String,Exp),
infix_to_postfix(Exp,ExpPost),
postfix(ExpPost,Val), !.