importData.Char(isSpace)-- A simple interpreter for a math expressions.-- Supported binary operations: +-/*-- Supported unary operations: +--- All operators are right associative.-- Operator precedence: Unary Operators > -- Multiplication, Division > -- Addition, Subtraction-- Output is modulo 10^9 + 7---------------------------------------------------------------------------------- GrammardataExp=Exp1TermOpEExp|Exp2TermdataTerm=Trm1FactorOpTTerm|Trm2FactordataFactor=NumberInteger|Fac2UnOpFactor|Fac3ExpdataUnOp=NotNeg|NegdataOpE=Sub|AdddataOpT=Div|Mul---------------------------------------------------------------------------------- Parser ToolsdataParserta=Parser([t]->EitherString(a,[t]))instanceMonad(Parsers)wherereturnx=Parser(\xs->Right(x,xs))Parserh>>=f=Parser(\s->casehsofLefta->LeftaRight(x,s')->casefxof(Parserm)->ms')(<|>)::Parsersa->Parsersa->Parsersa(Parserf1)<|>(Parserf2)=Parser(\s->casef1sofLeft_->f2sa->a)parse::Parserta->[t]->EitherString(a,[t])parse(Parserf)=fsat::(Char->Bool)->ParserCharCharsatp=Parserfwheref(x:xs)|px=Right(x,xs)fxs=Left$"Can't parse sat at "++xsmany::Showa=>Parserca->Parserc[a]manyp=lots<|>nonewherelots=do{x<-p;xs<-manyp;return(x:xs)}none=return[]whitespace::ParserCharCharwhitespace=satisSpacelexeme::ParserCharb->ParserCharblexemep=dox<-pmanywhitespacereturnxparens::ParserCharb->ParserCharbparensp=dolexeme$sat(=='(')x<-plexeme$sat(==')')returnx---------------------------------------------------------------------------------- ParserparseExp::ParserCharExpparseExp=parseExp1<|>parseExp2parseExp1::ParserCharExpparseExp1=dot<-parseTermo<-parseOpEe<-parseExpmanywhitespacereturn$Exp1toeparseExp2::ParserCharExpparseExp2=dot<-parseTermmanywhitespacereturn$Exp2tparseTerm::ParserCharTermparseTerm=parseTerm1<|>parseTerm2parseTerm1::ParserCharTermparseTerm1=dof<-parseFactoro<-parseOpTt<-parseTermmanywhitespacereturn$Trm1fotparseTerm2::ParserCharTermparseTerm2=dof<-parseFactormanywhitespacereturn$Trm2fparseFactor::ParserCharFactorparseFactor=parseNumber<|>parseFac2<|>parseFac3parseFac2::ParserCharFactorparseFac2=doo<-parseUnOpf<-parseFactormanywhitespacereturn$Fac2ofparseFac3::ParserCharFactorparseFac3=doe<-parensparseExpmanywhitespacereturn$Fac3eparseNumber::ParserCharFactorparseNumber=don<-parseNumber'manywhitespacereturnnwhereparseNumber'::ParserCharFactorparseNumber'=Parser(\s->casegetIntsofNothing->Left"Can't parse int"Just(i,s')->Right(Number(readi),s'))getInt::String->Maybe(String,String)getInt[]=NothinggetInt(x:xs)|x`elem`"0123456789"=casegetIntxsofJust(s1,s2)->Just(x:s1,s2)Nothing->Just([x],xs)getInt_=NothingparseOpE::ParserCharOpEparseOpE=doo<-lexeme$sat(`elem`"-+")manywhitespacecaseoof'-'->returnSub'+'->returnAdd_->error"Parse error: failed while parsing + or -"parseOpT::ParserCharOpTparseOpT=doo<-lexeme$sat(`elem`"/*")manywhitespacecaseoof'/'->returnDiv'*'->returnMul_->error"Parse error: failed while parsing / or *"parseUnOp::ParserCharUnOpparseUnOp=doo<-lexeme$sat(`elem`"-+")manywhitespacecaseoof'+'->returnNotNeg'-'->returnNeg_->error"Parse error: failed while parsing + or -"---------------------------------------------------------------------------------- Interpretereval::Exp->Integerevale=evalee`mod`modAmountmodAmount::IntegermodAmount=10^(9::Int)+7evale::Exp->Integerevale(Exp1tSube)=evaltt-evaleeevale(Exp1tAdde)=evaltt+evaleeevale(Exp2t)=evalttevalt::Term->Integerevalt(Trm1fDivt)=evalff*powm(evaltt)(modAmount-2)modAmount1evalt(Trm1fMult)=evalff*evalttevalt(Trm2f)=evalffevalf::Factor->Integerevalf(Numberi)=ievalf(Fac2Negf)=-(evalff)evalf(Fac2NotNegf)=evalffevalf(Fac3e)=evaleepowm::Integer->Integer->Integer->Integer->Integerpowm_0_r=rpowmbemr|e`mod`2==1=powm(b*b`mod`m)(e`div`2)m(r*b`mod`m)powmbemr=powm(b*b`mod`m)(e`div`2)mr---------------------------------------------------------------------------------- Mainmain::IO()main=doexpression<-getLineletex=parseparseExpexpressionans=caseexofRight(e,_)->show$evaleLefterr->showerrputStrLnans