53
edits
Changes
Jump to navigation
Jump to search
no edit summary
=== Notações Infixa, Pré-fixa e Pós-fixa ===
Agora iremos discutir como usar o Maple para trabalhar com as formas infixa, pré-fixa e pós-fixa de expressões aritméticas. Essas formas são discutidas na sessão 8.33 do texto. Especificamente, iremos mostrar como criar uma representação em árvore binária de uma expressão infixa, como usar percursos em pós-ordem e pré-ordem para crias as formas pós-fixa e pré-fixa de expressões, respectivamente, e também como avaliar essas expressões a partir de suas formas pós-fixa e pré-fixa. Para começar essa seção, nós construímos um procedure em Maple que pega uma expressão aritmética infixa e a converte em um uma representação de árvore binária. Essa representação é em árvore binária pode ser percorrida usando os percursos das seções anteriores para formar vários formatos de representação aritmética. Como um exemplo, podemos construir uma árvore binária representando uma expressão infixa, como (3+10)^2 - (100-30)/(5*2), e então executar um percurso em pré-ordem nessa árvore para formar a representação pré-fixa dessa expressão aritmética.
No procedure em Maple que iremos implementearimplementar, consideraremos uma versão modificada da notação infixa, para evitar manipulações complicadas de string que depreciam o verdadeiro problema.
Especificamente, iremos utilizar chaves ao invés dos parênteses normalmente utilizados na notação infixa.
Adicionalmente, iremos definir nossos operadores em termos de suas representações em string: + para adição, - para subtração e assim vai.
Dessa maneira, as facilidades de manipulação de lista do Maple ficam imediatamente disponíveis. Então, nós representamos expressões x + y as como [x,"+",y] , onde + é uma string.
Procedures do Maple podem ser usados para ajudar-nos a construir tais listas. Por exemplo,
O Maple manipula os nomes de procedures da forma ... como operadores infixos. O procedure que Unique tem é definido especialmente para as rotinas usadas nesse artigo.
O resultado é uma lista incluindo versões especialmente encodadas codificadas da string + , que não colide com usos anteriores de + como nome. (Cada vértice da expressão árvore deve ter um nome diferente, mesmo que eles pareçam iguais).
Similarmente, usamos
O resultado é uma lista aninhada de listas, com cada lista representando uma operação binária.
Agora estamos prontos para construir uma árvore binária representando tal expressão. O algoritmo necessário para isso em pseudocódigo é:
1. Se houver uma expressão algébrica isolada (como um nome ou número), a árvore consiste de um vértice isolado.
2. Caso contrário, a lista consiste de um operando a à esquerda, um operador , e um operando a à direita. Use o algoritmo para construir a árvore binária para o operando a à esquerda.
3. Repita o passo (2) no operando a à direita.
4. Combina os resultados dos passos (2) e (3) para formar a árvore binária.
Nossa implementação é a seguinteesta:
<pre>
</pre>
Se não tivermos sublistas em nossa expressão, retorne as listas de arestas e vértices como mostrado
<pre>
</pre>
A raiz da árvore é manipulada de maneira especial. Recomputando Recomputar a raiz da árvore é estranho complicado e carotaxativo, então nós simplesmente pedimos a cada árvore que se lembre de sua própria raiz. Isso é feito por declarações de tarefa como T(Root) := LocL;.
O procedure Unique é novamente usado para se assegurar que cada instancia de vértice tem nome único, mesmo que pareça igual a outro. Em todos os outros aspectos, a implementação é quase exatamente como descrito no pseudocódigo.
Para testar esse procedure, use-o para construir uma árvore de expressão árvore para a expressão anterior Expr1.
<pre>
</pre>
Suponha que somos dados uma representação em árvore binária de uma expressão aritmética. Nós podemos usar os algoritmos anteriormente criados para expressas essas árvores como expressões pós-fixas ou pré-fixas executando os percursos de pós-ordem ou pré-ordem, respectivamente. Como isso é trivial, cabe ao leitor explorar essa técnica.Como um exemplo final dessa seção, nós demonstramos como avaliar uma dada expressão pós-fixa. Para simplificar, nós representamos as operações básicas pelas primeiras letras das palavras add, subtract, multiply, divide e exponentiate. cabe Cabe ao leitor explorar como implementar um procedure que irá avaliar uma expressão pré-fixa, dado que essa técnica é a simples modificação do argumento que será usado no caso pós-fixo.
<pre>
</pre>
Note que em release 4, nós somos permitidos atribuir diretamente a à lista elements.
== Árvores e Ordenação ==
