Ir para o conteúdo
leia

arvores

Mensagens Recomendadas

leia

Boa noite,

Agradecia se houver alguém que me desse umas luzes de como posso definir um tipo capaz de representar expressões aritméticas sob forma de uma arvore.Por exemplo esta arvore pode conter operadores unários : soma, substração, multiplicação, divisão e expoente.operadores binários: menos unário, seno e coseno.As folhas podem conter valores numericos ou variáveis, a variável é caracterisada pelo seu nome(String ).

Ando as voltas com isso .... e não consegui fazer :confused::( :(

Agradeço desde já!!

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
leia

O pior e que não sei por onde começar e queria umas sugestões para fazer algo e mostrar que fiz

Agradecia um pequeno exemplo que fosse para eu a partir disso desenvolver o resto.

Editado por leia

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
Kimio

Sugiro que cries um novo tipo de dado, chamado Expr por exemplo, usando Algebraic Data Types. E um Expr pode ser uma de 4 alternativas:

1. Uma simples constante do tipo Double

2. Um operador unário e um Expr como argumento

3. Um operador binário e dois Exprs como argumentos

4. Uma variável com o seu nome do tipo String... (e um Expr como valor? Não é claro pela descrição, como se determina atribui valores às variáveis)

Editado por Kimio
  • Voto 1

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
Rui Carlos

Já agora, se ainda não souberes definir árvores em Haskell, tens vários exemplos aqui no fórum que podes encontrar através da pesquisa: 1, 2, 3, 4, 5 (são exemplos de árvores binárias; as que precisas são um pouco mais complexas).

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
thoga31

Já devia estar mesmo a dormir... Either? No que estava eu a pensar? LOL :D

@leia, os exemplos dados pelo @Rui Carlos são o ponto de partida para definires um tipo de dados que te seja útil ao teu problema. Qualquer dúvida, apita ;)


Knowledge is free!

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
leia

ola de novo,

Ontem estive ate as tantas de manha a tentar perceber como ou porque usar o Either e não cheguei a conclusão nenhuma por isso não disse mais nada :) :).

Estou mesmo agora a ver exemplos do que me deram e dicas para ver se entendo o funcionamento disso . E que nessa parte sou uma planta autentica e queria mesmo conseguir perceber e resolver exercícios deste género. Parece que tenho paragem de memória quando tento escrever algo com arvores... :confused::(:confused:

por exemplo se eu quero definir entao dois tipos Op2 e Op1 para representar os operadores binários e unários posso fazer isso?

data Op1 a = Minus a | Seno a | Coseno a | Leaf a
data Op2 a b = Plus (Op2 a b) (Op2 a b) | Minus (Op2 a b) (Op2 a b) | Mult (Op2 a b) (Op2 a b) | Div (Op2 a b) (Op2 a b) | Exp (Op2 a b) (Op2 a b)| Leaf a | Leaf b

Já agora mais acima me foi tb sugerido usar um novo tipo de dado Expr

data Expr a  =  Val a
	| Add  (Expr a) (Expr a)
	| Sub  ( Expr a) (Expr a)
	| Mul  (Expr a) (Expr a)
	| Div  (Expr a ) ( Expr a )

ou esta errado?

Editado por leia

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
Rui Carlos

Isso que tens não faz muito sentido, embora também não esteja completamente errado.

Para começar, sabes explicar o que é que isto significa?

data Op2 a b = Plus (Op2 a b) (Op2 a b) | Minus (Op2 a b) (Op2 a b) | Mult (Op2 a b) (Op2 a b) | Div (Op2 a b) (Op2 a b) | Exp (Op2 a b) (Op2 a b)| Leaf a | Leaf b

Sabes definir um valor que seja desse tipo que acabaste de definir?

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
leia

eu queria definir entao dois tipos Op2 e Op1 para representar os operadores binários e unários que tinha colocado logo no principio das duvidas.

Nao sei definir o valor que seja deste tipo.

Ca esta a dificuldade que tenho entre as outras!!!!!

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
Rui Carlos

O teu tipo Expr, tal como está agora, já não está longe do que precisas.

Mas primeiro, deixo aqui algumas notas sobre árvores (assumo que conheces minimamente o data, se não conheces, vê se isto ajuda):

-- definição do tipo 'Tree'
-- Uma 'Tree' pode ser:
data Tree = Node Tree Tree -- Um nodo que contém duas sub-árvores
         | Leaf Int       -- Ou uma folha que contém um inteiro

--      /\
--     /  \
--    /    \
--   /\    /\
--  /  \  /  \
--  1  2  3  4
t :: Tree
t = Node (Node (Leaf 1) (Leaf 2)) (Node (Leaf 3) (Leaf 4))

folha :: Tree
folha = Leaf 1

Isto é um tipo de árvore muito simples, que só armazena valores nas folhas da árvore.

O carácter | define os vários formatos que um valor do tipo Tree pode ter. Ou seja, uma árvore ou é um nodo com duas sub-árvores, ou então é uma folha com um inteiro.

t é a expressão do tipo Tree que armazena a árvore desenhada. folha é uma expressão do tipo Tree que armazena apenas uma folha com o valor 1.

-- Uma 'Tree' pode ser:
data Tree a = Node (Tree a) (Tree a) -- Um nodo que contém duas sub-árvores
           | Leaf a                 -- Ou uma folha que contém um valor do tipo 'a' (que é variável)

t1 :: Tree Int -- 'a' é 'Int', logo árvore de inteiros, igual à anterior
t1 = Node (Node (Leaf 1) (Leaf 2)) (Node (Leaf 3) (Leaf 4))

--      /\
--     /  \
--    /    \
--   /\    3.3
--  /  \
-- 1.1 2.2
t2 :: Tree Double -- 'a' é 'Double', logo árvore de doubles
t2 = Node (Node (Leaf 1.1) (Leaf 2.2)) (Leaf 3.3)

Esta é uma versão mais genérica da árvore anterior. Enquanto que na anterior as folhas armazenavam inteiros (obrigatoriamente), agora as folhas armazenam valores de qualquer tipo.

Assim, as folhas podem conter doubles (t2), strings, listas, etc.

data Tree = Node String Tree Tree -- Node que contém uma string, e duas sub-árvores
         | Leaf Int              -- Folha que contém um inteiro

--      "S"
--      / \
--     /   \
--    /     \
--    1    "M"
--         / \
--        /   \
--        3   5
t :: Tree
t = Node "S" (Leaf 1) (Node "M" (Leaf 3) (Leaf 5))

Este tipo de árvore, para além de armazenar informação nas folhas, também armazena informação nos nodos. Ou seja, agora uma árvore ou é um nodo com uma string e duas sub-árvores, ou então é uma folha com um inteiro.

Neste caso voltei a usar tipos fixos (String para os nodos, Int para as folhas). No teu caso, também podes começar por usar tipos fixos, ou seja, não precisas de algo como data Expr a b = ..., basta data Expr = ....

O único problema que tens na tua definição do Expr é o identificadores que estás a usar para os possíveis valores do tipo. Em vez de +, devias ter, por exemplo Soma. O mesmo para os restantes operadores.

Para ver se percebeste os conceitos, podes agora tentar definir o tipo Expr de forma a suportar não apenas inteiros. E depois, podes também tentar criar algo semelhante ao meu último tipo de árvore para que os operadores não sejam fixos. Na última árvore que desenhei, o "S" podia representar uma soma, e o "M" uma multiplicação, e terias outros valores para outras operações binárias. Podes usar uma estratégia semelhante para definires um tipo mais genérico. É uma solução deste género que precisas para usar o Op1 e o Op2 (Op1 e Op2 serão os tipos de dados dos valores armazenados nos nodos da tua árvore).

PS: Neste link, que já te indiquei anteriormente, tens lá uma definição simples para expressões matemáticas.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
Kimio

Aqui vai um exemplo para a simples expressão: 2 * (1 + 4) * (-3)

Usando o tal tipo de dados Expr, esta expressão poderia ser representada em algo do seguinte género:

Mul (Mul (Val 2) (Add (Val 1) (Val 4))) (Neg (Val 3))

O que daria uma árvore com o seguinte aspecto:

tree.png

Editado por Kimio

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
leia

portanto para operadores binarios poderia ficar assim

data Expr  = Val a
| Add (Expr a) (Expr a)
| Sub ( Expr a) (Expr a)
| Mul (Expr a) (Expr a)
| Div (Expr a) ( Expr a)
| Exp (Expr a) (Expr a)

Op2 :: Tree Double
data Op2  = Node Sum (Node Sub (Node Mul (Node Div (Node Exp ))))

para operadores unarios a seguir

data Expr = Val a
| Menos (Expr a) (Expr a)
| Seno ( Expr a) (Expr a)
| Coseno (Expr a) (Expr a)

Op1 ::Tree Double
data Op1 = Node Menos (Node Seno (Node Coseno ))

Sera que e assim????

Se fiz desparates peço desculpas!!!!

Se com a definição da minha Expr quero definir uma expressão que represente a expressão 3x^2 +5x +9

Escrevi assim mas nao sei se esta certo :confused:

Expr = Plus( Plus(Times( Leaf 3.0 (Pow(Leaf x Leaf 2.0))) Times(Leaf 5.0 Leaf x)) Leaf 9.0)

Plus

Plus

Times

3.0

Pow

x

2.0

Plus

5

x

9.0

Editado por leia

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
Kimio

Não precisas do Op1 e Op2, basta o Expr. E as operações unárias recebem apenas um Expr e não dois .

data Expr = Val Double
         | Var String
         | Add Expr Expr
         | Sub Expr Expr
         | Mul Expr Expr
         | Div Expr Expr
         | Pow Expr Expr
         | Neg Expr
         | Sin Expr
         | Cos Expr

Para simplificar, tou assumir que trabalhas apenas com Doubles (inteiros não ligam muito bem com senos e cossenos).

A expressão 3x^2 +5x +9 pode ser representada da seguinte maneira:

Add (Add (Mul (Val 3) (Pow (Var "x") (Val 2))) (Mul (Val 5) (Var "x"))) (Val 9)

Editado por Kimio

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
leia

Obrigada ,ja estou a começar a perceber mais coisas desta materia...!!

Agora terei de modificar os tipos criados de forma a que sejam instâncias da classe Show.mas neste caso preciso do Op1 e Op2 ou não necessariamente? para que a expressão (3x^2+5x+9) ser mostrada da mesma forma que é necessária escreve-la.??


module BinaryTree
				   where

instance (Show Tree) => Show (tree) where
showTree = "<" ++ showTree l ++ "|" ++ showTree r ++ ">"

isso me da o seguinte erro

Syntax error in instance head (constructor expected)
Hugs> 

Editado por Rui Carlos

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
Kimio

Acho que ainda há aí alguma confusão. Se estiveres a usar o tipo que eu sugeri, então não precisas desse Tree para nada; a combinação de Exprs já forma uma árvore. Para tornar o Expr uma instância de Show, apenas tens que adicionar "deriving Show" e o compilador automáticamente cria a instância por ti:

data Expr = Val Double
         | Var String
         | Add Expr Expr
         | Sub Expr Expr
         | Mul Expr Expr
         | Div Expr Expr
         | Pow Expr Expr
         | Neg Expr
         | Sin Expr
         | Cos Expr
         deriving Show

Mas se quiseres mesmo criar a instância à mão (para definir um Show personalizado, ou apenas como exercício), então será algo deste género:

instance Show Expr where
 show (Val x) = "Val " ++ show x
 show (Var s) = "Var " ++ show s
 show (Add e1 e2) = "Add (" ++ show e1 ++ ") (" ++ show e2 ++ ")"
 ...

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
leia

Bom dia,

Sim E Verdade Kimio que ainda baralho mesmo tudo .Não tive quem me explicar isso e estou a tentar resolver um enunciado encadeado praticamente onde com o passar tenho de ir alterando as coisas.

Comecei por querer definir um tipo capaz de representar expressões aritméticas sob forma de uma árvore.Esta árvore poderá conter :

operadores binários : soma, substração, multiplicação, divisão e expoente.

operadores binários: menos unário, seno e coseno.

as folhas podem conter valores numericos ou variáveis. Uma variável é caracterisada pelo seu nome

(String ).

1.Depois tinha de definir dois tipos Op2 e Op1 para representar os operadores binários e unários.

2. Usando a sua definição do tipo expressão tinha que definir uma expressão que representa a expressão 3x2 +

5x + 9 . (Opcional poderei definir expressões auxiliares para representar cada parcela.)

3. Depois tinha que modificar os tipos criados de forma a que sejam instâncias da classe Show . Em que expressão deverá ser

mostrada da mesma forma que é necessária escreve-la

4.E por fim tenho de definir uma função treeShow :: Expr -> String que representa a expressão sob forma de uma

ávore. A expressão 3x2 + 5x + 9 será representada por :

Plus

Plus

Times

3.0

Pow

x

2.0

Plus

5

x

9.0

E isso que estou ha horas a tentar definir e entender.

Posso assumir que com a ultima parte o que inclui o deriving show ate ao ponto 4 esta resolvido???

E que so me falta responder o ponto 5??

Obrigada por me acompanharem a entender isso!!

Editado por Rui Carlos

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
Kimio

1. Não tinha ficado claro que definir os tipos Op1 e Op2 eram um requisito do problema. Sendo assim o tipo Expr precisa de ser alterado da seguinte maneira:

data Expr = Val Double
         | Var String
         | Binary Op2 Expr Expr
         | Unary Op1 Expr
         deriving Show


data Op1 = Cos | Sin | ...
          deriving Show

data Op2 = Plus | Minus | ...
          deriving Show

2. Com esta reformulação, uma expressão como por exemplo 3x^2 pode ser representado da seguinte maneira:

Binary Times (Val 3) (Binary Pow (Var x) (Val 2))

3. Acrescentado o "deriving Show" deverá ser suficiente.

4. O treeShow tem de ser implementado à mão, como por exemplo:

treeShow :: Expr -> String
treeShow e = treeShowAux 0 e


treeShowAux :: Int -> Expr -> String
treeShowAux indent (Val x) = (replicate indent ' ') ++ show x ++ "\n"
treeShowAux indent (Var s) = (replicate indent ' ') ++ s ++ "\n"
treeShowAux indent (Unary op e) = (replicate indent ' ') ++
                                 show op ++ "\n" ++
                                 (treeShowAux (indent + 1) e)
...

O nível de indentação vai sendo passado no argumento "indent".

Editado por Kimio
  • Voto 1

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
leia

Muito obrigada mais uma vez (a todos e pelas dicas todas que me derom) :)

Vou tentar agora preencher as partes incompletas e volto a colocar aqui o final para ver se esta bem feito.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
leia

Boa noite,

Não consegui por isso a correr pk me aparecem muitos erros :confused: :confused: !!!

Vou por o que completei

data Expr = Val Double
      | Var String
      | Binary Op2 Expr Expr
      | Unary Op1 Expr
     derivind Show
-- 1
data Op1 = Minus | Sin | Cos
  deriving Show

data Op2 = Plus | Minus | Times | Div | Pow
  deriving Show

--2.
Binary Plus ( Binary Plus ( Binary Times (Val 3) ( Binary Pow (Var x ) (Val 2)) Binary Times ( Val 5) (Var x))) (Val 9)

--4.função   -  treeShow


treeShow :: Expr -> String
treeShow e = treeShowAux 0 e


treeShowAux :: Int -> Expr -> String
treeShowAux indent (Val x) = (replicate indent ' ') ++ show x ++ "\n"
treeShowAux indent (Var s) = (replicate indent ' ') ++ s ++ "\n"
treeShowAux indent (Unary op e) = (replicate indent ' ') ++
				   show op ++ "\n"
				   (treeShowAux (indent + 1) e)
treeShowAux indent (Binary op f g) = (replicate indent ' ') ++ show op ++ "\n"
					  (treeShowAux (indent + 1) f) ++ "\n" (replicate indent " ") ++
					  (treeShowAux (indent + 1) g)






Editado por leia

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
Rui Carlos

Em Haskell os espaços, quebras de linha e afins são considerados para a interpretação do código.

Agora olha para o código que usaste e para o código que te deram, e tenta descobrir os erros que tens.

Adicionalmente, a linha seguinte é para quê?

Binary Plus ( Binary Plus ( Binary Times (Val 3) ( Binary Pow (Var x ) (Val 2)) Binary Times ( Val 5) (Var x))) (Val 9)

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
leia

Era um ponto a resolver que e este a seguir enunciado.

2. Usando a sua definição do tipo expressão tinha que definir uma expressão que representa a expressão 3x^2 +5x + 9 .

Os espaços que aparecem mal feitos estão por culpa do copy paste mas no meu ficheiro estão bem arrumados igual aos exemplos que me derom

Editado por leia

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
Kimio

Era um ponto a resolver que e este a seguir enunciado.

2. Usando a sua definição do tipo expressão tinha que definir uma expressão que representa a expressão 3x^2 +5x + 9 .

Sim, mas era suposto guardares isso algures, como numa constante. Deixar à solta no top-level não faz sentido; como é que depois conseguias aceder ao seu valor?

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
leia

reparei nos erros alterei mas continua a aparecer este erro.

Acerca de guardar não sei onde ao certo...

Expr :: Op2
Expr = Binary Plus ( Binary Plus ( Binary Times (Val 3) ( Binary Pow (Var x ) (Val 2)) Binary Times ( Val 5) (Var x))) (Val 9)

ERROR "tipoe.hs":34 - Type error in application
*** Expression : "\n" (treeShowAux (indent + 1) e)
*** Term : "\n"
*** Type : String
*** Does not match : a -> b

Editado por leia

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
leia

Boa tarde ,

Podem so dizer porque aparece -me este erro.Porque fiz todas as alterações necessarias para funcionar

expr :: Expr
expr = Binary Plus ( Binary Plus ( Binary Times ( Val 3) ( Binary Pow ( Var "x" ) ( Val 2))) ( Var "x")) (Val 9)

Syntax error in declaration (unexpected `::')

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!

Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.

Entrar Agora

×

Aviso Sobre Cookies

Ao usar este site você aceita os nossos Termos de Uso e Política de Privacidade. Este site usa cookies para disponibilizar funcionalidades personalizadas. Para mais informações visite esta página.