-- Primeira Prova de LP2 -- 10/12/98
------------------------------------

--1 - (2.0) Compreensoes de listas sao um excelente mecanismo
--    para definir listas a partir de outras listas.
--    Usando compreensao de listas, defina as seguintes funcoes:

map' :: (a->b) -> [a] -> [b]
map' f l = [f x | x <- l]

filter' :: (a -> Bool) -> [a] -> [a]
filter' p l = [x | x <- l, p x]

mcs :: Int -> Int -> [Int]
    -- multiplos comuns de dois numeros (ate' no maximo x * y)
mcs x y = [z | z <- [x..(x*y)], z `mod` x == 0, z `mod` y == 0]

dcs :: Int -> Int -> [Int] 
    -- divisores comuns de dois numeros
dcs x y = [z | z <- [1..(max x y)], x `mod` z == 0, y `mod` z == 0]
     
--2 - Algumas calculadoras, para evitar o uso de parenteses,
--    trabalham com uma notacao matematica onde as operacoes
--    aparecem apos os operandos, por exemplo:
--    "3 4 +" --> "3 + 4" --> 7
--    "3 4 + 11 1 - *" --> "(3 + 4) * (11 - 1)" --> 70
--    "3 4 11 1 - * *" --> "3 * (4 * (11 - 1))" --> 120
--    "3 4 11 1 - 5 * * +" --> "3 + (4 * ((11 - 1) * 5))" --> 203
--    faca funcoes para:
--    (1.0) separar uma String em Strings apenas com numeros ou operacoes:
separa :: String -> [String]
--          separa "3 4 11 1 - * *" = ["3","4","11","1","-","*","*"]
separa [] = []
separa st = (takeWhile (/=' ') (dropWhile (==' ') st)) : 
            (separa (dropWhile (/=' ') (dropWhile (==' ') st)))

--    (0.5) contar o numero de operacoes em uma String nesta notacao
ops :: String -> Int
--          ops "3 4 11 1 - * *" = 3
ops st = length [c | c <- st, c `elem` "+-*"]

--    (1.0) contar o numero de operandos em uma String nesta notacao
operandos :: String -> Int
--          operandos "3 4 11 1 - * *" = 4
operandos st = length (filter soNumeros (separa st))
-- ou simplesmente
-- operandos = length . filter soNumeros . separa
  where
    soNumeros (x:xs) = isDigit x 

--    (1.0) converter um operando em seu respectivo inteiro:
--          stoi' "225" = 225
stoi' :: String -> Int
stoi' [] = 0
stoi' (x:xs) = (ord x - ord '0') * (10^(length xs)) + stoi' xs
-- ou, mais simplemente
stoi'' :: String -> Int
stoi'' st = read st

--    (1.0) qual o tipo da seguinte funcao:
--stoop :: String -> Int -> Int -> Int
--(os parenteses sao opcionais), ou, mais precisamente
stoop :: Num t => String -> t -> t -> t
stoop "*" = (*)
stoop "+" = (+)
stoop "-" = (-)

--    (2.0) avaliar uma expressao nesta notacao
evalR :: String -> Int
--          evalR "3 4 + 11 1 - *" = 70
evalR st = stoi' (head (simplif (separa st)))
  where
    simplif (v1:v2:op:resto) | isOp op = simplif (show ((stoop op) (stoi' v1) (stoi' v2)) : resto)
    simplif (v1:v2:v3:resto) = simplif (v1:simplif (v2:v3:resto))
    simplif resultado = resultado

isOp st = st == "*" || st == "+" || st == "-"

--    (2.0) mostrar uma expressao nesta notacao com parenteses
showParen' :: String -> String
--          showParen' "3 4 + 11 1 - *" = "(3 + 4) * (11 - 1)" 
showParen' st = head (simpl (separa st))
  where
    simpl (v1:v2:op:resto) | isOp op = simpl (("(" ++ v1 ++ op ++ v2 ++ ")") : resto)
    simpl (v1:v2:v3:resto) = simpl (v1:simpl (v2:v3:resto))
    simpl result = result