逆ポーランド形式に変換するだけ

ParseFormula.hs

import Text.ParserCombinators.Parsec
import qualified Text.ParserCombinators.Parsec.Token as TokenSymbols
import Text.ParserCombinators.Parsec.Language

{-
  data Impl
-}
data Impl = ImplNum Integer | ImplSym String | ImplOp String
  deriving Show

generate_exp :: String -> [Impl] -> [Impl] -> [Impl]

-- prefix notation
-- generate_exp op lhs rhs = [ImplOp op] ++ lhs ++ rhs

-- infix notation
-- generate_exp op lhs rhs = lhs ++ [ImplOp op] ++ rhs

-- postfix notation
generate_exp op lhs rhs = lhs ++ rhs ++ [ImplOp op]

(<||>) f g = \x -> (f x) <|> (g x)

{-
  parser
-}

lexer :: TokenSymbols.TokenParser ()
lexer = TokenSymbols.makeTokenParser emptyDef

symbol = TokenSymbols.symbol     lexer
number = TokenSymbols.natural    lexer
ident  = TokenSymbols.identifier lexer

{-
calc expr BNF
  infix  -> exp
  exp    -> term   "+" exp  | term   "-" exp  | term
  term   -> factor "*" term | factor "/" term | factor
  factor -> ident | number | "(" exp ")"

calc expr BNF (re-define)
  infix  -> exp
  exp    -> term exp'
  exp'   -> "+" term exp'    | "-" term exp'    | e
  term   -> factor term'
  term'  -> "*" factor term' | "/" factor term' | e
  factor -> ident | number | "(" exp ")"
  e      -> nil
-}

convert_str s = parse parse_infix "convert_str" s

parse_infix = parse_exp

parse_exp = parse_term >>= parse_exp'

parse_exp' = parse_exp_op "+"
        <||> parse_exp_op "-"
        <||> return

parse_exp_op op lhs = generate_exp op lhs <$>
                      (symbol op *> parse_term) >>= parse_exp'

parse_term = parse_factor >>= parse_term'

parse_term' = parse_term_op "*"
         <||> parse_term_op "/"
         <||> return

parse_term_op op lhs = generate_exp op lhs <$>
                       (symbol op *> parse_factor) >>= parse_term'

parse_factor = parse_factor_number
           <|> parse_factor_ident
           <|> parse_factor_exp

parse_factor_number = (\x -> [ImplNum x]) <$>
                      number

parse_factor_ident = (\x -> [ImplSym x]) <$>
                     ident

parse_factor_exp = symbol "(" *> parse_exp <* symbol ")"

{-
   main
 -}
main = do
  print $ convert_str "1+2*3-4"
  print $ convert_str "(1+2)*(3-4)"