Difference of expressions when evaluated in different orders

Question

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

Answer 1

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

Answer 2

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.)

Answer 3

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

Answer 4

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