Skip to content

Instantly share code, notes, and snippets.

@oscherler
Created August 15, 2019 09:49
Show Gist options
  • Save oscherler/91c272e0f78783900f79b99e1b5f4825 to your computer and use it in GitHub Desktop.
Save oscherler/91c272e0f78783900f79b99e1b5f4825 to your computer and use it in GitHub Desktop.
Expression parser in Erlang

Extended expression parser for the dev.to daily challenge #10.

Try it:

% erl
1> c(calc).
{ok,calc}
2> calc:test().
  All 57 tests passed.
ok
3> calc:calc("1.5 * 2").
3.0
4> calc:calc("12e4 * 2e-3").
240.0
5> calc:calc("3 ^ 4").
81.0
6> calc:calc("2 ^ 0.5").
1.4142135623730951
7> calc:calc("2 + ( 3 * 4 )").
14.0
8> calc:calc("8 / 2 * (2 + 2)").
16.0 % OBVIOUSLY!
9> calc:calc("3^(1/2)").
1.7320508075688772
-module( calc ).
-export( [ calc/1 ] ).
-include_lib("eunit/include/eunit.hrl").
% expr := term [+|- term]*
% term := factor [*|/ factor]*
% factor := num_expr [^ num_expr]?
% num_expr := number | ( expr )
% number := -?digit+
skip_ws( [ $\ | Rest ] ) ->
skip_ws (Rest );
skip_ws( [ $\t | Rest ] ) ->
skip_ws (Rest );
skip_ws( Rest ) ->
Rest.
parse_number( [ $- | S ] ) ->
parse_number( S, undef, -1, int, undef, undef );
parse_number( S ) ->
parse_number( S, undef, 1, int, undef, undef ).
% decimal point
parse_number( [ $. | Rest ], Value, Sign, int, undef, undef ) ->
parse_number( Rest, Value, Sign, 0, undef, undef );
% exponent
parse_number( [ $e | Rest ], Value, Sign, Decimals, undef, undef ) ->
parse_number( Rest, Value, Sign, Decimals, exp, 1 );
% new integer or decimal digit
parse_number( [ C | Rest ], Value, Sign, Decimals, undef, undef ) when C >= $0, C =< $9 ->
NewValue = case Value of
undef -> 0;
_ -> Value
end * 10 + ( C - $0 ),
NewDecimals = case Decimals of
int -> int;
_ -> Decimals + 1
end,
parse_number( Rest, NewValue, Sign, NewDecimals, undef, undef );
% negative sign of exponent
parse_number( [ $- | Rest ], Value, Sign, Decimals, exp, 1 ) ->
parse_number( Rest, Value, Sign, Decimals, 0, -1 );
% new exponent digit
parse_number( [ C | Rest ], Value, Sign, Decimals, Exp, ExpSign ) when C >= $0, C =< $9 ->
NewExp = case Exp of
exp -> 0;
_ -> Exp
end * 10 + ( C - $0 ),
parse_number( Rest, Value, Sign, Decimals, NewExp, ExpSign );
% end of number
parse_number( Rest, Value, Sign, Decimals, Exp, ExpSign ) ->
Scale = case Decimals of
int -> 1;
_ -> math:pow( 10, Decimals )
end,
ExpScale = case { Exp, ExpSign } of
{ undef, _ } -> 1;
{ exp, _ } -> 1;
{ _, _ } -> math:pow( 10, ExpSign * Exp )
end,
case Value of
undef -> { invalid, "" };
_ -> { Sign * Value * ExpScale / Scale, Rest }
end.
parse_numexpr( [ $( | Rest ] ) ->
{ Expr, R1 } = parse_expr( skip_ws( Rest ) ),
R2 = skip_ws( R1 ),
case R2 of
[ $) | R3 ] -> { Expr, R3 };
_ -> { invalid, "" }
end;
parse_numexpr( S ) ->
parse_number( S ).
parse_factor( S ) ->
{ Base, R1 } = parse_numexpr( S ),
R2 = skip_ws( R1 ),
{ Exp, R3 } = case R2 of
[ $^ | R4 ] -> parse_numexpr( skip_ws( R4 ) );
_ -> { 1, R2 }
end,
{ math:pow( Base, Exp ), R3 }.
parse_term( S ) ->
parse_term( S, 1, $* ).
parse_term( S, Value, Op ) ->
{ F1, R1 } = parse_factor( S ),
NewValue = case Op of
$* -> Value * F1;
$/ -> Value / F1
end,
R2 = skip_ws( R1 ),
case R2 of
[ $* | R3 ] -> parse_term( skip_ws( R3 ), NewValue, $* );
[ $/ | R3 ] -> parse_term( skip_ws( R3 ), NewValue, $/ );
_ -> { NewValue, R2 }
end.
parse_expr( S ) ->
parse_expr( S, 0, $+ ).
parse_expr( S, Value, Op ) ->
{ F1, R1 } = parse_term( S ),
NewValue = case Op of
$+ -> Value + F1;
$- -> Value - F1
end,
R2 = skip_ws( R1 ),
case R2 of
[ $+ | R3 ] -> parse_expr( skip_ws( R3 ), NewValue, $+ );
[ $- | R3 ] -> parse_expr( skip_ws( R3 ), NewValue, $- );
_ -> { NewValue, R2 }
end.
calc( S ) ->
{ Result, [] } = parse_expr( skip_ws( S ) ),
Result.
% TESTS
skip_ws_test_() -> [
?_assertEqual( "", skip_ws("") ),
?_assertEqual( "", skip_ws(" ") ),
?_assertEqual( "", skip_ws(" ") ),
?_assertEqual( "", skip_ws( [ $\t ] ) ),
?_assertEqual( "ASDF", skip_ws(" ASDF") ),
?_assertEqual( "AS DF ", skip_ws( [ $\ , $\t, $\ , $\ , $A, $S, $\ , $D, $F, $\ ] ) )
].
parse_number_test_() -> [
?_assertEqual( { 0.0, "" }, parse_number("0") ),
?_assertEqual( { 2.0, "" }, parse_number("2") ),
?_assertEqual( { 42.0, "" }, parse_number("42") ),
?_assertEqual( { -1.0, "" }, parse_number("-1") ),
?_assertEqual( { -145.0, "" }, parse_number("-145") ),
?_assertEqual( { -145.0, " some stuff" }, parse_number("-145 some stuff") ),
?_assertEqual( { invalid, "" }, parse_number("asdf") ),
?_assertEqual( { invalid, "" }, parse_number("-") ),
?_assertEqual( { invalid, "" }, parse_number("-stuff") ),
?_assertEqual( { invalid, "" }, parse_number("- stuff") ),
?_assertEqual( { 1.5, "" }, parse_number("1.5") ),
?_assertEqual( { 1.234, "" }, parse_number("1.234") ),
?_assertEqual( { 0.5, "" }, parse_number("0.5") ),
?_assertEqual( { 0.05, "" }, parse_number("0.05") ),
?_assertEqual( { 0.05, "" }, parse_number(".05") ),
?_assertEqual( { -0.32, "" }, parse_number("-.32") ),
?_assertEqual( { 10000.0, "" }, parse_number("1e4") ),
?_assertEqual( { 0.01, "" }, parse_number("1e-2") ),
?_assertEqual( { 234.5, "" }, parse_number("2.345e2") ),
?_assertEqual( { 45.67, "" }, parse_number("4567e-2") ),
?_assertEqual( { 4.0, "" }, parse_number("4e") ),
?_assertEqual( { 4.0, "" }, parse_number("4e-") ),
?_assertEqual( { 4.0, "" }, parse_number("4e0") ),
?_assertEqual( { 4.0, "" }, parse_number("4e-0") )
].
parse_factor_test_() -> [
?_assertEqual( { 2.0, "" }, parse_factor("2") ),
?_assertEqual( { 2.0, "" }, parse_factor("2^1") ),
?_assertEqual( { 2.0, "" }, parse_factor("2^ 1") ),
?_assertEqual( { 2.0, "" }, parse_factor("2 ^1") ),
?_assertEqual( { 2.0, "" }, parse_factor("2 ^ 1") ),
?_assertEqual( { 1.0, "" }, parse_factor("4^0") ),
?_assertEqual( { 0.01, "" }, parse_factor("10^-2") ),
?_assertEqual( { 5.0, "" }, parse_factor("25^0.5") )
].
parse_term_test_() -> [
?_assertEqual( { 6.0, "" }, parse_term("3 * 2") ),
?_assertEqual( { -6.0, "" }, parse_term("-3 * 2") ),
?_assertEqual( { -6.0, "" }, parse_term("3 * -2") ),
?_assertEqual( { 6.0, "" }, parse_term("-3 * -2") )
].
parse_expr_test_() -> [
?_assertEqual( { 5.0, "" }, parse_expr("3 + 2") ),
?_assertEqual( { 1.0, "" }, parse_expr("3 - 2") ),
?_assertEqual( { 1.0, "" }, parse_expr("3 + -2") ),
?_assertEqual( { -1.0, "" }, parse_expr("-3 - -2") )
].
calc_test_() -> [
?_assertEqual( 0.0, calc("0") ),
?_assertEqual( 2.0, calc("2") ),
?_assertEqual( -3.0, calc("-3") ),
?_assertEqual( 128.0, calc("128 ") ),
?_assertEqual( 128.0, calc(" 128 ") ),
?_assertEqual( 14.0, calc("2 + 3 * 4") ),
?_assertEqual( 9.0, calc("6 / 2 * 3") ),
?_assertEqual( 1.0, calc("-1 - -2") ),
?_assertEqual( 11.0, calc("3 * -2 + 17") ),
?_assertEqual( -251.0, calc("5 ^ 3 * -2 - 1") ),
?_assertEqual( 25.0, calc("( 2 + 3 ) ^( 1 + 1 )") )
].
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment