module Main where

import Data.Maybe (fromMaybe)
import Text.Read (readEither)
import Control.Monad (liftM2)
import Test.QuickCheck

-- Expression types
data IntExpr = Leaf Int | Add IntExpr IntExpr | Sub IntExpr IntExpr | Mul IntExpr IntExpr | Uminus IntExpr deriving (Show, Eq)
data IdExpr = LeafId Int | Id String deriving (Show, Eq)
data MaybeExpr = LeafMaybe Int | IdMaybe String | AddMaybe MaybeExpr MaybeExpr | SubMaybe MaybeExpr MaybeExpr | MulMaybe MaybeExpr MaybeExpr | UminusMaybe MaybeExpr deriving (Show, Eq)

-- Expression evaluation
evalIntExpr :: IntExpr -> Int
evalIntExpr (Leaf i) = i
evalIntExpr (Add e1 e2) = evalIntExpr e1 + evalIntExpr e2
evalIntExpr (Sub e1 e2) = evalIntExpr e1 - evalIntExpr e2
evalIntExpr (Mul e1 e2) = evalIntExpr e1 * evalIntExpr e2
evalIntExpr (Uminus e) = negate (evalIntExpr e)

evalIdExpr :: IdExpr -> [(String, Int)] -> Int
evalIdExpr (LeafId i) _ = i
evalIdExpr (Id idStr) env = fromMaybe 0 (lookup idStr env)

evalMaybeExpr :: MaybeExpr -> [(String, Int)] -> Maybe Int
evalMaybeExpr (LeafMaybe i) _ = Just i
evalMaybeExpr (IdMaybe idStr) env = lookup idStr env
evalMaybeExpr (AddMaybe m1 m2) env = liftM2 (+) (evalMaybeExpr m1 env) (evalMaybeExpr m2 env)
evalMaybeExpr (SubMaybe m1 m2) env = liftM2 (-) (evalMaybeExpr m1 env) (evalMaybeExpr m2 env)
evalMaybeExpr (MulMaybe m1 m2) env = liftM2 (*) (evalMaybeExpr m1 env) (evalMaybeExpr m2 env)
evalMaybeExpr (UminusMaybe m) env = fmap negate (evalMaybeExpr m env)

-- Parsing
data Token = Num Int | Op Operator deriving (Show, Eq)
data Operator = Plus | Minus | Multiply | UnaryMinus deriving (Show, Eq)

parseToken :: String -> Either String Token
parseToken "+" = Right (Op Plus)
parseToken "-" = Right (Op Minus)
parseToken "*" = Right (Op Multiply)
parseToken str = case reads str of
  [(value, "")] -> Right (Num value)
  _             -> Left "Unable to parse token."

parseTokens :: [String] -> Either String [Token]
parseTokens = mapM parseToken

postfixExpr :: String -> Either String [Token]
postfixExpr = parseTokens . words

-- Expression evaluation from postfix notation
evalPostfixExpr :: [Token] -> Either String Int
evalPostfixExpr = evalPostfixExpr' []

evalPostfixExpr' :: [Int] -> [Token] -> Either String Int
evalPostfixExpr' [result] [] = Right result
evalPostfixExpr' stack (Num n : tokens) = evalPostfixExpr' (n : stack) tokens
evalPostfixExpr' (y : x : stack) (Op op : tokens) = case op of
  Plus -> evalPostfixExpr' (x + y : stack) tokens
  Minus -> evalPostfixExpr' (x - y : stack) tokens
  Multiply -> evalPostfixExpr' (x * y : stack) tokens
  UnaryMinus -> evalPostfixExpr' ((-y) : stack) tokens
evalPostfixExpr' _ _ = Left "Invalid expression or operator."

-- Unit tests
prop_evalPostfixExpr :: String -> Bool
prop_evalPostfixExpr str = case postfixExpr str of
  Left _ -> True
  Right tokens -> case evalPostfixExpr tokens of
    Left _ -> False
    Right _ -> True

main :: IO ()
main = do
  putStrLn "Expression evaluation and parsing"
  putStrLn "==============================="

  let sampleEnv = [("x", 10), ("y", 20)] -- Sample environment

  -- Sample expressions
  let intExpr = Add (Leaf 2) (Mul (Leaf 3) (Leaf 4))
      idExpr = Add (Id "x") (LeafId 42)
      maybeExpr = AddMaybe (LeafMaybe 42) (IdMaybe "x")

  -- Evaluate expressions
  putStrLn "Expression Evaluation Results:"
  putStrLn $ "Int Expression: " ++ show (evalIntExpr intExpr)
  putStrLn $ "Id Expression: " ++ show (evalIdExpr idExpr sampleEnv)
  putStrLn $ "Maybe Expression: " ++ show (evalMaybeExpr maybeExpr sampleEnv)

  -- Run property-based tests
  putStrLn "\nProperty-based Tests:"
  quickCheck prop_evalPostfixExpr