Code Golf: Mathematical expression evaluator (that respects PEMDAS)

user_63844 0
Viewed 7442

I challenge you to write a mathematical expression evaluator that respects PEMDAS (order of operations: parentheses, exponentiation, multiplication, division, addition, subtraction) without using regular expressions, a pre-existing "Eval()"-like function, a parsing library, etc.

I saw one pre-existing evaluator challenge on SO (here), but that one specifically required left-to-right evaluation.

Sample inputs and outputs:

"-1^(-3*4/-6)" -> "1"

"-2^(2^(4-1))" -> "256"

"2*6/4^2*4/3" -> "1"

I wrote an evaluator in C#, but would like to see how badly it compares to those of smarter programmers in their languages of choice.

Related:

Code Golf: Evaluating mathematical expressions

Clarifications:

  1. Let's make this a function that accepts a string argument and returns a string result.

  2. As for why no regexes, well, that's to level the playing field. I think there ought to be a separate challenge for "the most compact regex".

  3. Using StrToFloat() is acceptable. By "parsing library" I meant to exclude such things as general-purpose grammar parsers, also to level the playing-field.

  4. Support floats.

  5. Support paretheses, exponentiation, and the four arithmetic operators.

  6. Give multiplication and division equal precedence.

  7. Give addition and subtraction equal precedence.

  8. For simplicity, you may assume all inputs are well-formed.

  9. I don't have a preference as to whether your function accepts such things as ".1" or "1e3" as valid numbers, but accepting them would earn you brownie points. ;)

  10. For divide-by-zero cases, you could perhaps return "NaN" (assuming you wish to implement error handling).

rosetta-stone code-golf math parsing
18 Answers

I know, I know..this code-golf seems to be closed. Still, I felt the urge to code this stuff in erlang __, so here is an erlang version (didn't found the will to golf-format it, so these are 58 lines, about 1400 chars)

-module (math_eval).
-export ([eval/1]).
eval( Str ) ->
  ev(number, Str,[]).
ev( _, [], Stack ) -> [Num] = do(Stack), Num;
ev( State, [$ |Str], Stack ) ->
  ev( State,Str,Stack );
ev( number, [$(|Str], Stack ) ->
  ev( number,Str,[$(|Stack] );
ev( number, Str, Stack ) ->
  {Num,Str1} = r(Str),
  ev( operator,Str1,[Num|Stack] );
ev( operator, [$)|Str], Stack) ->
  ev( operator, Str, do(Stack) );
ev( operator, [Op2|Str], [N2,Op,N1|T]=Stack ) when is_float(N1) andalso is_float(N2) ->
  case p(Op2,Op) of
    true -> ev( number, Str, [Op2|Stack]);
    false -> ev( operator, [Op2|Str], [c(Op,N1,N2)|T] )
  end;
ev( operator, [Op|Str], Stack ) ->
  ev( number,Str,[Op|Stack] ).
do(Stack) ->
  do(Stack,0).
do([],V) -> [V];
  do([$(|Stack],V) -> [V|Stack];
do([N2,Op,N1|Stack],0) ->
  do(Stack,c(Op,N1,N2));
do([Op,N1|Stack],V) ->
  do(Stack,c(Op,N1,V)).
p(O1,O2) -> op(O1) < op(O2).
op(O) ->
  case O of
    $) -> 0; $( -> 0;
    $^ -> 1;
    $* -> 2; $/ -> 2;
    $+ -> 3; $- -> 3;
    $  -> 4; _ -> -1
  end.
r(L) ->
  r(L,[]).
r([], Out) ->
  {f( lists:reverse(Out) ),[]};
r([$-|R],[]) ->
  r(R,[$-]);
r([C|T]=R,O) ->
  if (C =< $9 andalso C >= $0) orelse C =:= $. -> r(T,[C|O]);
    true -> {f(lists:reverse(O)),R}
  end.
f(L) ->
  case lists:any(fun(C) -> C =:= $. end,L) of
    true -> list_to_float(L);
    false -> list_to_float(L++".0")
  end.
c($+,A,B) -> A+B;
c($-,A,B) -> A-B;
c($*,A,B) -> A*B;
c($/,A,B) -> A/B;
c($^,A,B) -> math:pow(A,B).
cheng81_467540
Related