A math expression evaluator written in Elm.
Evaluates parentheses, exponentials, addition, subtraction, multiplication, and integer division from a String representation.
#Evaluating expressions
Evaluate a math expression
evaluateExpression "5 * (10 / (10 - 8)) + 3" == Ok 28
evaluateExpression "2^10" == Ok 1024
evaluateExpression "invalid" == Err "'i' is not a supported Operator."
evaluateExpression "6 + 4) / 5" == Err "Unmatched CloseParen at chararcter #6."
evaluateExpression "6 + 4 / " == Err "Too few values for the operators."
evaluateExpression "5 / (1 - 1)" == Err "Cannot divide by 0."
module Math.Strings exposing (evaluateExpression)
{-| A math expression evaluator written in Elm.
Evaluates parentheses, exponentials, addition, subtraction, multiplication, and integer division from a String representation.
#Evaluating expressions
@docs evaluateExpression
-}
import Stack exposing (Stack)
import Char
import Debug
import Math.Strings.Operators as Operators exposing (Operator(..))
import Math.Strings.Tokens exposing (..)
import Math.Strings.EvaluationState exposing (..)
{-| Evaluate a math expression
evaluateExpression "5 * (10 / (10 - 8)) + 3" == Ok 28
evaluateExpression "2^10" == Ok 1024
evaluateExpression "invalid" == Err "'i' is not a supported Operator."
evaluateExpression "6 + 4) / 5" == Err "Unmatched CloseParen at chararcter #6."
evaluateExpression "6 + 4 / " == Err "Too few values for the operators."
evaluateExpression "5 / (1 - 1)" == Err "Cannot divide by 0."
-}
evaluateExpression : String -> Result String Int
evaluateExpression expr =
evaluate initialState expr
{-| Given a condition, recursively apply the top Operator to the top two values until the condition returns True.
-}
applyUntil : (Operator -> Bool) -> EvaluationState -> Result String EvaluationState
applyUntil cond state =
case Stack.top state.operators of
Just nextOp ->
if cond nextOp then
--if the condition says to stop applying
Ok state
else
let
( maybeB, tmpVals ) =
Stack.pop state.values
( maybeA, newVals ) =
Stack.pop tmpVals
newValue =
Maybe.map2 (Operators.applyOperator nextOp) maybeB maybeA
in
case newValue of
Just resultVal ->
let
( _, newOperators ) =
Stack.pop state.operators
updateState : Int -> EvaluationState
updateState value =
{ state | values = (Stack.push value newVals), operators = newOperators }
in
resultVal
|> Result.map updateState
|> Result.andThen (applyUntil cond)
Nothing ->
Err "Too few values for the operators"
Nothing ->
Ok state
{-| Update the EvaluationState token by token until the expression is empty. Once the string is empty, process remaining Operators in the EvaluationState.
-}
evaluate : EvaluationState -> String -> Result String Int
evaluate state expr =
let
vals =
state.values
runningVal =
state.runningValue
in
case String.uncons expr of
Nothing ->
saveRunningVal state
|> Result.andThen (applyUntil (\x -> False))
|> Result.map (\s -> Stack.pop s.values)
|> Result.andThen
(\( maybeFinal, remaining ) ->
case maybeFinal of
Just finalValue ->
case Stack.top remaining of
Nothing ->
Ok finalValue
Just _ ->
Err "Too few operators."
Nothing ->
Err "Evaluation error: no final value."
)
Just ( nextChar, exprTail ) ->
parseToken nextChar
|> Result.andThen (processToken state)
|> Result.andThen (\newState -> evaluate newState exprTail)
{-| Update the EvaluationState by processing the Token
-}
processToken : EvaluationState -> Token -> Result String EvaluationState
processToken state token =
let
newState =
incrementNumProcessed state
in
case token of
Whitespace ->
saveRunningVal newState
Digit digitAsChar ->
let
digitAsString =
String.fromChar digitAsChar
newRunning =
newState.runningValue
|> Maybe.map (\s -> String.append s digitAsString)
|> Maybe.withDefault digitAsString
in
Ok { newState | runningValue = Just newRunning }
Op operator ->
saveRunningVal newState
|> Result.andThen (processOperator operator)
{-| Handle the Operator according to the current EvaluationState. There are three cases here:
1. The Operator is '(' -> push to Operator stack
2. The Operator is ')' -> apply all Operators on the stack until we reach the matching '(', then pop the '(' off the Operator stack
3. The Operator is any other -> apply the Operators on top of the stack while they have a higher precedence than the new Operator, then push the new Operator on the Operator stack.
-}
processOperator : Operator -> EvaluationState -> Result String EvaluationState
processOperator op state =
case op of
OpenParen ->
Ok (addOperator OpenParen state)
CloseParen ->
if state.nestedLevel < 1 then
-- no matching open paren, err
Err ("Unmatched CloseParen at chararcter #" ++ (toString state.numProcessed))
else
--process until we find the OpenParen
applyUntil (\o -> o == OpenParen) state
|> Result.map popOperator
_ ->
--op is a valid operator. apply while it has precendence
applyUntil (Operators.hasPrecedence op) state
|> Result.map (addOperator op)