3
\$\begingroup\$

We all know the standard order of operations for math functions (PEMDAS), but what if we instead evaluated expressions left-to-right?

The Challenge

Given a string through standard input or through command line args, find the difference between the traditional evaluation (PEMDAS) and the in-order (left-to-right) evaluation of that expression.

Details

  • You will be given a string in a format such as:

    "1 + 2 * 3 ^ 2 - 11 / 2 + 16"
    
  • To simplify things, there will be:

    • a space between each number and operator
    • no leading or trailing spaces
    • no decimal numbers or negative numbers (non-negative integers only)
    • no operators beyond +(plus), -(minus), *(multiply), /(divide), ^(exponentiation)
    • no parens to worry about
    • you may remove the spaces if it's easier for you to handle, but no other modification of the input format will be allowed.
  • You must provide the absolute value of the difference between the two evaluations of the string

  • Your division can either be floating-point or integer division - both will be accepted
  • Your program can not use any sort of expression evaluation library.

    To clarify - any sort of built-in eval function in which your language evaluates a string that is valid code for the same language IS acceptable

  • Explanations of your code are preferred
  • Shortest code by byte count wins
  • Winner will be chosen Saturday (July 19, 2014)

Examples:

A: 1 + 2 * 3 ^ 2 - 11 / 2 + 16 (using floating-point division)

  • In traditional order of operations:

    1 + 2 * 3 ^ 2 - 11 / 2 + 16   -->   1 + 2 * 9 - 11 / 2 + 16   -->
    
    1 + 18 - 5.5 + 16             -->   29.5
    
  • In-order traversal yields:

    1 + 2 * 3 ^ 2 - 11 / 2 + 16   -->   3 * 3 ^ 2 - 11 / 2 + 16   -->
    
    9 ^ 2 - 11 / 2 + 16           -->   81 - 11 / 2 + 16          -->
    
    70 / 2 + 16                   -->   35 + 16                   -->
    
    51
    
  • Resulting difference: 51 - 29.5 = 21.5

B: 7 - 1 * 3 ^ 2 + 41 / 3 + 2 * 9 * 2 (using integer division)

  • In traditional order of operations:

    7 - 1 * 3 ^ 2 + 41 / 3 + 2 * 9 * 2   -->   7 - 1 * 9 + 41 / 3 + 2 * 9 * 2   -->
    
    7 - 9 + 13 + 18 * 2                  -->   7 - 9 + 13 + 36                  -->
    
    47
    
  • In-order traversal yields:

    7 - 1 * 3 ^ 2 + 41 / 3 + 2 * 9 * 2   -->   6 * 3 ^ 2 + 41 / 3 + 2 * 9 * 2   -->
    
    18 ^ 2 + 41 / 3 + 2 * 9 * 2          -->   324 + 41 / 3 + 2 * 9 * 2         -->
    
    365 / 3 + 2 * 9 * 2                  -->   121 + 2 * 9 * 2                  -->
    
    123 * 9 * 2                          -->   1107 * 2                         -->
    
    2214
    
  • Resulting difference: 2214 - 47 = 2167

\$\endgroup\$
  • 1
    \$\begingroup\$ Can we use parentheses if we want to...? or are they forbidden? \$\endgroup\$ – Eric Lagergren Jul 16 '14 at 3:10
  • \$\begingroup\$ They're forbidden. I'll make that edit. \$\endgroup\$ – Kyle McCormick Jul 16 '14 at 13:49
  • \$\begingroup\$ @KyleMcCormick Is eval forbidden? If so It appears that only the Haskell answer is valid. \$\endgroup\$ – core1024 Jul 16 '14 at 15:45
  • 1
    \$\begingroup\$ Dosen't eval sort of vastly simplify the challenge? I mean for most langauges with eval, eval = the traditional order. (And surely you folks can do better than Haskell, even without eval...!) \$\endgroup\$ – MtnViewMark Jul 17 '14 at 3:27
  • \$\begingroup\$ @MtnViewMark There is still a challenge when allowing evals. The challenge comes with doing both orders of operations. Languages will not eval for both orders. Golfers will most likely end up with one easier(shorter) case akin to their language's syntax and one harder(longer) case that requires more manipulation. \$\endgroup\$ – Kyle McCormick Jul 18 '14 at 0:56
2
\$\begingroup\$

GolfScript, 84 characters

' '/.{?}:^;(~\2/{~~\~}/\{\?}:^;-1%'^'{[`{2$?0<!{@~\~@~`}*}+/]}:C~-1%'*/'C'+-'C~~-abs

This version does integer division and therefore yields a different result for the first test case. You may try the code here.

> 1 + 2 * 3 ^ 2 - 11 / 2 + 16
21

> 7 - 1 * 3 ^ 2 + 41 / 3 + 2 * 9 * 2
2167

Code with comments:

' '/.            # split the input at spaces and save a copy for each evaluation

# LTR evaluation
{?}:^;           # define ^ to be the power operator
(~\              # convert the left most string (first operand) into a number
2/{              # loop over the rest in pairs of two
  ~              #   split pair
  ~              #   evaluate second item of tuple (i.e. numeric operand)
  \~             #   apply the operator to two items on stack
}/               # end loop

# standard evaluation
\{\?}:^;         # redefine ^ to be the rtl power operator
-1%              # -1%  .... -1% reverse the input in order to handle right associativity
'^'
{                # {...}:C~ define code-block C and apply it to the string '^'
  [`{            # stringify the argument in order to add it to the internal
                 # code-block. afterwards loop over the input array and collect
                 # the results in an array
    2$?0<!       # if the second top item on the stack is one of the provided operators
    {            
      @~         #   take the first operand and convert to number
      \~         #   take the second operand and convert to number
      @~         #   apply the operator
      `          #   stringify result
    }*           # end if
  }+/]
}:C~
-1%

'*/'C            # afterwards apply the same code-block for operators * and /
'+-'C            # and then for operators + and -
~~               # flatten the resulting array and convert the result to a number

-abs             # take absolute difference between the two evaluation methods
\$\endgroup\$
2
\$\begingroup\$

Haskell, 281 256 characters

(x:o:y:z)%p|p o=(show(m o(read x)$read y::Float):z)%p|1<3=x:o:(y:z)%p;z%_=z
m"+"=(+);m"-"=(-);m"*"=(*);m"/"=(/);m"^"=(**);m _= \a->abs.(a-)
l=(%(\_->1<3))
t e=foldl(%)e$map(\w->(`elem`w).head)["^","*/","+-"]
d e=l$l e++"~":t e
main=interact$concat.d.words

Brief explaintaion:

  • % reduces an expression, so long as the operator meets some predicate p
  • show(m o(read x)$read y::Float) applies an operator to the two string arguments, producing a string result
  • m maps a string to an operator; note the string "~" is mapped to absolute difference
  • l computes left-to-right order by applying % once, with a predicate that is always true
  • t computes traditional order by repeatedly applying % with tests that match operators first of higher precedence, then lower
  • d computes the two values, then forms a new expression with operator ~ and computes that

Runs:

& echo "1 + 2 * 3 ^ 2 - 11 / 2 + 16" | runhaskell 34599-EvalOrder.hs 
21.5

& echo "7 - 1 * 3 ^ 2 + 41 / 3 + 2 * 9 * 2" | runhaskell 34599-EvalOrder.hs 
2178.3333

(Second result differs from example above because this code always computes in floating point.)

\$\endgroup\$
2
\$\begingroup\$

Perl 204 (203 + 1 for the -p flag)

LOL using eval got boring (s/\^/**/g;$_=eval"("x(()=/\d+/g).s/(\d+)/\1)/rg."-($_)") as I saw Calvin's Hobbies's comment on the eric_lagergren's answer so here's an non-eval method:

$d='([-\d.]+)';$s=$t=$_;map{$o=$_;$s=~s|$d (.) $d|($1*$3,$1+$3,0,$1-$3,$1**$3,$1/$3)[ord($2)%6]|e,$t=~s|$d ([\\$o]) $d|($1*$3,$1+$3,'',$1-$3,$1**$3,$1/$3)[ord($2)%6]|eg for$t=~/./g}'^/*-+'=~/./g;$_=$s-$t

Ungolfed:

# shortcut
$d = '([-\d.]+)';

# initial values for the traditional and sequential evaluation
$s = $t = $_;

# split the list of operators and loop throught them
map {
    # store current operator in $o
    $o=$_;

    # repeatedly evaluate the input string until the calculations are done
    for($t=~/./g) {
        # Here is an array with calculated all operators and I pick the correct element
        # ord($2)%6 is never 2 so I put 0 in that position of the array
        $s=~s|$d (.) $d|($1*$3,$1+$3,0,$1-$3,$1**$3,$1/$3)[ord($2)%6]|e;
        $t=~s|$d ([\\$o]) $d|($1*$3,$1+$3,'',$1-$3,$1**$3,$1/$3)[ord($2)%6]|eg
    }
} ('^/*-+'=~/./g);

# subtract the traditional evaluation form the in-order one
$_ = $s - $t

This solution uses floating point calculations.

Output:

$ PS1='\n\$ '

$ ./order.pl <<<"1 + 2 * 3 ^ 2 - 11 / 2 + 16"
21.5
$ ./order.pl <<<"7 - 1 * 3 ^ 2 + 41 / 3 + 2 * 9 * 2"
2178.33333333333
\$\endgroup\$
  • \$\begingroup\$ Why not read the question before writing the answer? "Your program can not use any sort of expression evaluation library" \$\endgroup\$ – edc65 Jul 16 '14 at 14:50
  • \$\begingroup\$ I literally meant a "library". Doing an "eval" procedure which treats a string as code from its own language is acceptable. Made this clarification yesterday. \$\endgroup\$ – Kyle McCormick Jul 18 '14 at 0:30
0
\$\begingroup\$

Python 208

d=x=input();z=2;u='('*(((len(x)-len(x.replace(' ','')))/2)+1);d=x=d.replace(r'^','**');x=x.split();p=u+''.join(")".join(x[i:i+z]) for i in range(0,len(x),z))+")";m=eval(p)-eval(d);m=m*-1 if 0>m else m;print m;

Calvin'sHobbies comment::

import re;e=input().replace('^','**');print abs(eval(e)-eval(e.count(' ')/2*'('+re.sub('(\d) ',r'\1)',e)))

Explanation:

# variable d  =  x, and x  =  user input

d = x = input() 

# variable z = 2

z = 2

# I take the length of the string 'x' (aka the equation we're solving) with 
# *all* whitespaces removed (it's the 'len(x.replace(' ', '')...' part) and 
# subtract that from 'len(x)' which is the vanilla length of our equation
# I divide the total by two and add one for reasons I'll explain in a minute
# the '(' * part means to make a string with as many '(' as I get from multiplying
# so '(' * 5 = '(((((', '(' * 3 = '((('

u = '(' * (((len(x) - len(x.replace(' ', ''))) / 2) + 1)

# Here I replace the caret with **, because in Python ^ == **
# I also split the string by whitespaces, but only for x;

d = x = d.replace(r'^','**'); x = x.split();

# I set the variable p = to the result of joining the list (aka array) that
# I just made with the .split() in the above section first with a ')' on every
# second character (e.g. [1,2,3,4,5,6] would be 1,2),3,4),... etc. I do it like
# this because in our math equation we'll (hopefully) follow the pattern of
# num op num op num op... etc. I insert parenthases because I'm using PEMDAS
# to my advantage by grouping each set of numbers in the order I want them
# to be completed. The initial ''.join simply rejoins all elements into a
# complete string (basically removes the commas that are left over from
# converting a list -> string). I add a '(' to the end because every 2nd
# character would skip the final one

p = u + ''.join(")".join(x[i:i + z]) for i in range(0, len(x), z)) + ")"

# I eval() both p and d. eval() will run arbitrary code, so you can pass it a
# string and it will act as if the string is code, so while print '1+1' would
# usually result in TypeError (or Value? I forget), print eval('1+1') would
# print '2', I have to do them separately because eval() thinks I wanna
# subtract two string for whatever reason

m = eval(p) - eval(d)

# Here I make use of Python's ternary operators by saying this:
# if 0 > m:
#   m = m * -1
# else:
#   m
# which means that if m is negative, multiply it by -1 to make it
# a positive number so we can get the absolute value. If it's not negative
# then we can just have m and not do anything with it

m = m * -1 if 0 > m else m

# Print m :)

print m
\$\endgroup\$
  • 1
    \$\begingroup\$ Wouldn't using eval not follow the rule "Your program can not use any sort of expression evaluation library"? \$\endgroup\$ – Calvin's Hobbies Jul 16 '14 at 7:22
  • \$\begingroup\$ @Calvin'sHobbies I assumed OP meant something like a module that purposely ignored PEMDAS or something like this:stackoverflow.com/questions/12540306/… \$\endgroup\$ – Eric Lagergren Jul 16 '14 at 7:49
  • \$\begingroup\$ If that's the case then here's a much shorter Python answer with 106 characters: import re;e=input().replace('^','**');print abs(eval(e)-eval(e.count(' ')/2*'('+re.sub('(\d) ',r'\1)',e))) \$\endgroup\$ – Calvin's Hobbies Jul 16 '14 at 8:00
  • \$\begingroup\$ @Calvin'sHobbies fiiiiiiine I'll re-write it... \$\endgroup\$ – Eric Lagergren Jul 16 '14 at 8:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.