Evaluating a string of simple mathematical expressions [closed]

Question

Challenge

Here is the challenge (of my own invention, though I wouldn't be surprised if it has previously appeared elsewhere on the web).

Write a function that takes a single argument that is a string representation of a simple mathematical expression and evaluates it as a floating point value. A "simple expression" may include any of the following: positive or negative decimal numbers, +, -, *, /, (, ). Expressions use (normal) infix notation. Operators should be evaluated in the order they appear, i.e. not as in BODMAS, though brackets should be correctly observed, of course. The function should return the correct result for any possible expression of this form. However, the function does not have to handle malformed expressions (i.e. ones with bad syntax).

Examples of expressions:

1 + 3 / -8                            = -0.5       (No BODMAS)
2*3*4*5+99                            = 219
4 * (9 - 4) / (2 * 6 - 2) + 8         = 10
1 + ((123 * 3 - 69) / 100)            = 4
2.45/8.5*9.27+(5*0.0023)              = 2.68...

Rules

I anticipate some form of "cheating"/craftiness here, so please let me forewarn against it! By cheating, I refer to the use of the eval or equivalent function in dynamic languages such as JavaScript or PHP, or equally compiling and executing code on the fly. (I think my specification of "no BODMAS" has pretty much guaranteed this however.) Apart from that, there are no restrictions. I anticipate a few Regex solutions here, but it would be nice to see more than just that.

Now, I'm mainly interested in a C#/.NET solution here, but any other language would be perfectly acceptable too (in particular, F# and Python for the functional/mixed approaches). I haven't yet decided whether I'm going to accept the shortest or most ingenious solution (at least for the language) as the answer, but I would welcome any form of solution in any language, except what I've just prohibited above!

My Solution

I've now posted my C# solution here (403 chars). Update: My new solution has beaten the old one significantly at 294 chars, with the help of a bit of lovely regex! I suspected that this will get easily beaten by some of the languages out there with lighter syntax (particularly the funcional/dynamic ones), and have been proved right, but I'd be curious if someone could beat this in C# still.

Update

I've seen some very crafty solutions already. Thanks to everyone who has posted one. Although I haven't tested any of them yet, I'm going to trust people and assume they at least work with all of the given examples.

Just for the note, re-entrancy (i.e. thread-safety) is not a requirement for the function, though it is a bonus.

---

Format

Please post all answers in the following format for the purpose of easy comparison:

Language

Number of characters: ???

Fully obfuscated function:

(code here)

Clear/semi-obfuscated function:

(code here)

Any notes on the algorithm/clever shortcuts it takes.

---

Antrorse

You probably meant your first example to equal .125 (move decimal place) and your second to have 99 on the left-hand side (one too many nines). – Raffinose

Yeah, thanks. Those were pretty glaring typos. – Antrorse

I've also made this community wiki (forgot to do so originally), since that would seem most appropiate for this style of question. – Antrorse

The funny thing here is by specifying no BODMAS you have eliminated the simplest solutions. In PHP: function calc($string) { return eval($string); } – Noun

@jmucchiello: Yes, I have indeed eliminated the simplest (cheat?) solutions! I mention in the question that I'm not really interested in seeing solutions using dynamic evaluation features (e.g. eval), so it's all good. :) – Antrorse

You ought to add an example where the lack of BODMAS is significant, e.g. "1 + 1 * 3 = 6" – Hare

@Ben: Good point. I will change one of them as such. – Antrorse

Ahh, I was wondering when the first vote to close would come. Note to all voters: there are plenty of open code golf questions in StackOverflow already. Consensus seems to be they're fine - mainly just a bit of fun. – Antrorse

I'm inclined to agree this is fine, especially as "wiki" – Adamec

Thanks for the moderator approval, Marc. :) – Antrorse

I suppose someone will do this in J in 25 characters. – Urbanna

I've been playing around with a couple of MATLAB solutions which might get close to 200 characters, but I can't really test them out until Monday. =( – Escarp

@gnovice: Ah, I have been waiting for a MATLAB solution. Would be good to see one - just post it when you can. – Antrorse

Kind of an odd question, in that you are looking for algorithms that make incorrect/unexpected results. If you don't obey BODMAS (I learned BEDMAS (E = exponents), then it isn't much use to people who want to program a proper algorithm. – Kolodgie

@Kibbee: Not really an odd question, if you understand it properly. I take it you're not familiar with code golf? The aim is purely to have a bit of fun in trying to code the shortest solution! Use in the "real world" is of no importance. I introduced the "no BODMAS" requirement for two reasons: a) to make the algorithms simpler (in the general case), b) to try to stop people just using "eval". Also, there's nothing "incorrect" about not following BODMAS - it's purely convention. (BODMAS and BEDMES are both acceptable by the way.) – Antrorse

Someone longer than I in the tooth should do a 6-character APL solution. – Insomnia

I think it's useful to add a perl tag now... – Rudie

Answer 1

Perl (no eval)

Number of characters: 167 106 (see below for the 106 character version)

Fully obfuscated function: (167 characters if you join these three lines into one)

sub e{my$_="($_[0])";s/\s//g;$n=q"(-?\d++(\.\d+)?+)";
@a=(sub{$1},1,sub{$3*$6},sub{$3+$6},4,sub{$3-$6},6,sub{$3/$6});
while(s:\($n\)|(?<=\()$n(.)$n:$a[7&ord$5]():e){}$_}

Clear/deobfuscated version:

sub e {
  my $_ = "($_[0])";
  s/\s//g;
  $n=q"(-?\d++(\.\d+)?+)"; # a regex for "number", including capturing groups
                           # q"foo" in perl means the same as 'foo'
                           # Note the use of ++ and ?+ to tell perl
                           # "no backtracking"

  @a=(sub{$1},             # 0 - no operator found
      1,                   # placeholder
      sub{$3*$6},          # 2 - ord('*') = 052
      sub{$3+$6},          # 3 - ord('+') = 053
      4,                   # placeholder
      sub{$3-$6},          # 5 - ord('-') = 055
      6,                   # placeholder
      sub{$3/$6});         # 7 - ord('/') = 057

  # The (?<=... bit means "find a NUM WHATEVER NUM sequence that happens
  # immediately after a left paren", without including the left
  # paren.  The while loop repeatedly replaces "(" NUM WHATEVER NUM with
  # "(" RESULT and "(" NUM ")" with NUM.  The while loop keeps going
  # so long as those replacements can be made.

  while(s:\($n\)|(?<=\()$n(.)$n:$a[7&ord$5]():e){}

  # A perl function returns the value of the last statement
  $_
}

I had misread the rules initially, so I'd submitted a version with "eval". Here's a version without it.

The latest bit of insight came when I realized that the last octal digit in the character codes for +, -, /, and * is different, and that ord(undef) is 0. This lets me set up the dispatch table @a as an array, and just invoke the code at the location 7 & ord($3).

There's an obvious spot to shave off one more character - change q"" into '' - but that would make it harder to cut-and-paste into the shell.

Even shorter

Number of characters: 124 106

Taking edits by ephemient into account, it's now down to 124 characters: (join the two lines into one)

sub e{$_=$_[0];s/\s//g;$n=q"(-?\d++(\.\d+)?+)";
1while s:\($n\)|$n(.)$n:($1,1,$3*$6,$3+$6,4,$3-$6,6,$6&&$3/$6)[7&ord$5]:e;$_}

Shorter still

Number of characters: 110 106

The ruby solution down below is pushing me further, though I can't reach its 104 characters:

sub e{($_)=@_;$n='( *-?[.\d]++ *)';
s:\($n\)|$n(.)$n:(($1,$2-$4,$4&&$2/$4,$2*$4,$2+$4)x9)[.8*ord$3]:e?e($_):$_}

I had to give in and use ''. That ruby send trick is really useful for this problem.

Squeezing water from a stone

Number of characters: 106

A small contortion to avoid the divide-by-zero check.

sub e{($_)=@_;$n='( *-?[.\d]++ *)';
s:\($n\)|$n(.)$n:($1,0,$2*$4,$2+$4,0,$2-$4)[7&ord$3]//$2/$4:e?e($_):$_}

Here's the test harness for this function:

perl -le 'sub e{($_)=@_;$n='\''( *-?[.\d]++ *)'\'';s:\($n\)|$n(.)$n:($1,0,$2*$4,$2+$4,0,$2-$4)[7&ord$3]//$2/$4:e?e($_):$_}' -e 'print e($_) for @ARGV' '1 + 3' '1 + ((123 * 3 - 69) / 100)' '4 * (9 - 4) / (2 * 6 - 2) + 8' '2*3*4*5+99' '2.45/8.5*9.27+(5*0.0023) ' '1 + 3 / -8'

Grad

That's craziness. I suppose the the original code golf language ought to have beaten them all here, and indeed it has. I can't say I much like the abundance of regex, but good job! I might just have to accept this as answer... – Antrorse

thats crafty using ord. I like how you've used $n as a way to duplicate a section of the regular expression. – Huihuie

Is there a reason you use "local" when "my" should work just as well? – Insomnia

@Chris Lutz: No, so I changed it and lost three more characters. Just the force of powerful habit telling me to use "local" with global variables. – Grad

Ugh... in my edit, qw// was supposed to be qr//. Since that (accidentally) works, you could shave another 2 characters off by replacing it with ''. – Boser

In fact, ephemient, I was already doing that (using q""). But nice trick to avoid all the "sub" noise. – Grad

That's impressive - you shaved it down AND added in divide-by-zero protection. I was going to suggest using "1 while" instead of "while(){}", but I didn't know that 1while (without the space) would parse correctly, so it didn't save any space. Glad it works. – Insomnia

It's pretty scary how small Perl can go, I edited my answer to keep it the smallest Ruby implementation and ran out of room at 170 chars. But 124? Good gravy! – Lyonnaise

I didn't notice that nobody has mentioned it yet, but this solution requires Perl 5.10. For compatibility with 5.8, use (-?(?>\d+(\.\d+)?)) which is two characters longer. – Boser

@Epaga, don't worry I got your typo: perl. is. awesome. – Arrowroot

Shorten it by 1 character - change "$_=$_[0]" to "($_)=@_". – Insomnia

Do you really need to check for division by zero? Most of the solutions (including mine) do not. – Polonium

Because it unconditionally performs the arithmetic regardless of the operator (picking the correct result later), it does need to avoid dividing by zero. – Boser

Used another Perl 5.10 trick to cut the character count a little more, but geez, this is getting really tough. Getting to 103 will not be easy. – Boser

Dare I tempt you to break 100? :P No really, please don't spend any more time on it unless you absolutely want to (for yourself)! It's a great solution as it is - certainly good enough for me. – Antrorse

It's more like a stubborn refusal to believe that Perl could be permanently beaten by its younger cousin Ruby, but yeah, it's not really a productive use of time... – Boser

I found a way to make it shorter, but it doesn't work. Negative array indices in Perl wrap once, but if they wrap past the end of the array, they don't keep wrapping. Otherwise, I could have had it to 105. (It lined up perfectly, too, which is really bothering me - if it kept wrapping, element -42 would have ended up as index 2, and it would have worked perfectly.) – Insomnia

Answer 2

Assembler

427 bytes

Obfuscated, assembled with the excellent A86 into a .com executable:

dd 0db9b1f89h, 081bee3h, 0e8af789h, 0d9080080h, 0bdac7674h, 013b40286h
dd 07400463ah, 0ccfe4508h, 08ce9f675h, 02fc8000h, 013b0057eh, 0feaac42ah
dd 0bedf75c9h, 0ba680081h, 04de801h, 04874f73bh, 04474103ch, 0e8e8b60fh
dd 08e8a003fh, 0e880290h, 0de0153h, 08b57e6ebh, 0d902a93eh, 046d891dh
dd 08906c783h, 05f02a93eh, 03cffcee8h, 057197510h, 02a93e8bh, 08b06ef83h
dd 05d9046dh, 02a93e89h, 03bc9d95fh, 0ac0174f7h, 074f73bc3h, 0f3cac24h
dd 0eed9c474h, 0197f0b3ch, 07cc4940fh, 074f73b09h, 0103cac09h, 0a3ce274h
dd 0e40a537eh, 0e0d90274h, 02a3bac3h, 021cd09b4h, 03e8b20cdh, 0ff8102a9h
dd 0ed7502abh, 0474103ch, 0e57d0b3ch, 0be02a3bfh, 014d903a3h, 0800344f6h
dd 02db00574h, 0d9e0d9aah, 0d9029f2eh, 0bb34dfc0h, 08a0009h, 01c75f0a8h
dd 020750fa8h, 0b0f3794bh, 021e9aa30h, 0de607400h, 08802990eh, 0de07df07h
dd 0c392ebc1h, 0e8c0008ah, 0aa300404h, 0f24008ah, 04baa3004h, 02eb0ee79h
dd 03005c6aah, 0c0d90ab1h, 0e9defcd9h, 02a116deh, 0e480e0dfh, 040fc8045h
dd 0ede1274h, 0c0d90299h, 015dffcd9h, 047300580h, 0de75c9feh, 0303d804fh
dd 03d80fa74h, 04f01752eh, 0240145c6h, 0dfff52e9h, 0d9029906h, 0f73b025fh
dd 03caca174h, 07fed740ah, 0df07889ah, 0277d807h, 047d9c1deh, 0990ede02h
dd 025fd902h, 03130e0ebh, 035343332h, 039383736h, 02f2b2d2eh, 02029282ah
dd 0e9000a09h, 07fc9f9c1h, 04500000fh, 0726f7272h
db 024h, 0abh, 02h

EDIT: Unobfuscated source:

        mov [bx],bx
        finit
        mov si,81h
        mov di,si
        mov cl,[80h]
        or cl,bl
        jz ret
    l1:
        lodsb
        mov bp,d1
        mov ah,19
    l2:
        cmp al,[bp]
        je l3
        inc bp
        dec ah
        jne l2
        jmp exit
    l3:
        cmp ah,2
        jle l4
        mov al,19
        sub al,ah
        stosb
    l4:
        dec cl
        jnz l1
        mov si,81h
        push done

    decode:
    l5:
        call l7
    l50:
        cmp si,di
        je ret
        cmp al,16
        je ret
        db 0fh, 0b6h, 0e8h ; movzx bp,al
        call l7
        mov cl,[bp+op-11]
        mov byte ptr [sm1],cl
        db 0deh
    sm1:db ?
        jmp l50

    open:
        push di
        mov di,word ptr [s]
        fstp dword ptr [di]
        mov [di+4],bp
        add di,6
        mov word ptr [s],di
        pop di
        call decode
        cmp al,16
        jne ret
        push di
        mov di,word ptr [s]
        sub di,6
        mov bp,[di+4]
        fld dword ptr [di]
        mov word ptr [s],di
        pop di
        fxch st(1)
        cmp si,di
        je ret
        lodsb
        ret



    l7: cmp si,di
        je exit
        lodsb
        cmp al,15
        je open
        fldz
        cmp al,11
        jg exit
        db 0fh, 94h, 0c4h ; sete ah 
        jl l10
    l9:
        cmp si,di
        je l12
        lodsb
        cmp al,16
        je ret
    l10:
        cmp al,10
        jle l12i

    l12:
        or ah,ah
        je l13
        fchs
    l13:
        ret

    exit:
        mov dx,offset res
        mov ah,9
        int 21h
        int 20h

    done:
        mov di,word ptr [s]
        cmp di,(offset s)+2
        jne exit
        cmp al,16
        je ok
        cmp al,11
        jge exit
    ok:
        mov di,res
        mov si,res+100h
        fst dword ptr [si]
        test byte ptr [si+3],80h
        jz pos
        mov al,'-'
        stosb
        fchs
    pos:
        fldcw word ptr [cw]
        fld st(0)
        fbstp [si]
        mov bx,9
    l1000:
        mov al,[si+bx]
        test al,0f0h
        jne startu
        test al,0fh
        jne startl
        dec bx
        jns l1000
        mov al,'0'
        stosb
        jmp frac

    l12i:
        je l11
        fimul word ptr [d3]
        mov [bx],al
        fild word ptr [bx]
        faddp
        jmp l9
        ret

    startu:
        mov al,[si+bx]
        shr al,4
        add al,'0'
        stosb
    startl:
        mov al,[si+bx]
        and al,0fh
        add al,'0'
        stosb
        dec bx
        jns startu

    frac:
        mov al,'.'
        stosb
        mov byte ptr [di],'0'
        mov cl,10
        fld st(0)
        frndint
    frac1:  
        fsubp st(1)
        ficom word ptr [zero]
        fstsw ax
        and ah,045h
        cmp ah,040h
        je finished
        fimul word ptr [d3]
        fld st(0)
        frndint
        fist word ptr [di]
        add byte ptr [di],'0'
        inc di
        dec cl
        jnz frac1

    finished:   
        dec di
        cmp byte ptr [di],'0'
        je finished
        cmp byte ptr [di],'.'
        jne f2
        dec di
    f2:
        mov byte ptr [di+1],'$'
    exit2:
        jmp exit


    l11:
        fild word ptr [d3]
        fstp dword ptr [bx+2]
    l111:
        cmp si,di
        je ret
        lodsb
        cmp al,10
        je exit2
        jg ret
        mov [bx],al
        fild word ptr [bx]
        fdiv dword ptr [bx+2]
        faddp
        fld dword ptr [bx+2]
        fimul word ptr [d3]
        fstp dword ptr [bx+2]
        jmp l111


    d1: db '0123456789.-+/*()', 32, 9
    d3: dw 10
    op: db 0e9h, 0c1h, 0f9h, 0c9h
    cw: dw 0f7fh
    zero: dw 0
    res:db 'Error$'
    s:  dw (offset s)+2

Resale

Assembly - this is real programming! – Propylite

I once saw a full tetris game in 64 bytes – Repetend

Answer 3

C (VS2005)

Number of Characters: 1360

Abuse of preprocessor and warnings for fun code layout (scroll down to see):

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define b main
#define c(a) b(a,0)
#define d -1
#define e -2
#define g break
#define h case
#define hh h
#define hhh h
#define w(i) case i
#define i return
#define j switch
#define k float
#define l realloc
#define m sscanf
#define n int _
#define o char
#define t(u) #u
#define q(r) "%f" t(r)  "n"
#define s while
#define v default
#define ex exit
#define W printf
#define x fn()
#define y strcat
#define z strcpy
#define Z strlen

char*p    =0    ;k    *b    (n,o**    a){k*f
;j(_){    hh   e:     i*    p==40?    (++p,c
(d        ))  :(      f=        l(        0,
4)        ,m (p       ,q        (%        ),
f,&_),    p+=_        ,f       );        hh
d:f=c(    e);s        (1      ){        j(
    *p    ++ ){       hh     0:        hh
    41    :i  f;      hh    43        :*
f+=*c(    e)   ;g     ;h    45:*f=    *f-*c(
e);g;h    42    :*    f=    *f**c(    e);g;h

47:*f      /=*c      (e);     g;   v:    c(0);}
}w(1):    if(p&&    printf    (q  ((     "\\"))
,*  c(    d)  ))    g;  hh    0: ex      (W
(x  ))    ;v  :p    =(        p?y:       z)(l(p
,Z(1[     a]  )+    (p        ?Z(p           )+
1:1))     ,1  [a    ])  ;b    (_ -1          ,a
+1  );    g;  }i    0;};fn    ()  {n     =42,p=
43  ;i     "Er"      "ro"     t(   r)    "\n";}

Resale

Answer 4

Ruby

Number of characters: 103

N='( *-?[\d.]+ *)'
def e x
x.sub!(/\(#{N}\)|#{N}([^.\d])#{N}/){$1or(e$2).send$3,e($4)}?e(x):x.to_f
end

This is a non-recursive version of The Wicked Flea's solution. Parenthesized sub-expressions are evaluated bottom-up instead of top-down.

Edit: Converting the 'while' to a conditional + tail recursion has saved a few characters, so it is no longer non-recursive (though the recursion is not semantically necessary.)

Edit: Borrowing Daniel Martin's idea of merging the regexps saves another 11 characters!

Edit: That recursion is even more useful than I first thought! x.to_f can be rewritten as e(x), if x happens to contain a single number.

Edit: Using 'or' instead of '||' allows a pair of parentheses to be dropped.

Long version:

# Decimal number, as a capturing group, for substitution
# in the main regexp below.
N='( *-?[\d.]+ *)'

# The evaluation function
def e(x)
  matched = x.sub!(/\(#{N}\)|#{N}([^\d.])#{N}/) do
    # Group 1 is a numeric literal in parentheses.  If this is present then
    # just return it.
    if $1
      $1
    # Otherwise, $3 is an operator symbol and $2 and $4 are the operands
    else
      # Recursively call e to parse the operands (we already know from the
      # regexp that they are numeric literals, and this is slightly shorter
      # than using :to_f)
      e($2).send($3, e($4))
      # We could have converted $3 to a symbol ($3.to_s) or converted the
      # result back to string form, but both are done automatically anyway
    end
  end
  if matched then
    # We did one reduction. Now recurse back and look for more.
    e(x)
  else
    # If the string doesn't look like a non-trivial expression, assume it is a
    # string representation of a real number and attempt to parse it
    x.to_f
  end
end

Polonium

I almost thought this was the new leader until I saw the Perl one had been edited to become even shorter! Good job, anyway. – Antrorse

Getting rid of 'e=readline.chomp;...;p e.to_f' and using 'def q(e);...;e.to_f;end' like the other solutions would save 10 characters. However, it fails to q("1 + 3 / -8")==-0.5 as in the question. – Boser

@Boser that's a bug you found - it could not handle negative numbers. – Polonium

The gsub!('--','') in my code is for how the parenthetical argument works, if negated. If the result of the interior of a negated parenthetical is negative the minus outside the statement remains: --7.0, for example. However, supporting that costs me 24 characters, still 19 above you. I don't know that I can shrink it any more than the tricks I learned from you. (But I did great for a 2nd try!) – Lyonnaise

Using "send" is really coming close to violating the "no eval" rule. But nice trick incorporating the spaces into your number regex. Using that trick and another one got my perl solution down to 119 characters. – Grad

Perl's down to 107 now, but that's still 4 + 103... – Boser

Answer 5

Visual Basic.NET

Number of characters: 9759

I'm more of a bowler myself.

NOTE: does not take nested parentheses into account. Also, untested, but I'm pretty sure it works.

Imports Microsoft.VisualBasic
Imports System.Text
Imports System.Collections.Generic
Public Class Main
Public Shared Function DoArithmaticFunctionFromStringInput(ByVal MathematicalString As String) As Double
    Dim numberList As New List(Of Number)
    Dim operationsList As New List(Of IOperatable)
    Dim currentNumber As New Number
    Dim currentParentheticalStatement As New Parenthetical
    Dim isInParentheticalMode As Boolean = False
    Dim allCharactersInString() As Char = MathematicalString.ToCharArray
    For Each mathChar In allCharactersInString
        If mathChar = Number.ZERO_STRING_REPRESENTATION Then
            currentNumber.UpdateNumber(mathChar)
        ElseIf mathChar = Number.ONE_STRING_REPRESENTATION Then
            currentNumber.UpdateNumber(mathChar)
        ElseIf mathChar = Number.TWO_STRING_REPRESENTATION Then
            currentNumber.UpdateNumber(mathChar)
        ElseIf mathChar = Number.THREE_STRING_REPRESENTATION Then
            currentNumber.UpdateNumber(mathChar)
        ElseIf mathChar = Number.FOUR_STRING_REPRESENTATION Then
            currentNumber.UpdateNumber(mathChar)
        ElseIf mathChar = Number.FIVE_STRING_REPRESENTATION Then
            currentNumber.UpdateNumber(mathChar)
        ElseIf mathChar = Number.SIX_STRING_REPRESENTATION Then
            currentNumber.UpdateNumber(mathChar)
        ElseIf mathChar = Number.SEVEN_STRING_REPRESENTATION Then
            currentNumber.UpdateNumber(mathChar)
        ElseIf mathChar = Number.EIGHT_STRING_REPRESENTATION Then
            currentNumber.UpdateNumber(mathChar)
        ElseIf mathChar = Number.NINE_STRING_REPRESENTATION Then
            currentNumber.UpdateNumber(mathChar)
        ElseIf mathChar = Number.DECIMAL_POINT_STRING_REPRESENTATION Then
            currentNumber.UpdateNumber(mathChar)
        ElseIf mathChar = Addition.ADDITION_STRING_REPRESENTATION Then
            Dim addition As New Addition

            If Not isInParentheticalMode Then
                operationsList.Add(addition)
                numberList.Add(currentNumber)
            Else
                currentParentheticalStatement.AllNumbers.Add(currentNumber)
                currentParentheticalStatement.AllOperators.Add(addition)
            End If

            currentNumber = New Number
        ElseIf mathChar = Number.NEGATIVE_NUMBER_STRING_REPRESENTATION Then
            If currentNumber.StringOfNumbers.Length > 0 Then
                currentNumber.UpdateNumber(mathChar)

                Dim subtraction As New Addition
                If Not isInParentheticalMode Then
                    operationsList.Add(subtraction)
                    numberList.Add(currentNumber)
                Else
                    currentParentheticalStatement.AllNumbers.Add(currentNumber)
                    currentParentheticalStatement.AllOperators.Add(subtraction)
                End If

                currentNumber = New Number
            Else
                currentNumber.UpdateNumber(mathChar)
            End If
        ElseIf mathChar = Multiplication.MULTIPLICATION_STRING_REPRESENTATION Then
            Dim multiplication As New Multiplication

            If Not isInParentheticalMode Then
                operationsList.Add(multiplication)
                numberList.Add(currentNumber)
            Else
                currentParentheticalStatement.AllNumbers.Add(currentNumber)
                currentParentheticalStatement.AllOperators.Add(multiplication)
            End If
            currentNumber = New Number
        ElseIf mathChar = Division.DIVISION_STRING_REPRESENTATION Then
            Dim division As New Division

            If Not isInParentheticalMode Then
                operationsList.Add(division)
                numberList.Add(currentNumber)
            Else
                currentParentheticalStatement.AllNumbers.Add(currentNumber)
                currentParentheticalStatement.AllOperators.Add(division)
            End If
            currentNumber = New Number
        ElseIf mathChar = Parenthetical.LEFT_PARENTHESIS_STRING_REPRESENTATION Then
            isInParentheticalMode = True
        ElseIf mathChar = Parenthetical.RIGHT_PARENTHESIS_STRING_REPRESENTATION Then
            currentNumber = currentParentheticalStatement.EvaluateParentheticalStatement
            numberList.Add(currentNumber)
            isInParentheticalMode = False
        End If
    Next

    Dim result As Double = 0
    Dim operationIndex As Integer = 0
    For Each numberOnWhichToPerformOperations As Number In numberList
        result = operationsList(operationIndex).PerformOperation(result, numberOnWhichToPerformOperations)
        operationIndex = operationIndex + 1
    Next

    Return result

End Function
Public Class Number
    Public Const DECIMAL_POINT_STRING_REPRESENTATION As Char = "."
    Public Const NEGATIVE_NUMBER_STRING_REPRESENTATION As Char = "-"
    Public Const ZERO_STRING_REPRESENTATION As Char = "0"
    Public Const ONE_STRING_REPRESENTATION As Char = "1"
    Public Const TWO_STRING_REPRESENTATION As Char = "2"
    Public Const THREE_STRING_REPRESENTATION As Char = "3"
    Public Const FOUR_STRING_REPRESENTATION As Char = "4"
    Public Const FIVE_STRING_REPRESENTATION As Char = "5"
    Public Const SIX_STRING_REPRESENTATION As Char = "6"
    Public Const SEVEN_STRING_REPRESENTATION As Char = "7"
    Public Const EIGHT_STRING_REPRESENTATION As Char = "8"
    Public Const NINE_STRING_REPRESENTATION As Char = "9"

    Private _isNegative As Boolean
    Public ReadOnly Property IsNegative() As Boolean
        Get
            Return _isNegative
        End Get
    End Property
    Public ReadOnly Property ActualNumber() As Double
        Get
            Dim result As String = ""
            If HasDecimal Then
                If DecimalIndex = StringOfNumbers.Length - 1 Then
                    result = StringOfNumbers.ToString
                Else
                    result = StringOfNumbers.Insert(DecimalIndex, DECIMAL_POINT_STRING_REPRESENTATION).ToString
                End If
            Else
                result = StringOfNumbers.ToString
            End If
            If IsNegative Then
                result = NEGATIVE_NUMBER_STRING_REPRESENTATION & result
            End If
            Return CType(result, Double)
        End Get
    End Property
    Private _hasDecimal As Boolean
    Public ReadOnly Property HasDecimal() As Boolean
        Get
            Return _hasDecimal
        End Get
    End Property
    Private _decimalIndex As Integer
    Public ReadOnly Property DecimalIndex() As Integer
        Get
            Return _decimalIndex
        End Get
    End Property
    Private _stringOfNumbers As New StringBuilder
    Public ReadOnly Property StringOfNumbers() As StringBuilder
        Get
            Return _stringOfNumbers
        End Get
    End Property
    Public Sub UpdateNumber(ByVal theDigitToAppend As Char)
        If IsNumeric(theDigitToAppend) Then
            Me._stringOfNumbers.Append(theDigitToAppend)
        ElseIf theDigitToAppend = DECIMAL_POINT_STRING_REPRESENTATION Then
            Me._hasDecimal = True
            Me._decimalIndex = Me._stringOfNumbers.Length
        ElseIf theDigitToAppend = NEGATIVE_NUMBER_STRING_REPRESENTATION Then
            Me._isNegative = Not Me._isNegative
        End If
    End Sub
    Public Shared Function ConvertDoubleToNumber(ByVal numberThatIsADouble As Double) As Number
        Dim numberResult As New Number
        For Each character As Char In numberThatIsADouble.ToString.ToCharArray
            numberResult.UpdateNumber(character)
        Next
        Return numberResult
    End Function
End Class
Public MustInherit Class Operation
    Protected _firstnumber As New Number
    Protected _secondnumber As New Number
    Public Property FirstNumber() As Number
        Get
            Return _firstnumber
        End Get
        Set(ByVal value As Number)
            _firstnumber = value
        End Set
    End Property
    Public Property SecondNumber() As Number
        Get
            Return _secondnumber
        End Get
        Set(ByVal value As Number)
            _secondnumber = value
        End Set
    End Property
End Class
Public Interface IOperatable
    Function PerformOperation(ByVal number1 As Double, ByVal number2 As Number) As Double
End Interface
Public Class Addition
    Inherits Operation
    Implements IOperatable
    Public Const ADDITION_STRING_REPRESENTATION As String = "+"
    Public Sub New()

    End Sub
    Public Function PerformOperation(ByVal number1 As Double, ByVal number2 As Number) As Double Implements IOperatable.PerformOperation
        Dim result As Double = 0
        result = number1 + number2.ActualNumber
        Return result
    End Function
End Class
Public Class Multiplication
    Inherits Operation
    Implements IOperatable
    Public Const MULTIPLICATION_STRING_REPRESENTATION As String = "*"
    Public Sub New()

    End Sub
    Public Function PerformOperation(ByVal number1 As Double, ByVal number2 As Number) As Double Implements IOperatable.PerformOperation
        Dim result As Double = 0
        result = number1 * number2.ActualNumber
        Return result
    End Function
End Class
Public Class Division
    Inherits Operation
    Implements IOperatable
    Public Const DIVISION_STRING_REPRESENTATION As String = "/"
    Public Const DIVIDE_BY_ZERO_ERROR_MESSAGE As String = "I took a lot of time to write this program. Please don't be a child and try to defile it by dividing by zero. Nobody thinks you are funny."
    Public Sub New()

    End Sub
    Public Function PerformOperation(ByVal number1 As Double, ByVal number2 As Number) As Double Implements IOperatable.PerformOperation
        If Not number2.ActualNumber = 0 Then
            Dim result As Double = 0
            result = number1 / number2.ActualNumber
            Return result
        Else
            Dim divideByZeroException As New Exception(DIVIDE_BY_ZERO_ERROR_MESSAGE)
            Throw divideByZeroException
        End If
    End Function
End Class
Public Class Parenthetical
    Public Const LEFT_PARENTHESIS_STRING_REPRESENTATION As String = "("
    Public Const RIGHT_PARENTHESIS_STRING_REPRESENTATION As String = ")"
    Private _allNumbers As New List(Of Number)
    Public Property AllNumbers() As List(Of Number)
        Get
            Return _allNumbers
        End Get
        Set(ByVal value As List(Of Number))
            _allNumbers = value
        End Set
    End Property
    Private _allOperators As New List(Of IOperatable)
    Public Property AllOperators() As List(Of IOperatable)
        Get
            Return _allOperators
        End Get
        Set(ByVal value As List(Of IOperatable))
            _allOperators = value
        End Set
    End Property
    Public Sub New()

    End Sub
    Public Function EvaluateParentheticalStatement() As Number
        Dim result As Double = 0
        Dim operationIndex As Integer = 0
        For Each numberOnWhichToPerformOperations As Number In AllNumbers
            result = AllOperators(operationIndex).PerformOperation(result, numberOnWhichToPerformOperations)
            operationIndex = operationIndex + 1
        Next

        Dim numberToReturn As New Number
        numberToReturn = Number.ConvertDoubleToNumber(result)
        Return numberToReturn
    End Function
End Class
End Class

Hydroscope

I also probably could have hit 10k characters if it weren't so late at night :) – Hydroscope

Do you know less characters is better? This way they never think vb.net is any good. – Annabell

@ikke - it was supposed to be as FEW characters as possible? oh dear... someone seems to have missed the point – Hydroscope

ZERO_STRING_REPRESENTATION looks like something that belongs on thedailywtf – Vaccine

@lkke - I think that is the point. See comment from finnw. – Triciatrick

+1 this made me laugh more than any other answer on SO. ever. – Hacking

Answer 6

Haskell

Number of characters: 182

No attempt at cleverness, just some compression: 4 lines, 312 bytes.

import Data.Char;import Text.ParserCombinators.Parsec
q=either(error.show)id.runParser t id"".filter(' '/=);t=do
s<-getState;a<-fmap read(many1$oneOf".-"<|>digit)<|>between(char '('>>setState id)(char ')'>>setState s)t
option(s a)$choice(zipWith(\c o->char c>>return(o$s a))"+-*/"[(+),(-),(*),(/)])>>=setState>>t

And now, really getting into the golf spirit, 3 lines and 182 bytes:

q=snd.(`e`id).filter(' '/=)
e s c|[(f,h)]<-readsPrec 0 s=g h(c f);e('(':s)c=g h(c f)where(')':h,f)=e s id
g('+':h)=e h.(+);g('-':h)=e h.(-);g('*':h)=e h.(*);g('/':h)=e h.(/);g h=(,)h

Exploded:

-- Strip spaces from the input, evaluate with empty accumulator,
-- and output the second field of the result.
q :: String -> Double
q = snd . flip eval id . filter (not . isSpace)

-- eval takes a string and an accumulator, and returns
-- the final value and what’s left unused from the string.
eval :: (Fractional a, Read a) => String -> (a -> a) -> (String, a)

-- If the beginning of the string parses as a number, add it to the accumulator,
-- then try to read an operator and further.
eval str accum | [(num, rest)] <- readsPrec 0 str = oper rest (accum num)

-- If the string starts parentheses, evaluate the inside with a fresh
-- accumulator, and continue after the closing paren.
eval ('(':str) accum = oper rest (accum num) where (')':rest, num) = eval str id

-- oper takes a string and current value, and tries to read an operator
-- to apply to the value.  If there is none, it’s okay.
oper :: (Fractional a, Read a) => String -> a -> (String, a)

-- Handle operations by giving eval a pre-seeded accumulator.
oper ('+':str) num = eval str (num +)
oper ('-':str) num = eval str (num -)
oper ('*':str) num = eval str (num *)
oper ('/':str) num = eval str (num /)

-- If there’s no operation parsable, just return.
oper str num = (str, num)

Boser

I suspect that it may still be possible to get below 225, but this is as far as I can get at 3am. – Boser

That appears to be quite an elegant functional solution. (One that I certainly wouldn't have understand without the comments, so thanks for those.) Also, you're just marginally ahead of Dave's Python solution at the moment, so you seem to be leading! I'd be curious if an F# solution could match or even beat this. – Antrorse

It's interesting to me that the Parsec solution (parser combinators = generalized regex + more), even if minimization was attempted, doesn't come close to the hand-rolled parsing. I don't think F#'s syntax can be as concise as Haskell, but I'd welcome some competition too :) – Boser

@ephemient: I tried using both regex and the parser module in Python quickly. Was almost immediately below 300 chars, but saw no chance to get competitive. The issue is the import and the function calls eat up too much. That is true for most languages (exception Perl). BTW, you don't have to parse yourself to get substantially below 300 chars, as my solution shows. – Denudation

I think you're over penalizing your character count. The problem asked for a String->Double function, so you should count characters by replacing "main=interact$show." with "q=", for 17 more characters, putting your count at 209. – Grad

Answer 7

Python

Number of characters: 237

Fully obfuscated function:

from operator import*
def e(s,l=[]):
 if s:l+=list(s.replace(' ','')+')')
 a=0;o=add;d=dict(zip(')*+-/',(0,mul,o,sub,div)));p=l.pop
 while o:
  c=p(0)
  if c=='(':c=e(0)
  while l[0]not in d:c+=p(0)
  a=o(a,float(c));o=d[p(0)]
 return a

Clear/semi-obfuscated function:

import operator

def calc(source, stack=[]):
    if source:
        stack += list(source.replace(' ', '') + ')')

    answer = 0

    ops = {
        ')': 0,
        '*': operator.mul,
        '+': operator.add,
        '-': operator.sub,
        '/': operator.div,
    }

    op = operator.add
    while op:
        cur = stack.pop(0)

        if cur == '(':
            cur = calc(0)

        while stack[0] not in ops:
            cur += stack.pop(0)

        answer = op(answer, float(cur))
        op = ops[stack.pop(0)]

    return answer

Overawe

Note: the current version doesn't handle an input like -(1.0) though it does handle negative literals correctly. It wasn't clear from the spec if this is required. – Overawe

One can make l non-global for free by tucking it into the parameter list of e. Still won't be thread-safe, however. – Overawe

Very cunning. That was well worth the effort of interpreting. :) – Propensity

@Dave: Mine fails on -(1.0) too, so no worries! I'll clarify the question. Anyway, very clever solution it seems - I'm still trying to figure out how it works though (not exactly knowing Python). If you could add a brief explanation, that would be much appreciated. – Antrorse

Answer 8

Fortran 77 (gfortran dialect, now with g77 support)

Number of characters: 2059

Obfuscated version:

      function e(c)
      character*99 c
      character b
      real f(24)                
      integer i(24)             
      nf=0                      
      ni=0                      
 20   nf=kf(0.0,nf,f)
      ni=ki(43,ni,i)         
 30   if (isp(c).eq.1) goto 20
      h=fr(c)
 31   g=fp(nf,f)
      j=ip(ni,i)
      select case(j)
      case (40) 
         goto 20
      case (42)                 
         d=g*h
      case (43)                 
         d=g+h
      case (45)                 
         d=g-h
      case (47)                 
         d=g/h
      end select
 50   nf=kf(d,nf,f)
 60   j=nop(c)
      goto (20, 70, 75, 75, 60, 75, 60, 75) (j-39)
 65   e=fp(nf,f)
      return
 70   h=fp(nf,f)              
      goto 31
 75   ni=ki(j,ni,i)
      goto 30
      end
      function kf(v,n,f)
      real f(24)
      kf=n+1
      f(n+1)=v
      return
      end
      function ki(j,n,i)
      integer i(24)
      ki=n+1
      i(n+1)=j
      return
      end
      function fp(n,f)
      real f(24)
      fp=f(n)
      n=n-1
      return
      end
      function ip(n,i)
      integer i(24)
      ip=i(n)
      n=n-1
      return
      end
      function nop(s)
      character*99 s
      l=1
      do while(s(l:l).eq." ".and.l.lt.99)
         l=l+1
      enddo
      nop=ichar(s(l:l))
      s(l:l)=" "
      return
      end
      function isp(s)
      character*99 s
      isp=0
      l=1
      do while(s(l:l).eq." ".and.l.lt.99)
         l=l+1
      enddo
      isp=41-ichar(s(l:l))
      if (isp.eq.1) s(l:l)=" "
      return
      end
      function fr(s)
      character*99 s
      m=1                      
      n=1                      
      i=1
      do while(i.le.99)
         j=ichar(s(i:i))
         if (j.eq.32) goto 90   
         if (j.ge.48.and.j.lt.58) goto 89
         if (j.eq.43.or.j.eq.45) goto (89,80) m
         if (j.eq.46) goto (83,80) n
 80      exit
 83      n=2
 89      m=2
 90      i=i+1
      enddo
      read(s(1:i-1),*) fr
      do 91 j=1,i-1
         s(j:j)=" "
 91   continue
      return 
      end

Clear version: (3340 characters with scaffold)

      program infixeval
      character*99 c
      do while (.true.)
         do 10 i=1,99
            c(i:i)=" "
 10      continue
         read(*,"(A99)") c
         f=e(c)
         write(*,*)f
      enddo
      end

      function e(c)
      character*99 c
      character b
      real f(24)                ! value stack
      integer i(24)             ! operator stack
      nf=0                      ! number of items on the value stack
      ni=0                      ! number of items on the operator stack
 20   nf=pushf(0.0,nf,f)
      ni=pushi(43,ni,i)         ! ichar(+) = 43
D     write (*,*) "'",c,"'"
 30   if (isp(c).eq.1) goto 20
      h=fr(c)
D     write (*,*) "'",c,"'"
 31   g=fpop(nf,f)
      j=ipop(ni,i)
D     write(*,*) "Opperate ",g," ",char(j)," ",h
      select case(j)
      case (40) 
         goto 20
      case (42)                 ! "*" 
         d=g*h
      case (43)                 ! "+"
         d=g+h
      case (45)                 ! "-"
         d=g-h
      case (47)                 ! "*"
         d=g/h
      end select
 50   nf=pushf(d,nf,f)
 60   j=nop(c)
D     write(*,*) "Got op: ", char(j)
      goto (20, 70, 75, 75, 60, 75, 60, 75) (j-39)
 65   e=fpop(nf,f)
      return
 70   h=fpop(nf,f)              ! Encountered a "("
      goto 31
 75   ni=pushi(j,ni,i)
      goto 30
      end

c     push onto a real stack
c     OB as kf
      function pushf(v,n,f)
      real f(24)
      pushf=n+1
      f(n+1)=v
D     write(*,*) "Push ", v
      return
      end

c     push onto a integer stack
c     OB as ki
      function pushi(j,n,i)
      integer i(24)
      pushi=n+1
      i(n+1)=j
D     write(*,*) "Push ", char(j)
      return
      end

c     pop from real stack
c     OB as fp
      function fpop(n,f)
      real f(24)
      fpop=f(n)
      n=n-1
D      write (*,*) "Pop ", fpop
      return
      end

c     pop from integer stack
c     OB as ip
      function ipop(n,i)
      integer i(24)
      ipop=i(n)
      n=n-1
D      write (*,*) "Pop ", char(ipop)
      return
      end

c     Next OPerator: returns the next nonws character, and removes it
c     from the string
      function nop(s)
      character*99 s
      l=1
      do while(s(l:l).eq." ".and.l.lt.99)
         l=l+1
      enddo
      nop=ichar(s(l:l))
      s(l:l)=" "
      return
      end

c     IS an open Paren: return 1 if the next non-ws character is "("
c     (also overwrite it with a space. Otherwise return not 1
      function isp(s)
      character*99 s
      isp=0
      l=1
      do while(s(l:l).eq." ".and.l.lt.99)
         l=l+1
      enddo
      isp=41-ichar(s(l:l))
      if (isp.eq.1) s(l:l)=" "
      return
      end

c     Float Read: return the next real number in the string and removes the
c     character
      function fr(s)
      character*99 s
      m=1                      ! No sign (Minus or plus) so far
      n=1                      ! No decimal so far
      i=1
      do while(i.le.99)
         j=ichar(s(i:i))
         if (j.eq.32) goto 90   ! skip spaces
         if (j.ge.48.and.j.lt.58) goto 89
         if (j.eq.43.or.j.eq.45) goto (89,80) m
         if (j.eq.46) goto (83,80) n
c     not part of a number
 80      exit
 83      n=2
 89      m=2
 90      i=i+1
      enddo
      read(s(1:i-1),*) fr
      do 91 j=1,i-1
         s(j:j)=" "
 91   continue
      return 
      end

Notes This edited version is rather more evil than my first attempt. Same algorithm, but now inline with a horrible tangle of gotos. I've ditched the co-routines, but am now using a couple of flavors of computed branches. All error checking and reporting has been removed, but this version will silently recover from some classes of unexpected characters in the input. This version also compiles with g77.

The primary limits are still fortran's rigid formatting, long and ubiquitous keywords, and simple primitives.

Excisable

Good God, man! You must have been bored today. ;) – Escarp

Hehe, I don't think I was ever expecting a Fortran solution! I think we can conclude that the language isn't particularly well-suited to code golf? Up-voted anyway for the sheer effort and for using an antiquated language. :) – Antrorse

I find this kind of fiddly byte diddling to be wordy and awkward in fortran, but not actually hard. Writing unstructured code and using those computed branches, on the other hand, feels kinda kinky. – Premonish

Nicely done, but how does a 2000+ character fortran version get more votes than my short little ruby1.9 version? lol – Bolshevist

@darkhelmet: I have no idea. I did it on a lark and expected one or two votes for effort and perversity. I am obscenely proud of this abomination, but this is ridiculous... – Premonish

Answer 9

C99

Number of characters: 239 (But see below for 209)

compressed function:

#define S while(*e==32)++e
#define F float
F strtof();char*e;F v();F g(){S;return*e++-40?strtof(e-1,&e):v();}F v(){F b,a=g();for(;;){S;F o=*e++;if(!o|o==41)return a;b=g();a=o==43?a+b:o==45?a-b:o==42?a*b:a/b;}}F f(char*x){e=x;return v();}

decompressed function:

float strtof();

char* e;
float v();

float g() {
    while (*e == ' ') ++e;
    return *e++ != '(' ? strtof(e-1, &e) : v();
}

float v() {
    float b, a = g();
    for (;;) {
        while (*e == ' ') ++e;
        float op = *e++;
        if (op == 0 || op == ')') return a;
        b = g();
        a = op == '+' ? a + b : op == '-' ? a - b : op == '*' ? a * b : a / b;
    }
}

float eval(char* x) {
    e = x;
    return v();
}

Function is not re-entrant.

EDIT from Chris Lutz: I hate to trample on another man's code, but here is a 209-character version:

#define S for(;*e==32;e++)
#define X (*e++-40?strtof(e-1,&e):v())
float strtof();char*e;float v(){float o,a=X;for(;;){S;o=*e++;if(!o|o==41)return a;S;a=o-43?o-45?o-42?a/X:a*X:a-X:a+X;}}
#define f(x) (e=x,v())

Readable (well, not really very readable, but decompressed):

float strtof();
char *e;
float v() {
    float o, a = *e++ != '(' ? strtof(e - 1, &e) : v();
    for(;;) {
        for(; *e == ' '; e++);
        o = *e++;
        if(o == 0 || o==')') return a;
        for(; *e == ' '; e++);
        // I have no idea how to properly indent nested conditionals
        // and this is far too long to fit on one line.
        a = o != '+' ?
          o != '-' ?
            o != '*' ?
              a / (*e++ != '(' ? strtof(e - 1, &e) : v()) :
              a * (*e++ != '(' ? strtof(e - 1, &e) : v()) :
            a - (*e++ != '(' ? strtof(e - 1, &e) : v()) :
          a + (*e++ != '(' ? strtof(e - 1, &e) : v());
      }
}
#define f(x) (e = x, v())

Yeah, f() is a macro, not a function, but it works. The readable version has some of the logic rewritten but not reordered (like o != '+' instead of o - '+'), but is otherwise just an indented (and preprocessed) version of the other one. I keep trying to simplify the if(!o|o==41)return a; part into the for() loop, but it never makes it shorter. I still believe it can be done, but I'm done golfing. If I work on this question anymore, it will be in the language that must not be named.

Paquin

Nice solution, and bonus points for using "pure" C. Beats mine by 3 chars, as well! Re-entrancy wasn't in the rules, so that's fine. (It is a plus however.) – Antrorse

Nice! You can shave off a few more characters by using ASCII codes, e.g. replace '0' with 48, etc. And of course, you can save a bunch by using atof() instead of your home-grown float parser, but you're intentionally not using library functions, which is not a strict requirement of the problem. – Paresh

I was thinking of using atof() but it doesn't tell you where the float string ends so you would need to parse it anyway. – Paquin

Thanks for the tip, Adam. Using that and a couple of other (ugly) tricks, I shrunk it a bit further. – Paquin

Ouch, I didn't count on negative numbers. Code inflated to 400 characters. – Paquin

Oh right; I guess you can't use atof(), but you could use strtod() or sscanf() with a %n modifier. – Paresh

One more microoptimization: replace "o==0||o==41" with "!o|o==41" – Paresh

Nice tip concerning strtod(), I didn't even know about it. It cut it down quite a bit in spite of the fact that it needs a #include. – Paquin

You can save two characters by using the fact that strtod() skips leading whitespace. – Overawe

Not really, Dave, it still has to skip whitespace in the case where there is a ( and not a number. – Paquin

Doh! I don't need the W macro anymore! – Paquin

Yet another shaving: replace the #include with an exlpicit declaration of "double strtod();". In C (but NOT C++), an empty set of parens means the function takes any number of parameters of any type. Unfortunately, the declaration cannot be elided completely because it doesn't return int. – Paresh

Actually, screw strtod() and use strtof() instead (C99 only)! Saves one more character (if you declare it yourself instead of including stdlib.h), and gets rid of a double-to-float warning. – Paresh

Shaved a few more characters by making op a float instead of char. Made me a little queasy, but it worked. – Paquin

Well done for the persistence! I'm not sure you're going to catch the Haskell/Python solutions, but you're amazingly close, much more so than I ever thought a solution in C would get. Interestingly, I believe this entire solution could be converted to C# at a minimal char cost. – Antrorse

You can save a few more characters by using something I used in my perl solution - the last octal digit of the character codes is different for each operator character, so {{F o=*e++;if(!o|o==41)...}} is equivalent to {{F o=7&*e++;if(o<2)...}}. You should be able to squeeze some more characters out by using "<" and single digits for the rest of that long line; just sort by operator character code. – Grad

@Nosredna: I thought of that but it actually wound up increasing the size by a couple of characters. One more return and it would have worked. – Paquin

After a day of golfing, I've got one down to 214, but I'm going to see if I can shave off any more before I post it (I'm aiming to break 200, but I doubt it'll happen). Hints to what I did: g() and f() are simple enough to inline, strtof()'s chews up leading whitespace for you, o-41 is the same as o!=41 but shorter. I'll post code soon if I can't shave any more off. – Insomnia

209 and I'm posting it and freeing myself from this. Should I edit this post and add my solution or make a new one? – Insomnia

feel free to edit this post if you want – Paquin

+ This is a riot. It is kinda like what I do in performance tuning big software, when I get the chance. I don't obfuscate, but I love lopping off big factors. – Reproduction

Woohoo! Clunky old C is now beating every Python solution up here, as well as Haskell! – Insomnia

Does the preprocessor let you do this and then use D for #define? If so, I can cut another couple characters, I think. --- #define D #define – Whitherward

@Whitherward - No, it doesn't. It checks macro expansions for other macros, but not for new preprocessor directives. – Insomnia

Answer 10

Common Lisp

(SBCL)
Number of characters: 251

(defun g(e)(if(numberp e)e(let((m (g (pop e)))(o(loop for x in e by #'cddr collect x))(n(loop for x in (cdr e)by #'cddr collect (g x))))(mapcar(lambda(x y)(setf m(apply x(list m y))))o n)m)))(defun w(e)(g(read-from-string(concatenate'string"("e")"))))

Proper version (387 chars):

(defun wrapper (exp) (golf-eval (read-from-string (concatenate 'string "(" exp ")"))))

(defun golf-eval (exp)
 (if (numberp exp)
     exp
   (let ((mem (golf-eval (pop exp)))
     (op-list (loop for x in exp by #'cddr collect x))
     (num-list (loop for x in (cdr exp) by #'cddr collect (golf-eval x))))
    (mapcar (lambda (x y) (setf mem (apply x (list mem y)))) op-list num-list)
    mem)))

Input is form w(), which takes one string argument. It uses the trick that nums/operands and operators are in the pattern N O N O N ... and recursively evaluates all operands, and therefore getting nesting very cheap. ;)

Dawes

Clever solution. Nonetheless, I'm not quite sure it's completely valid given that the specification was for the function to take a string object. – Antrorse

Sorry about that. Fixed! – Thousand

No problem. Didn't realise the conversion was so easy. Good solution, still! – Antrorse

Wow. That's beutiful. :) – Moleskins

Answer 11

JavaScript (Not IE compatible)

Number of characters: 268/260

Fully obfuscated function:

function e(x){x=x.replace(/ /g,'')+')'
function P(n){return x[0]=='('?(x=x.substr(1),E()):(n=/^[-+]?[\d.]+/(x)[0],x=x.substr(n.length),+n)}function E(a,o,b){a=P()
for(;;){o=x[0]
x=x.substr(1)
if(o==')')return a
b=P()
a=o=='+'?a+b:o=='-'?a-b:o=='*'?a*b:a/b}}return E()}

or, in JavaScript 1.8 (Firefox 3+), you can save a few characters by using expression closures:

e=function(x,P,E)(x=x.replace(/ /g,'')+')',P=function(n)(x[0]=='('?(x=x.substr(1),E()):(n=/^[-+]?[\d.]+/(x)[0],x=x.substr(n.length),+n)),E=function(a,o,b){a=P()
for(;;){o=x[0]
x=x.substr(1)
if(o==')')return a
b=P()
a=o=='+'?a+b:o=='-'?a-b:o=='*'?a*b:a/b}},E())

Clear/semi-obfuscated function:

function evaluate(x) {
    x = x.replace(/ /g, "") + ")";
    function primary() {
        if (x[0] == '(') {
            x = x.substr(1);
            return expression();
        }

        var n = /^[-+]?\d*\.?\d*/.exec(x)[0];
        x = x.substr(n.length);
        return +n;
    }

    function expression() {
        var a = primary();
        for (;;) {
            var operator = x[0];
            x = x.substr(1);

            if (operator == ')') {
                return a;
            }

            var b = primary();
            a = (operator == '+') ? a + b :
                (operator == '-') ? a - b :
                (operator == '*') ? a * b :
                                    a / b;
        }
    }

    return expression();
}

Neither version will work in IE, because they use array-style subscripting on the string. If you replace both occurrences of x[0] with x.charAt(0), the first one should work everywhere.

I cut out some more characters since the first version by turning variables into function parameters and replacing another if statement with the conditional operator.

Gruel

That's pretty good. I was waiting for someone to use regex here. :) It would seem like dynamic languages definitely have an advantage for this problem. – Antrorse

Answer 12

SQL (SQL Server 2008)

Number of characters: 4202

Fully obfuscated function:

WITH Input(id,str)AS(SELECT 1,'1 + 3 / -8'UNION ALL SELECT 2,'2*3*4*5+99'UNION ALL SELECT 3,'4 * (9 - 4)/ (2 * 6 - 2)+ 8'UNION ALL SELECT 4,'1 + ((123 * 3 - 69)/ 100)'UNION ALL SELECT 5,'2.45/8.5*9.27+(5*0.0023)'),Separators(i,ch,str_src,priority)AS(SELECT 1,'-',1,1UNION ALL SELECT 2,'+',1,1UNION ALL SELECT 3,'*',1,1UNION ALL SELECT 4,'/',1,1UNION ALL SELECT 5,'(',0,0UNION ALL SELECT 6,')',0,0),SeparatorsStrSrc(str,i)AS(SELECT CAST('['AS varchar(max)),0UNION ALL SELECT str+ch,SSS.i+1FROM SeparatorsStrSrc SSS INNER JOIN Separators S ON SSS.i=S.i-1WHERE str_src<>0),SeparatorsStr(str)AS(SELECT str+']'FROM SeparatorsStrSrc WHERE i=(SELECT COUNT(*)FROM Separators WHERE str_src<>0)),ExprElementsSrc(id,i,tmp,ele,pre_ch,input_str)AS(SELECT id,1,CAST(LEFT(str,1)AS varchar(max)),CAST(''AS varchar(max)),CAST(' 'AS char(1)),SUBSTRING(str,2,LEN(str))FROM Input UNION ALL SELECT id,CASE ele WHEN''THEN i ELSE i+1 END,CAST(CASE WHEN LEFT(input_str,1)=' 'THEN''WHEN tmp='-'THEN CASE WHEN pre_ch LIKE(SELECT str FROM SeparatorsStr)THEN tmp+LEFT(input_str,1)ELSE LEFT(input_str,1)END WHEN LEFT(input_str,1)IN(SELECT ch FROM Separators)OR tmp IN(SELECT ch FROM Separators)THEN LEFT(input_str,1)ELSE tmp+LEFT(input_str,1)END AS varchar(max)),CAST(CASE WHEN LEFT(input_str,1)=' 'THEN tmp WHEN LEFT(input_str,1)='-'THEN CASE WHEN tmp IN(SELECT ch FROM Separators)THEN tmp ELSE''END WHEN LEFT(input_str,1)IN(SELECT ch FROM Separators)OR tmp IN(SELECT ch FROM Separators)THEN CASE WHEN tmp='-'AND pre_ch LIKE(SELECT str FROM SeparatorsStr)THEN''ELSE tmp END ELSE''END AS varchar(max)),CAST(LEFT(ele,1)AS char(1)),SUBSTRING(input_str,2,LEN(input_str))FROM ExprElementsSrc WHERE input_str<>''OR tmp<>''),ExprElements(id,i,ele)AS(SELECT id,i,ele FROM ExprElementsSrc WHERE ele<>''),Scanner(id,i,val)AS(SELECT id,i,CAST(ele AS varchar(max))FROM ExprElements WHERE ele<>''UNION ALL SELECT id,MAX(i)+1,NULL FROM ExprElements GROUP BY id),Operator(op,priority)AS(SELECT ch,priority FROM Separators WHERE priority<>0),Calc(id,c,i,pop_count,s0,s1,s2,stack,status)AS(SELECT Scanner.id,1,1,0,CAST(scanner.val AS varchar(max)),CAST(NULL AS varchar(max)),CAST(NULL AS varchar(max)),CAST(''AS varchar(max)),CAST('init'AS varchar(max))FROM Scanner WHERE Scanner.i=1UNION ALL SELECT Calc.id,Calc.c+1,Calc.i,3,NULL,NULL,NULL,CASE Calc.s1 WHEN'+'THEN CAST(CAST(Calc.s2 AS real)+CAST(Calc.s0 AS real)AS varchar(max))WHEN'-'THEN CAST(CAST(Calc.s2 AS real)-CAST(Calc.s0 AS real)AS varchar(max))WHEN'*'THEN CAST(CAST(Calc.s2 AS real)*CAST(Calc.s0 AS real)AS varchar(max))WHEN'/'THEN CAST(CAST(Calc.s2 AS real)/CAST(Calc.s0 AS real)AS varchar(max))ELSE NULL END+' '+stack,CAST('calc '+Calc.s1 AS varchar(max))FROM Calc INNER JOIN Scanner NextVal ON Calc.id=NextVal.id AND Calc.i+1=NextVal.i WHERE Calc.pop_count=0AND ISNUMERIC(Calc.s2)=1AND Calc.s1 IN(SELECT op FROM Operator)AND ISNUMERIC(Calc.s0)=1AND(SELECT priority FROM Operator WHERE op=Calc.s1)>=COALESCE((SELECT priority FROM Operator WHERE op=NextVal.val),0)UNION ALL SELECT Calc.id,Calc.c+1,Calc.i,3,NULL,NULL,NULL,s1+' '+stack,CAST('paren'AS varchar(max))FROM Calc WHERE pop_count=0AND s2='('AND ISNUMERIC(s1)=1AND s0=')'UNION ALL SELECT Calc.id,Calc.c+1,Calc.i,Calc.pop_count-1,s1,s2,CASE WHEN LEN(stack)>0THEN SUBSTRING(stack,1,CHARINDEX(' ',stack)-1)ELSE NULL END,CASE WHEN LEN(stack)>0THEN SUBSTRING(stack,CHARINDEX(' ',stack)+1,LEN(stack))ELSE''END,CAST('pop'AS varchar(max))FROM Calc WHERE Calc.pop_count>0UNION ALL SELECT Calc.id,Calc.c+1,Calc.i+1,Calc.pop_count,CAST(NextVal.val AS varchar(max)),s0,s1,coalesce(s2,'')+' '+stack,cast('read'as varchar(max))FROM Calc INNER JOIN Scanner NextVal ON Calc.id=NextVal.id AND Calc.i+1=NextVal.i WHERE NextVal.val IS NOT NULL AND Calc.pop_count=0AND((Calc.s0 IS NULL OR calc.s1 IS NULL OR calc.s2 IS NULL)OR NOT(ISNUMERIC(Calc.s2)=1AND Calc.s1 IN(SELECT op FROM Operator)AND ISNUMERIC(calc.s0)=1AND (SELECT priority FROM Operator WHERE op=Calc.s1)>=COALESCE((SELECT priority FROM Operator WHERE op=NextVal.val),0))AND NOT(s2='('AND ISNUMERIC(s1)=1AND s0=')')))SELECT Calc.id,Input.str,Calc.s0 AS result FROM Calc INNER JOIN Input ON Calc.id=Input.id WHERE Calc.c=(SELECT MAX(c)FROM Calc calc2 WHERE Calc.id=Calc2.id)ORDER BY id

Clear/semi-obfuscated function:

WITH
  Input(id, str) AS (    
    SELECT 1, '1 + 3 / -8'
    UNION ALL SELECT 2, '2*3*4*5+99'
    UNION ALL SELECT 3, '4 * (9 - 4) / (2 * 6 - 2) + 8'
    UNION ALL SELECT 4, '1 + ((123 * 3 - 69) / 100)'
    UNION ALL SELECT 5, '2.45/8.5*9.27+(5*0.0023)'
  )
, Separators(i, ch, str_src, priority) AS (
    SELECT 1, '-', 1, 1
    UNION ALL SELECT 2, '+', 1, 1
    UNION ALL SELECT 3, '*', 1, 1
    UNION ALL SELECT 4, '/', 1, 1
    UNION ALL SELECT 5, '(', 0, 0
    UNION ALL SELECT 6, ')', 0, 0
  )
, SeparatorsStrSrc(str, i) AS (
    SELECT CAST('[' AS varchar(max)), 0
    UNION ALL
    SELECT
        str + ch
      , SSS.i + 1
    FROM
        SeparatorsStrSrc SSS
          INNER JOIN Separators S ON SSS.i = S.i - 1
    WHERE
        str_src <> 0
  )
, SeparatorsStr(str) AS (
    SELECT str + ']' FROM SeparatorsStrSrc
    WHERE i = (SELECT COUNT(*) FROM Separators WHERE str_src <> 0)
  )
, ExprElementsSrc(id, i, tmp, ele, pre_ch, input_str) AS (
    SELECT
        id
      , 1
      , CAST(LEFT(str, 1) AS varchar(max))
      , CAST('' AS varchar(max))
      , CAST(' ' AS char(1))
      , SUBSTRING(str, 2, LEN(str))
    FROM
        Input
    UNION ALL
    SELECT
        id
      , CASE ele
        WHEN '' THEN i
                ELSE i + 1
        END
      , CAST(
          CASE
          WHEN LEFT(input_str, 1) = ' '
            THEN ''
          WHEN tmp = '-'
            THEN CASE
                 WHEN pre_ch LIKE (SELECT str FROM SeparatorsStr)
                   THEN tmp + LEFT(input_str, 1)
                   ELSE LEFT(input_str, 1)
                 END
          WHEN LEFT(input_str, 1) IN (SELECT ch FROM Separators)
               OR
               tmp IN (SELECT ch FROM Separators)
            THEN LEFT(input_str, 1)
            ELSE tmp + LEFT(input_str, 1)
          END
        AS varchar(max))
      , CAST(
          CASE
          WHEN LEFT(input_str, 1) = ' '
            THEN tmp
          WHEN LEFT(input_str, 1) = '-'
            THEN CASE
                 WHEN tmp IN (SELECT ch FROM Separators)
                   THEN tmp
                   ELSE ''
                 END
          WHEN LEFT(input_str, 1) IN (SELECT ch FROM Separators)
               OR
               tmp IN (SELECT ch FROM Separators)
            THEN CASE
                 WHEN tmp = '-' AND pre_ch LIKE (SELECT str FROM SeparatorsStr)
                   THEN ''
                   ELSE tmp
                 END
            ELSE ''
          END
        AS varchar(max))
      , CAST(LEFT(ele, 1) AS char(1))
      , SUBSTRING(input_str, 2, LEN(input_str))
    FROM
        ExprElementsSrc
    WHERE
        input_str <> ''
        OR
        tmp <> ''
  )
, ExprElements(id, i, ele) AS (
    SELECT
        id
      , i
      , ele
    FROM
        ExprElementsSrc
    WHERE
        ele <> ''
  )
, Scanner(id, i, val) AS (
    SELECT
        id
      , i
      , CAST(ele AS varchar(max))
    FROM
        ExprElements
    WHERE
        ele <> ''
    UNION ALL
    SELECT
        id
      , MAX(i) + 1
      , NULL
    FROM
        ExprElements
    GROUP BY
        id
  )
, Operator(op, priority) AS (
    SELECT
        ch
      , priority 
    FROM
        Separators
    WHERE
        priority <> 0
  )
, Calc(id, c, i, pop_count, s0, s1, s2, stack, status) AS (
    SELECT
        Scanner.id
      , 1
      , 1
      , 0
      , CAST(scanner.val AS varchar(max))
      , CAST(NULL AS varchar(max))
      , CAST(NULL AS varchar(max))
      , CAST('' AS varchar(max))
      , CAST('init' AS varchar(max))
    FROM
        Scanner
    WHERE
        Scanner.i = 1
    UNION ALL
    SELECT
        Calc.id
      , Calc.c + 1
      , Calc.i
      , 3
      , NULL
      , NULL
      , NULL
      , CASE Calc.s1
        WHEN '+' THEN CAST(CAST(Calc.s2 AS real) + CAST(Calc.s0 AS real) AS varchar(max))
        WHEN '-' THEN CAST(CAST(Calc.s2 AS real) - CAST(Calc.s0 AS real) AS varchar(max))
        WHEN '*' THEN CAST(CAST(Calc.s2 AS real) * CAST(Calc.s0 AS real) AS varchar(max))
        WHEN '/' THEN CAST(CAST(Calc.s2 AS real) / CAST(Calc.s0 AS real) AS varchar(max))
                 ELSE NULL
        END
          + ' '
          + stack
      , CAST('calc ' + Calc.s1 AS varchar(max))
    FROM
        Calc
          INNER JOIN Scanner NextVal ON Calc.id = NextVal.id
                                          AND Calc.i + 1 = NextVal.i
    WHERE
        Calc.pop_count = 0
          AND ISNUMERIC(Calc.s2) = 1
          AND Calc.s1 IN (SELECT op FROM Operator)
          AND ISNUMERIC(Calc.s0) = 1
          AND (SELECT priority FROM Operator WHERE op = Calc.s1)
            >= COALESCE((SELECT priority FROM Operator WHERE op = NextVal.val), 0)
    UNION ALL
    SELECT
        Calc.id
      , Calc.c + 1
      , Calc.i
      , 3
      , NULL
      , NULL
      , NULL
      , s1 + ' ' + stack
      , CAST('paren' AS varchar(max))
    FROM
        Calc
    WHERE
        pop_count = 0
          AND s2 = '('
          AND ISNUMERIC(s1) = 1
          AND s0 = ')'
    UNION ALL
    SELECT
        Calc.id
      , Calc.c + 1
      , Calc.i
      , Calc.pop_count - 1
      , s1
      , s2
      , CASE
        WHEN LEN(stack) > 0
          THEN SUBSTRING(stack, 1, CHARINDEX(' ', stack) - 1)
          ELSE NULL
        END
      , CASE
        WHEN LEN(stack) > 0
          THEN SUBSTRING(stack, CHARINDEX(' ', stack) + 1, LEN(stack))
          ELSE ''
        END
      , CAST('pop' AS varchar(max))
    FROM
        Calc
    WHERE
        Calc.pop_count > 0
    UNION ALL
    SELECT
        Calc.id
      , Calc.c + 1
      , Calc.i + 1
      , Calc.pop_count
      , CAST(NextVal.val AS varchar(max))
      , s0
      , s1
      , coalesce(s2, '') + ' ' + stack
      , cast('read' as varchar(max))
    FROM
        Calc
          INNER JOIN Scanner NextVal ON Calc.id = NextVal.id
                                          AND Calc.i + 1 = NextVal.i
    WHERE
        NextVal.val IS NOT NULL
          AND Calc.pop_count = 0
          AND (
            (Calc.s0 IS NULL or calc.s1 is null or calc.s2 is null)
            OR
            NOT(
              ISNUMERIC(Calc.s2) = 1
                AND Calc.s1 IN (SELECT op FROM Operator)
                AND ISNUMERIC(calc.s0) = 1
                AND (SELECT priority FROM Operator WHERE op = Calc.s1)
                  >= COALESCE((SELECT priority FROM Operator WHERE op = NextVal.val), 0)
            )
              AND NOT(s2 = '(' AND ISNUMERIC(s1) = 1 AND s0 = ')')
          )
  )
SELECT
    Calc.id
  , Input.str
  , Calc.s0 AS result
FROM
    Calc
      INNER JOIN Input ON Calc.id = Input.id
WHERE
    Calc.c = (SELECT MAX(c) FROM Calc calc2
              WHERE Calc.id = Calc2.id)
ORDER BY
    id

It is not shortest. But I think that it is very flexible for SQL. It's easy to add new operators. It's easy to change priority of operators.

Byars

Gosh, I don't think I was ever expecting an SQL solution! This isn't completely in the spirit of code golf, but up-voted anyway for the audacity (and not even using a programming language). :) – Antrorse

@Noldorin, why isn't it in the spirit of code golf? – Mooned

Answer 13

C# with Regex Love

Number of characters: 384

Fully-obfuscated:

float E(string i){i=i.Replace(" ","");Regex b=new Regex(@"\((?>[^()]+|\((?<D>)|\)(?<-D>))*(?(D)(?!))\)");i=b.Replace(i,m=>Eval(m.Value.Substring(1,m.Length-2)).ToString());float r=0;foreach(Match m in Regex.Matches(i,@"(?<=^|\D)-?[\d.]+")){float f=float.Parse(m.Value);if(m.Index==0)r=f;else{char o=i[m.Index-1];if(o=='+')r+=f;if(o=='-')r-=f;if(o=='*')r*=f;if(o=='/')r/=f;}}return r;}

Not-obfuscated:

private static float Eval(string input)
{
    input = input.Replace(" ", "");
    Regex balancedMatcher = new Regex(@"\(
                                            (?>
                                                [^()]+
                                            |
                                                \( (?<Depth>)
                                            |
                                                \) (?<-Depth>)
                                            )*
                                            (?(Depth)(?!))
                                        \)", RegexOptions.IgnorePatternWhitespace);
    input = balancedMatcher.Replace(input, m => Eval(m.Value.Substring(1, m.Length - 2)).ToString());

    float result = 0;

    foreach (Match m in Regex.Matches(input, @"(?<=^|\D)-?[\d.]+"))
    {
        float floatVal = float.Parse(m.Value);
        if (m.Index == 0)
        {
            result = floatVal;
        }
        else
        {
            char op = input[m.Index - 1];
            if (op == '+') result += floatVal;
            if (op == '-') result -= floatVal;
            if (op == '*') result *= floatVal;
            if (op == '/') result /= floatVal;
        }
    }

    return result;
}

Takes advantage of .NET's Regex balancing group feature.

Urbanna

Thanks for that solution. :) I wasn't sure whether I would see a C# solution with regex, but here we have it. Now, it's arguable whether you should include the "using System.Text.RegularExpressions;" in your char count, but it's a good solution nonetheless. – Antrorse

That wasn't part of the rules :). If you add "using R=System.Text.RegularExpressions.Regex;" and replace my "Regex" with R, it goes to 417. – Urbanna

@Jeff: Well, technically it won't compile without the using statement, so by default it should be included. Petty point, however, given that our C# solutions are all significantly behind the leader. – Antrorse

Answer 14

PHP

Number of characters: 284

obfuscated:

function f($m){return c($m[1]);}function g($n,$m){$o=$m[0];$m[0]=' ';return$o=='+'?$n+$m:($o=='-'?$n-$m:($o=='*'?$n*$m:$n/$m));}function c($s){while($s!=($t=preg_replace_callback('/\(([^()]*)\)/',f,$s)))$s=$t;preg_match_all('![-+/*].*?[\d.]+!',"+$s",$m);return array_reduce($m[0],g);}

readable:

function callback1($m) {return c($m[1]);}
function callback2($n,$m) {
    $o=$m[0];
    $m[0]=' ';
    return $o=='+' ? $n+$m : ($o=='-' ? $n-$m : ($o=='*' ? $n*$m : $n/$m));
}
function c($s){ 
    while ($s != ($t = preg_replace_callback('/\(([^()]*)\)/','callback1',$s))) $s=$t;
    preg_match_all('![-+/*].*?[\d.]+!', "+$s", $m);
    return array_reduce($m[0], 'callback2');
}


$str = '  2.45/8.5  *  -9.27   +    (   5   *  0.0023  ) ';
var_dump(c($str));
# float(-2.66044117647)

Should work with any valid input (including negative numbers and arbitrary whitespace)

Countless

preg_replace() with the e modifier would save you some more bytes. – Georgenegeorges

Answer 15

J

Number of characters: 208

After Jeff Moser's comment, I realized that I had completely forgotten about this language... I'm no expert, but my first attempt went rather well.

e=:>@{:@f@;:
f=:''&(4 :0)
'y x'=.x g y
while.($y)*-.')'={.>{.y do.'y x'=.(x,>(-.'/'={.>{.y){('%';y))g}.y end.y;x
)
g=:4 :0
z=.>{.y
if.z='('do.'y z'=.f}.y else.if.z='-'do.z=.'_',>{.}.y end.end.(}.y);":".x,z
)

It's a bit annoying, having to map x/y and -z into J's x%y and _z. Without that, maybe 50% of this code could disappear.

Boser

Yeah, that's pretty nice. Now what about a solution in K? :P I'm suspecting that might even be able to beat Perl. – Antrorse

Woohoo, I managed to get my Haskell solution under my J solution! Though if somebody here were a J or K or APL wizard, they'd probably destroy the 200-character barrier... – Boser

Answer 16

Python (without importing anything)

Number of characters: 222

I stole many tricks from Dave's answer, but I managed to shave off some more characters.

def e(s,l=0,n=0,f='+'):
 if s:l=[c for c in s+')'if' '!=c]
 while f!=')':
  p=l.pop;m=p(0)
  if m=='(':m=e(0,l)
  while l[0]not in'+-*/)':m+=p(0)
  m=float(m);n={'+':n+m,'-':n-m,'*':n*m,'/':n/(m or 1)}[f];f=p(0)
 return n

Commented version:

def evaluate(stringexpr, listexpr=0, n=0, f_operation='+'):
    # start out as taking 0 + the expression... (or could use 1 * ;)

    # We'll prefer to keep the expression as a list of characters,
    # so we can use .pop(0) to eat up the expression as we go.
    if stringexpr:
        listexpr = [c for c in stringexpr+')' if c!=' ']

    # use ')' as sentinel to return the answer
    while f_operation != ')':
        m_next = listexpr.pop(0)
        if m_next == '(':
            # lists are passed by reference, so this call will eat the (parexp)
            m_next = evaluate(None, listexpr)

        else:
            # rebuild any upcoming numeric chars into a string
            while listexpr[0] not in '+-*/)':
                m_next += listexpr.pop(0)

        # Update n as the current answer.  But never divide by 0.
        m = float(m_next)
        n = {'+':n+m, '-':n-m, '*':n*m, '/':n/(m or 1)}[f_operation]

        # prepare the next operation (known to be one of '+-*/)')
        f_operation = listexpr.pop(0)

    return n

Kenishakenison

+1 Nice dict idea. The current version fails on e('1+0'), however. Use {'+':n+m,'-':n-m,'':nm,'/':n/m if m else 1} instead. I have borrowed your idea (with this amendment). Thanks – Denudation

Thanks. I hadn't thought of the DivZero problem; a 7-character fix is n/(m or 1). – Kenishakenison

Will do this for my program, too ;-) – Denudation

hehe, don't change anything now, the number of characters is beautiful :) – Olivarez

Answer 17

F#

Number of characters: 327

OP was looking for an F# version, here it is. Can be done a lot nicer since I'm abusing a ref here to save characters. It handles most things such as -(1.0), 3 - -3 and even 0 - .5 etc.

let g s=
 let c=ref[for x in System.Text.RegularExpressions.Regex.Matches(s,"[0-9.]+|[^\s]")->x.Value]
 let rec e v=if (!c).IsEmpty then v else 
  let h=(!c).Head
  c:=(!c).Tail
  match h with|"("->e(e 0.0)|")"->v|"+"->e(v+(e 0.0))|"-"->e(v-(e 0.0))|"/"->e(v/(e 0.0))|"*"->e(v*(e 0.0))|x->float x
 e(e 0.0)

Jasmin

Indeed, I was hoping for an F# solution. Thanks for that. Char count is pretty decent too, especially considering that "System.Text.RegularExpressions.Regex.Matches" takes up an absurd number of characters. – Antrorse

yeah, same with the .Value.IsEmpty/Tail/Head calls - I got a new version in the works ;p hoping for sub250 chars. – Jasmin

I'm not actually sure whether in some code golf contests you are allowed import/using statements outside the char count. That would definitely help, if so. :) Looking forward to seeing the new version. – Antrorse

@Noldorin: Nope I'm sorry I can't get it under the 327 characters of this (a bit enhanced since last) code. The gain from having everything perfectly parsed with the regex outweighs the insanely long name of "System.Text.RegularExpressions.Regex.Matches" If F# would've had a short (aliased) name for the Matches function I would be at 288 chars, but it does not =/. – Jasmin

@fredrikholmstrom: No worries - good solution nonetheless. Also, I'm not completely sure, but I would say that you should be able to move "System.Text.RegularExpressions" into an "open" statement and exclude the char count for that at least. – Antrorse

Answer 18

MATLAB (v7.8.0)

Number of characters: 239

Obfuscated function:

function [v,s]=m(s),r=1;while s,s=regexp(s,'( ?)(?(1)-?)[\.\d]+|\S','match');c=s{end};s=[s{1:end-1}];if any(c>47),v=str2num(c);elseif c>41,[l,s]=m(s);v=[l/v l*v l+v l-v];v=v(c=='/*+-');if r,break;end;r=1;elseif c<41,break;end;r=r&c~=41;end

Clear(er) function:

function [value,str] = math(str)
  returnNow = 1;
  while str,
    str = regexp(str,'( ?)(?(1)-?)[\.\d]+|\S','match');
    current = str{end};
    str = [str{1:end-1}];
    if any(current > 47),
      value = str2num(current);
    elseif current > 41,
      [leftValue,str] = math(str);
      value = [leftValue/value leftValue*value ...
               leftValue+value leftValue-value];
      value = value(current == '/*+-');
      if returnNow,
        break;
      end;
      returnNow = 1;
    elseif current < 41,
      break;
    end;
    returnNow = returnNow & (c ~= 41);
  end

Test:

>> [math('1 + 3 / -8'); ...
math('2*3*4*5+99'); ...
math('4 * (9 - 4) / (2 * 6 - 2) + 8'); ...
math('1 + ((123 * 3 - 69) / 100)'); ...
math('2.45/8.5*9.27+(5*0.0023)')]

ans =

   -0.5000
  219.0000
   10.0000
    4.0000
    2.6834

Synopsis: A mixture of regular expressions and recursion. Pretty much the best I have been able to do so far, without cheating and using EVAL.

Escarp

Answer 19

Here comes another one:

Shell script (using sed+awk)

Number of characters: 295

obfuscated:

e(){ a="$1";while echo "$a"|grep -q \(;do eval "`echo "$a"|sed 's/\(.*\)(\([^()]*\))\(.*\)/a="\1\`e \"\2\"\`\3"/'`";done; echo "$a"|sed 's/\([-+*/]\) *\(-\?\) */ \1 \2/g'|awk '{t=$1;for(i=2;i<NF;i+=2){j=$(i+1);if($i=="+") t+=j; else if($i=="-") t-=j; else if($i=="*") t*=j; else t/=j}print t}';}

readable

e () {
    a="$1"
    # Recursively process bracket-expressions
    while echo "$a"|grep -q \(; do
        eval "`echo "$a"|
            sed 's/\(.*\)(\([^()]*\))\(.*\)/a="\1\`e \"\2\"\`\3"/'`"
    done
    # Compute expression without brackets
    echo "$a"|
        sed 's/\([-+*/]\) *\(-\?\) */ \1 \2/g'|
        awk '{
            t=$1;
            for(i=2;i<NF;i+=2){
                j=$(i+1);
                if($i=="+") t+=j;
                else if($i=="-") t-=j;
                else if($i=="*") t*=j;
                else t/=j
            }
            print t
        }'
}

Test:

str='  2.45 / 8.5  *  9.27   +    (   5   *  0.0023  ) '
echo "$str"|bc -l
e "$str"

Result:

2.68344117647058823526
2.68344

Countless

I have (almost) no idea how this works, but I am amazed how well a shell script does at this task! Well done indeed. – Antrorse

Well, just remember that many many operating systems use that language/tool mix for many many different tasks :) – Countless

Answer 20

Ruby

Number of characters: 170

Obfuscated:

def s(x)
while x.sub!(/\(([^\(\)]*?)\)/){s($1)}
x.gsub!('--','')
end
while x.sub!(/(-?[\d.]+)[ ]*([+\-*\/])[ ]*(-?[\d.]+)/){$1.to_f.send($2,$3.to_f)}
end
x.strip.to_f
end

Readable:

def s(x)
while x.sub!(/\(([^\(\)]*?)\)/){s($1)}
x.gsub!('--','')
end
while x.sub!(/(-?[\d.]+)[ ]*([+\-*\/])[ ]*(-?[\d.]+)/){$1.to_f.send($2,$3.to_f)}
end
x.strip.to_f
end

[
  ['1 + 3 / -8', -0.5],
  ['2*3*4*5+99', 219],
  ['4 * (9 - 4) / (2 * 6 - 2) + 8', 10],
  ['1 + ((123 * 3 - 69) / 100)', 4],
  ['2.45/8.5*9.27+(5*0.0023)',2.68344117647059],
  ['(3+7) - (5+2)', 3]
].each do |pair|
  a,b = s(String.new(pair[0])),pair[1]
  print pair[0].ljust(25), ' = ', b, ' (', a==b, ')'
  puts
end

There is no real obfuscation to this one, which I decided to post fresh since it's wildly different from my first. I should have seen this from the start. The process is a very simple process of elimination: find and resolve the highest pair of parenthesis (the most nested) into a number until no more are found, then resolve all the existing numbers and operations into the result. And, while resolving parenthetical statements I have it strip all double-dashes (Float.to_f doesn't know what to do with them).

So, it supports positive and negative numbers (+3, 3, & -3) and even negated sub-expressions within the parenthesis just by the order of processing. The only shorter implementation is the Perl (w/o eval) one.

Edit: I'm still chasing Perl, but this is the second smallest answer right now. I shrunk it with changes to the second regex and by changing the treatment of the string to be destructive (replaces the old string). This eliminated the need to duplicate the string, which I found out to just be a new pointer to the string. And renaming the function to s from solve saved a few characters.

Lyonnaise

Nice work, surprised I didn't try this approach myself, since I used something very similar to solve another parsing question. – Nipper

See my solution for a way to compress that regexp. You shouldn't need the final 'strip' either. And it doesn't look as though you fully implement unary minus, so you get little benefit from the gsub('--',''). – Polonium

I cannot actually shorten my particular algorithm or I fail 3-4 of the tests, I'm not certain why. I could shrink it by maybe 20 characters though. – Lyonnaise

Answer 21

C#

Number of characters: 403

So here's my solution... I'm still waiting for someone to post one in C# that can beat it. (Marc Gravell was close, and may yet do better than me after some more tinkering.)

Fully obfuscated function:

float e(string x){float v=0;if(float.TryParse(x,out v))return v;x+=';';int t=0;
char o,s='?',p='+';float n=0;int l=0;for(int i=0;i<x.Length;i++){o=s;if(
x[i]!=' '){s=x[i];if(char.IsDigit(x[i])|s=='.'|(s=='-'&o!='1'))s='1';if(s==')')
l--;if(s!=o&l==0){if(o=='1'|o==')'){n=e(x.Substring(t,i-t));if(p=='+')v+=n;
if(p=='-')v-=n;if(p=='*')v*=n;if(p=='/')v/=n;p=x[i];}t=i;if(s=='(')t++;}
if(s=='(')l++;}}return v;}

Semi-obfuscated function:

public static float Eval(string expr)
{
    float val = 0;
    if (float.TryParse(expr, out val))
        return val;
    expr += ';';
    int tokenStart = 0;
    char oldState, state = '?', op = '+';
    float num = 0;
    int level = 0;
    for (int i = 0; i < expr.Length; i++)
    {
        oldState = state;
        if (expr[i] != ' ')
        {
            state = expr[i];
            if (char.IsDigit(expr[i]) || state == '.' ||
                (state == '-' && oldState != '1'))
                state = '1';
            if (state == ')')
                level--;
            if (state != oldState && level == 0)
            {
                if (oldState == '1' || oldState == ')')
                {
                    num = Eval(expr.Substring(tokenStart, i - tokenStart));
                    if (op == '+') val += num;
                    if (op == '-') val -= num;
                    if (op == '*') val *= num;
                    if (op == '/') val /= num;
                    op = expr[i];
                }
                tokenStart = i;
                if (state == '(')
                    tokenStart++;
            }
            if (state == '(')
                level++;
        }
    }
    return val;
}

Nothing too clever going on here, it woul seem. The function does however have the advantage of being re-entrant (i.e. thread-safe).

I am also reasonably pleased with the number of chars, given that it's written in C# (valid 1.0, 2.0, and 3.0 I believe).

Antrorse

Any tips on how I might reduce the char count further would be welcome. (The is my first real attempt at code golf.) – Antrorse

I got it < 400, but it fails the edited test you added ;-p – Adamec

Suggestions: "var" for float, char - only shaves a few, and loses the C# 1.2/2.0 compatibility, though. – Adamec

@Marc: Yeah, that's about as far as I got too. With a few other minor changes, I might get it down to 390, but no less. – Antrorse

Nice solution Nolorin. I was able to get your solution down to 361 – Breathtaking

@Chris: Thanks - though now I'm curious how you managed to get the char count down so much. (I could probably knock off about 15 or 20 more myself, but no more.) Mind sharing it with us? Feel free to edit my post, even. – Antrorse

I've gotten it down to 294 chars using a bit of regex. :) See my new answer: #929063 – Antrorse

Doesn't work for unary minus: (5 + 5) * (3 + 2)-1 Evaluates to 51. – Defazio

Answer 22

Ruby

Number of characters: 217 179

This is the shortest ruby solution up to now (one heavily based on RegExp yields incorrect answers when string contains few groups of parenthesis) -- no longer true. Solutions based on regex and substitution are shorter. This one is based on stack of accumulators and parses whole expression from left to right. It is re-entrant, and does not modify input string. It could be accused of breaking the rules of not using eval, as it calls Float's methods with identical names as their mathematical mnemonics (+,-,/,*).

Obfuscated code (old version, tweaked below):

def f(p);a,o=[0],['+']
p.sub(/-/,'+-').scan(/(?:(-?\d+(?:\.\d+)?)|(.))\s*/).each{|n|
q,w=n;case w;when'(';a<<0;o<<'+';when')';q=a.pop;else;o<<w
end if q.nil?;a[-1]=a[-1].method(o.pop).call(q.to_f) if !q.nil?};a[0];end

More obfuscated code:

def f(p);a,o=[0],[:+]
p.scan(/(?:(-?\d+(?:\.\d+)?)|(.))\s*/).each{|n|q,w=n;case w
when'(';a<<0;o<<:+;when')';q=a.pop;else;o<<w;end if !q
a<<a.pop.send(o.pop,q.to_f)if q};a[0];end

Clean code:

def f(p)
  accumulators, operands = [0], ['+']
  p.gsub(/-/,'+-').scan(/(?:(-?\d+(?:\.\d+)?)|(.))\s*/).each do |n|
    number, operand = n
    case operand
      when '('
        accumulators << 0
        operands << '+'
      when ')'
        number = accumulators.pop
        operands.pop
      else 
        operands[-1] = operand
    end if number.nil?
    accumulators[-1] = accumulators.last.method(operands[-1]).call(number.to_f) unless number.nil?
  end
  accumulators.first
end

Jaclyn

Actually, mine is shorter (198) and uses regex to solve parenthesis from the top down before the final result of the mathematics. So "3 + (3 * (3 + 9))" goes: "3 + (3 * 12)", "3 + 36", 39. It goes top-to-bottom, left-to-right. It solves all tests, except one minor oversight which requires spaces between tokens. See: #929063 – Lyonnaise

Not that yours isn't clever, it very much is. – Lyonnaise

(3+7) - (5+2) -- that's what I've meant by several parentheses groups. Your solution has problem with non-nested parentheses, because of regex greediness. – Jaclyn

That may be, but I had been fiddling around with my parser yesterday night and improved it on my system (with mathematical functions and single letter variables). So I pulled my better regex from it and it works just fine, the post is updated with a new char count too. ;-) I'll roll in your equation into the tests in the answer momentarily. – Lyonnaise

I don't think the use of 'method' or 'send' is cheating - it's just a table lookup - you are not using the built-in parser. – Polonium

Answer 23

Python

Number of characters: 235

Fully obfuscated function:

def g(a):
 i=len(a)
 while i:
  try:m=g(a[i+1:]);n=g(a[:i]);a=str({'+':n+m,'-':n-m,'*':n*m,'/':n/(m or 1)}[a[i]])
  except:i-=1;j=a.rfind('(')+1
  if j:k=a.find(')',j);a=a[:j-1]+str(g(a[j:k]))+a[k+1:]
 return float(a.replace('--',''))

Semi-obfuscated:

def g(a):
    i=len(a);
    # do the math
    while i:
        try:
            # recursively evaluate left and right
            m=g(a[i+1:])
            n=g(a[:i])
            # try to do the math assuming that a[i] is an operator
            a=str({'+':n+m,'-':n-m,'*':n*m,'/':n/(m or 1)}[a[i]])
        except:
            # failure -> next try
            i-=1
            j=a.rfind('(')+1
        # replace brackets in parallel (this part is executed first)
        if j:
            k=a.find(')',j)
            a=a[:j-1]+str(g(a[j:k]))+a[k+1:]
    return float(a.replace('--',''))

FWIW, the n+1th Python solution. In a blatant abuse of try-except I use a trial-and-error approach. It should handle all cases properly including stuff like -(8), --8 and g('-(1 - 3)'). It is re-entrant. Without support for the -- case which many implementations don't support, it is at 217 chars (see previous revision).

Thanks for an interesting hour on a Sunday and another 30 mins on Monday. Thanks to krubo for his nice dict.

Denudation

Another interesting approach... Identical in length to one of the other Python solutions, too. This confirms my view that using a dictionary of operators is the way to go, where possible. I wanted to do something similar in C#, but the syntax simply takes up too many chars. – Antrorse

Answer 24

Python

Number of characters: 382

Yet another Python solution, heavily using regular expression replacement. Each run through the loop the simplest expressions are computed and the results are put back into the string.

This is the unobfuscated code, unless you consider regular expressions to be obfuscated.

import re
from operator import *    
operators = dict(zip("+-/*", (add, sub, truediv, mul)))    
def compute(s):
    def repl(m):
        v1, op, v2 = m.groups()
        return str(operators[op](float(v1), float(v2)))
    while not re.match("^\d+\.\d+$", s):
        s = re.sub("([.\d]+)\s*([+-/*])\s*([.\d]+)", repl, s)
        s = re.sub("\(([.\d]+)\)", r"\1", s)
    return s

Had this idea just as I was turning in and couldn't let it go until I wrote it down and made it work.

Bratton

Nice solution... Looks very clear to me, too. It would seem that using dict/zip to store the operators is definitely a very effective approach in Python. – Antrorse

Answer 25

Python with regular expressions

Number of characters: 283

Fully obfuscated function:

import re
from operator import*
def c(e):
 O=dict(zip("+-/*()",(add,sub,truediv,mul)))
 a=[add,0];s=a
 for v,o in re.findall("(-?[.\d]+)|([+-/*()])",e):
  if v:s=[float(v)]+s
  elif o=="(":s=a+s
  elif o!=")":s=[O[o]]+s
  if v or o==")":s[:3]=[s[1](s[2],s[0])]
 return s[0]

Not obfuscated:

import re
from operator import *

def compute(s):
    operators = dict(zip("+-/*()", (add, sub, truediv, mul)))
    stack = [add, 0]
    for val, op in re.findall("(-?[.\d]+)|([+-/*()])", s):
        if val:
            stack = [float(val)] + stack
        elif op == "(":
            stack = [add, 0] + stack
        elif op != ")":
            stack = [operators[op]] + stack
        if val or op == ")":
            stack[:3] = [stack[1](stack[2], stack[0])]
    return stack[0]

I wanted to see if I cab beat the other Python solutions using regular expressions.

Couldn't.

The regular expression I'm using creates a list of pairs (val, op) where only one item in each pair is valid. The rest of the code is a rather standard stack based parser with a neat trick of replacing the top 3 cells in the stack with the result of the computation using Python list assignment syntax. Making this work with negative numbers required only two additional characters (-? in the regex).

Hush

You can save a couple of bytes by removing "()" from your operator string; zip stops at the end of the shorter list. – Hare

@gooli: Are you using Windows? By my count, the posted solution is only 273. One explanation for this may be that you counted newlines as two characters each. (Python doesn't care if you have single-char newlines, even in Windows.) Another explanation is that hit 8 when you meant 7. ;) – Raffinose

Answer 26

C#

Number of characters: 396 (updated)

(but fails the test you added with "/ -8", and I'm not inclined to fix it...

static float Eval(string s){int i,j;s=s.Trim();while((i=s.IndexOf(')'))>=0){j=s.LastIndexOf('(',i,i);s=s.Substring(0,j++)+Eval(s.Substring(j,i-j))+s.Substring(i+1);}if((i=s.LastIndexOfAny("+-*/".ToCharArray()))<0) return float.Parse(s);var r=float.Parse(s.Substring(i+1));var l=i>0?Eval(s.Substring(0,i)):(float?)null;return s[i]=='+'?(l??0)+r:(s[i]=='-'?(l??0)-r:(s[i]=='/'?(l??1)/r:(l??1)*r));}

From:

static float Eval(string s)
{
    int i, j;
    s = s.Trim();
    while ((i = s.IndexOf(')')) >= 0)
    {
        j = s.LastIndexOf('(', i, i);
        s = s.Substring(0, j++) + Eval(s.Substring(j, i - j)) + s.Substring(i + 1);
    } 
    if ((i = s.LastIndexOfAny("+-*/".ToCharArray())) < 0) return float.Parse(s);
    var r = float.Parse(s.Substring(i + 1));
    var l = i > 0 ? Eval(s.Substring(0, i)) : (float?)null;
    return s[i] == '+'
        ? (l ?? 0) + r
        : (s[i] == '-'
            ? (l ?? 0) - r
            : (s[i] == '/'
                ? (l ?? 1) / r
                : (l ?? 1) * r));
}

Adamec

Ah wonderful, a C# solution. Your use of nullable types in particular is quite interesting. 484 seems pretty good, given that you didn't have the time to tidy it up. (One improvement would be to convert the switch statement into a series of ifs, I believe.) I've posted my own C# solution now, if you wish to compare. :) – Antrorse

Answer 27

C# with Regex

Number of characters: 294

This is partially based off Jeff Moser's answer, but with a significantly simplified evaluation technique. There might even be further ways to reduce the char count, but I'm quite pleased now that there's a C# solution under 300 chars!

Fully obfuscated code:

float e(string x){while(x.Contains("("))x=Regex.Replace(x,@"\(([^\(]*?)\)",m=>e(m.Groups[1].Value).ToString());float r=0;foreach(Match m in Regex.Matches("+"+x,@"\D ?-?[\d.]+")){var o=m.Value[0];var v=float.Parse(m.Value.Substring(1));r=o=='+'?r+v:o=='-'?r-v:o=='*'?r*v:r/v;}return r;}

Clearer code:

float e(string x)
{
    while (x.Contains("("))
        x = Regex.Replace(x, @"\(([^\(]*?)\)", m => e(m.Groups[1].Value).ToString());
    float r = 0;
    foreach (Match m in Regex.Matches("+" + x, @"\D ?-?[\d.]+"))
    {
        var o = m.Value[0];
        var v = float.Parse(m.Value.Substring(1));
        r = o == '+' ? r + v : o == '-' ? r - v : o == '*' ? r * v : r / v;
    }
    return r;
}

Antrorse

Answer 28

C#

Number of Characters: 355

I took Noldorin's Answer and modified it, so give Noldorin 99% of the credit for this. Best I could do with the algorithm was using was 408 characters. See Noldorin's Answer for the clearer code version.

Changes made:
Change char comparisons to compare against numbers.
Removed some default declarations and combined same type of declarations.
Re-worked some of the if statments.

float q(string x){float v,n;if(!float.TryParse(x,out v)){x+=';';int t=0,l=0,i=0;char o,s='?',p='+';for(;i<x.Length;i++){o=s;if(x[i]!=32){s=x[i];if(char.IsDigit(x[i])|s==46|(s==45&o!=49))s='1';if(s==41)l--;if(s!=o&l==0){if(o==49|o==41){n=q(x.Substring(t,i-t));v=p==43?v+n:p==45?v-n:p==42?v*n:p==47?v/n:v;p=x[i];}t=i;if(s==40)t++;}if(s==40)l++;}}}return v;}

Edit: knocked it down some more, from 361 to 355, by removing one of the return statments.

Breathtaking

Ah, I didn't realise you'd already posted it as a new answer. Thanks for all the credit (which is probably more than I deserve, as I was stuck around 390). I'll take a look more closely at the modifications soon... the only one that I considered was changing char comparisons to use numbers. :) – Antrorse

Answer 29

SNOBOL4

Number of characters: 232

        a = pos(0) | '('
        n = span('0123456789.')
        j = '!+;!-;!*;!/;       output = e'
d       j '!' len(1) . y = "    e a . q n . l '" y "' n . r = q (l " y " r)     :s(p)"  :s(d)
        k = code(j)
        e = input
s       e ' ' = :s(s)
p       e ('(' n . i ')') = i   :s(p)f<k>
end

This is a semi-cheat. It uses code() (a variant of eval) to de-compress itself, but not to evaluate the input expression.

De-obfuscated version, without code:

        prefix = pos(0) | '('
        num = span('0123456789.')
        expr = input
spaces  expr ' ' = ''   :s(spaces)
paren   expr ('(' num . x ')') = x      :s(paren)
add     expr (prefix . pfx) (num . l) '+' (num . r) = pfx (l + r)       :s(paren)
sub     expr (prefix . pfx) (num . l) '-' (num . r) = pfx (l - r)       :s(paren)
mul     expr (prefix . pfx) (num . l) '*' (num . r) = pfx (l * r)       :s(paren)
div     expr (prefix . pfx) (num . l) '/' (num . r) = pfx (l / r)       :s(paren)
        output = expr
end

Strategy:

• First, remove all spaces (spaces)
• Whenever possible, remove parentheses surrounding a number (paren)
• Otherwise, find a simple expression involving two numbers, prefixed by '(' or at the start of the string
• If none of the above rules apply, the expression is fully evaluated. Now if the input was well formed we should be left with a number.

Example:

• 1 + (2 * 3) + 4
• 1+(2*3)+4 [spaces]
• 1+(6)+4 [mul]
• 1+6+4 [paren]
• 7+4 [add]
• 11 [add]

Polonium

Answer 30

Ruby 1.8.7

Number of characters: 620

Do try and take it easy on my implementation, it's the first time I've written an expression parser in my life! I guarantee that it isn't the best.

Obfuscated:

def solve_expression(e)
t,r,s,c,n=e.chars.to_a,[],'','',''
while(c=t.shift)
n=t[0]
if (s+c).match(/^(-?)[.\d]+$/) || (!n.nil? && n.match(/\d/) && c=='-')
s+=c
elsif (c=='-' && n=='(') || c=='('
m,o,x=c=='-',1,''
while(c=t.shift)
o+=1 if c=='('
o-=1 if c==')'
x+=c unless c==')' && o==0
break if o==0
end
r.push(m ? -solve_expression(x) : solve_expression(x))
s=''
elsif c.match(/[+\-\/*]/)
r.push(c) and s=''
else
r.push(s) if !s.empty?
s=''
end
end
r.push(s) unless s.empty?
i=1
a=r[0].to_f
while i<r.count
b,c=r[i..i+1]
c=c.to_f
case b
when '+': a=a+c
when '-': a=a-c
when '*': a=a*c
when '/': a=a/c
end
i+=2
end
a
end

Readable:

def solve_expression(expr)
  chars = expr.chars.to_a # characters of the expression
  parts = [] # resulting parts
  s,c,n = '','','' # current string, character, next character

  while(c = chars.shift)
    n = chars[0]
    if (s + c).match(/^(-?)[.\d]+$/) || (!n.nil? && n.match(/\d/) && c == '-') # only concatenate when it is part of a valid number
      s += c
    elsif (c == '-' && n == '(') || c == '(' # begin a sub-expression
      negate = c == '-'
      open = 1
      subExpr = ''
      while(c = chars.shift)
        open += 1 if c == '('
        open -= 1 if c == ')'
        # if the number of open parenthesis equals 0, we've run to the end of the
        # expression.  Make a new expression with the new string, and add it to the
        # stack.
        subExpr += c unless c == ')' && open == 0
        break if open == 0
      end
      parts.push(negate ? -solve_expression(subExpr) : solve_expression(subExpr))
      s = ''
    elsif c.match(/[+\-\/*]/)
      parts.push(c) and s = ''
    else
      parts.push(s) if !s.empty?
      s = ''
    end
  end
  parts.push(s) unless s.empty? # expression exits 1 character too soon.

  # now for some solutions!
  i = 1
  a = parts[0].to_f # left-most value is will become the result
  while i < parts.count
    b,c = parts[i..i+1]
    c = c.to_f
    case b
      when '+': a = a + c
      when '-': a = a - c
      when '*': a = a * c
      when '/': a = a / c
    end
    i += 2
  end
  a
end

Lyonnaise

That's quite good for a first attempt, and the length isn't hugely off the others anyway. Certainly, the algorithm is pretty clear. Note that you can reduce the char count significantly just by using one-letter variable names! – Antrorse

Thanks. My last bug took awhile to fix, but in general it wasn't anything brain-wracking; thankfully it functions fully. – Lyonnaise

Answer 31

Ruby 1.9

(because of the regex)

Number of characters: 296

def d(s)
  while m = s.match(/((?<pg>\((?:\\[()]|[^()]|\g<pg>)*\)))/)
    s.sub!(m[:pg], d(m[:pg][1,m[:pg].size-2]))
  end
  while m = s.match(/(-?\d+(\.\d+)?)\s*([*+\-\/])\s*(-?\d+(\.\d+)?)/)
    r=m[1].to_f.send(m[3],m[4].to_f) if %w{+ - * /}.include?m[3]
    s.sub!(m[0], r.to_s)
  end
  s
end

EDIT: Includes Martin's optimization.

Bolshevist

r=m[1].to_f.send(m[3],m[4].to_f) if %w{+ - * /}.include?m[3] – Semiconscious

Even better! I was trying to think of a nice way of doing that, and it skipped my mind. – Bolshevist

Answer 32

Ruby

Number of characters: 302

Semi-obfuscated:

def e(l)
  t=0.0;o=nil
  while l!=''
    l.sub!(/^\s+/,'')
    l.sub!(/^(-?\d+|-?\d+\.\d+)/,'')
    t=o ? t.send(o, $1.to_f) : $1.to_f if $~
    l.sub!(/^(\+|-|\*|\/)/,'')
    o=$1 if $~
    l.sub!(/^\(/,'')
    t=o ? t.send(o, e(l)) : e(l) if $~
    l.sub!(/^\)/,'')
    return t if $~
  end
  t
end

Destroys original string, also assumes expression is well-formed (only valid characters, and matching brackets).

Not obfuscated:

def evaluate_expression(expression)
  result_so_far = 0.0
  last_operator = nil

  while (expression != '')
    # remove any leading whitespace
    expression.sub!(/^\s+/, '') 

    # extract and remove leading integer or decimal number
    expression.sub!(/^(-?\d+|-?\d+\.\d+)/, '')
    if $~
      # match was successful
      number = $1.to_f
      if last_operator.nil?
        # first number, just store it
        result_so_far = number
      else
        # we have an operator, use it!
        # last_operator is a string matching '+', '-', '*' or '/'
        # just invoke the method of that name on our result_so_far
        # since these operators are just method calls in Ruby
        result_so_far = result_so_far.send(last_operator, number)
       end
    end

    # extract and remove leading operator +-*/
    expression.sub!(/^(\+|-|\*|\/)/, '')
    if $~
      # match was successful
      last_operator = $1
    end

    # extract and remove leading open bracket
    l.sub!(/^\(/, '')
    if $~
      # match successful
      if last_operator.nil?
        # first element in the expression is an open bracket
        # so just evaluate its contents recursively
        result_so_far = evaluate_expression(expression)
      else
        # combine the content of the bracketing with the
        # result so far using the last_operator
        result_so_far.send(last_operator, evaluate_expression(expression))
      end
    end

    # extract and remove leading close bracket
    l.sub!(/^\)/, '')
    if $~
      # match successful
      # this must be the end of a recursive call so
      # return the result so far without consuming the rest
      # of the expression
      return result_so_far
    end
  end
  t
end

The recursive call is controlled by the modification of the expression string, which is a bit nasty, but it seems to work.

Hauser

Could you put in a readable version as well? I'm not entirely sure how yours works. – Lyonnaise

Answer 33

Python 3K

(its 3K because / converts the result to a floating point number)

Number of characters: 808

Clear (I cannot write obfuscated code in Python XD):

def parse(line):
  ops = {"+": lambda x,y:x+y,
       "-": lambda x,y:x-y,
       "*": lambda x,y:x*y,
       "/": lambda x,y:x/y}
  def tpp(s, t):
    if len(s) > 0 and s[-1] in ops:
      f = ops[s.pop()]
      t = f(s.pop(), t)
    return t
  line = line + " "
  s = []
  t = 0
  m = None
  for c in line:
    if c in "0123456789":
      if not m:
        m = "i"
      if m == "i":
        t = t*10 + ord(c)-ord("0")
      elif m =="d":
        t = t + e*(ord(c)-ord("0"))
        e*=0.1
    elif c == ".":
      m = "d"
      e = 0.1
    elif m:
      t = tpp(s,t)
      s.append(t)
      m = None
      t = 0

    if c in ops or c == "(":
      s.append(c)
    elif c == ")":
      t = s.pop()
      s.pop()
      s.append(tpp(s,t))
      t = 0
  t = s.pop()
  if int(t) == t:
    t = int(t)
  return t

I'm not using any kind of regular expression, even the number parsing is made by hand ;-)

Quite simple, scans the line, it can be in 3 different modes (m), None that means that there's no number being parsed, "i" that means that it is parsing the integer part and "d" that means that is parsing the decimal part.

It uses a stack to store the temporary computations, when it has finished parsing a number sees if it there was an operator in the stack, in that case evals and pushes. The opening parens are just pushed and the closing parens remove the opening paren and repush the current eval.

Fairly simple and straightfordward :-)

Matildamatilde

Answer 34

Python

Number of characters: 492

Mildly obfuscated function (short variable names, no spaces around operators):

def e(s):
    q=[]
    b=1
    v=[]
    for c in s.replace(' ','')+'$':
        if c in '.0123456789' or c in '+-' and b and not v:
            v+=[c]
        else:
            if v:
                q+=[float(''.join(v))]
                v=[]
            while len(q)>=3:
                x,y,z=q[-3:]
                if type(x)==type(z)==float:
                    if y=='+':q[-3:]=[x+z]
                    elif y=='-':q[-3:]=[x-z]
                    elif y=='*':q[-3:]=[x*z]
                    elif y=='/':q[-3:]=[x/z]
                elif (x,z)==('(',')'):q[-3:]=[y]
                else:break
            if c=='$':break
            q+=[c]
            b=c!=')'
    return q[0]

I think this is relatively easy to understand. It's a pretty straightforward, naive approach. It doesn't import anything, doesn't use regex, is fully self-contained (single function, no globals, no side-effects), and should handle signed literals (positive or negative). Using more sensible variable names and adhering to recommended Python formatting increases the character count to more like 850-900, a big chunk of that from using four spaces instead of a single tab for indentation.

Raffinose

Does that char count include all the whitespace? If so, you could reduce it by a lot I'm sure. Well, the code pretty clear anyway, so good job with that. It's also a bonus that it's re-entrant. – Antrorse

My character count was what the editor told me was the size of the selection from the 'd' in "def" to the ']' at the end of the return. So that includes one character (a tab, for readability) for each indent level. This indentation is necessary for Python, so it has to be counted. Thanks for the comment; I knew I would never compete on pure character count or ingenuity. – Raffinose

Yeah, fair enough. I just observed that the other poster with a Python solution got away with using a single space for indentation, but if you're using tabs than that's equivalent. – Antrorse

I just noticed a brain fart in my code. Why did I make v a list instead of simply a string? The string not only saves 11 characters, but is also a little clearer, since it's what I eventually need anyway (Python's ''.join() isn't exactly the most intuitive). – Raffinose

Answer 35

OCaml using Camlp4 directly:

open Camlp4.PreCast

let expr = Gram.Entry.mk "expr"

EXTEND Gram
  expr:
  [   [ e1 = expr; "+"; e2 = expr -> e1 + e2
      | e1 = expr; "-"; e2 = expr -> e1 - e2 ]
  |   [ e1 = expr; "*"; e2 = expr -> e1 * e2
      | e1 = expr; "/"; e2 = expr -> e1 / e2 ]
  |   [ n = INT -> int_of_string n
      | "("; e = expr; ")" -> e ]   ];
END

let () = Gram.parse expr Loc.ghost (Stream.of_string "1-2+3*4")

OCaml using the Camlp4 stream parser extension:

open Genlex

let lex = make_lexer ["+"; "-"; "*"; "/"; "("; ")"]

let rec parse_atom = parser
  | [< 'Int n >] -> n
  | [< 'Kwd "("; e=parse_expr; 'Kwd ")" >] -> e
and parse_factor = parser
  | [< e1=parse_atom; stream >] ->
      (parser
         | [< 'Kwd "*"; e2=parse_factor >] -> e1 * e2
         | [< 'Kwd "/"; e2=parse_factor >] -> e1 / e2
         | [< >] -> e1) stream
and parse_expr = parser
  | [< e1=parse_factor; stream >] ->
      (parser
         | [< 'Kwd "+"; e2=parse_expr >] -> e1 + e2
         | [< 'Kwd "-"; e2=parse_expr >] -> e1 - e2
         | [< >] -> e1) stream

let () =
  Printf.printf "%d\n" (parse_expr(lex(Stream.of_string "1 + 2 * (3 + 4)")));;

Cerelia

Answer 36

C#, 264 characters

Strategy: the first 2 lines get rid of parentheses by induction. Then I split by \-?[\d.]+ to get numbers and operators. then using aggregate to reduce the string array to a double value.

Variable explanations

m is parenthesized expression with no nested parentheses.
d is a placeholder for that awkward TryParse syntax.
v is the accumulator for the final value
t is the current token.

float E(string s){var d=999f;while(d-->1)s=Regex.Replace(s,@"(([^(]?))",m=>E(m.Groups[1].Value)+"");return Regex.Split(s,@"(-?[\d.]+)").Aggregate(d,(v,t)=>(t=t.Trim()).Length==0?v:!float.TryParse(t,out d)?(s=t)==""?0:v:s=="/"?v/d:s=="-"?v-d:s==""?v*d:v+d);}

    float F(string s) {
        var d=999f;
        while(d-->1)
            s=Regex.Replace(s,@"\(([^\(]*?)\)",m=>F(m.Groups[1].Value)+"");
        return Regex.Split(s, @"(\-?[\d\.]+)")
            .Aggregate(d, (v, t) => 
                (t=t.Trim()).Length == 0 ? v :
                !float.TryParse(t, out d) ? (s=t) == "" ? 0 : v :
                s == "/" ? v / d :
                s == "-" ? v - d :
                s == "*" ? v * d :
                           v + d);
    }

EDIT: shamelessly stole parts from noldorin's answer, reused s as the operator variable.

EDIT: 999 nested parentheses should be enough for anyone.

Inveigle

Pretty nice. Looks fairly similar to my regex solution in fact. It's all shown me a few interesting tricks for reducing count such as +"" instead of ToString. Well done for throwing in the LINQ, too. – Antrorse

wow, I didn't see that one :) I might not have bothered posting this answer if I had. I think a lot of the differences simply come from my limited understanding of regex – Inveigle

Hehe, no worries. I'm just quite surprised how similar many parts of our solution are. You've certainly tempted me to reduce my char count now... I know I certainly can a bit. – Antrorse

Answer 37

PowerBASIC

Number of characters: ~400

A bit ugly, but it works. :) I'm sure regexp would have made it even smaller.

DEFDBL E,f,i,z,q,a,v,o  
DEFSTR s,c,k,p

FUNCTION E(s)  

    i=LEN(s)  
    DO  
        IF MID$(s,i,1)="("THEN  
            q=INSTR(i,s,")")  
            s=LEFT$(s,i-1)+STR$(E(MID$(s,i+1,q-i-1)))+MID$(s,q+1)  
        END IF  
        i-=1  
    LOOP UNTIL i=0  

    k="+-*/"  
    DIM p(PARSECOUNT(s,ANY k))  
    PARSE s,p(),ANY k  

    a=VAL(p(0))

    FOR i=1TO LEN(s)
        c=MID$(s,i,1)
        q=INSTR(k,c)
        IF q THEN
            z+=1
            IF o=0 THEN o=q ELSE p(z)=c+p(z)
            IF TRIM$(p(z))<>"" THEN
                v=VAL(p(z))
                a=CHOOSE(o,a+v,a-v,a*v,a/v)
                o=0
            END IF
        END IF
    NEXT

    E=a  
END FUNCTION  

Coronation

Answer 38

C++

Chars: 1670

 // not trying to be terse here
#define DIGIT(c)((c)>='0' && (c) <= '9')
#define WHITE(pc) while(*pc == ' ') pc++
#define LP '('
#define RP ')'

bool SeeNum(const char* &pc, float& fNum){
    WHITE(pc);
    if (!(DIGIT(*pc) || (*pc=='.'&& DIGIT(pc[1])))) return false;
    const char* pc0 = pc;
    while(DIGIT(*pc)) pc++;
    if (*pc == '.'){
        pc++;
        while(DIGIT(*pc)) pc++;
    }
    char buf[200];
    int len = pc - pc0;
    strncpy(buf, pc0, len); buf[len] = 0;
    fNum = atof(buf);
    return true;
}

bool SeeChar(const char* &pc, char c){
    WHITE(pc);
    if (*pc != c) return false;
    pc++;
    return true;
}

void ParsExpr(const char* &pc, float &fNum);

void ParsPrim(const char* &pc, float &fNum){
    if (SeeNum(pc, fNum));
    else if (SeeChar(pc, LP)){
        ParsExpr(pc, fNum);
        if (!SeeChar(pc, RP)) exit(0);
    }
    else exit(0); // you can abort better than this
}

void ParsUnary(const char* &pc, float &fNum){
    if (SeeChar(pc, '-')){
        pc+;
        ParsUnary(pc, fNum);
        fNum = -fNum;
    }
    else {
        ParsPrim(pc, fNum);
    }
}

void ParsExpr(const char* &pc, float &fNum){
    ParsUnary(pc, fNum);
    float f1 = 0;
    while(true){
        if (SeeChar(pc, '+')){
            ParsUnary(pc, f1);
            fNum += f1;
        }
        else if (SeeChar(pc, '-')){
            ParsUnary(pc, f1);
            fNum -= f1;
        }
        else if (SeeChar(pc, '*')){
            ParsUnary(pc, f1);
            fNum *= f1;
        }
        else if (SeeChar(pc, '/')){
            ParsUnary(pc, f1);
            fNum /= f1;
        }
        else break;
    }
}

This is just LL1 (recursive descent). I like to do it this way (although I use doubles) because it's plenty fast, and easy to insert routines to handle precedence levels.

Reproduction

Answer 39

Java

Number of Characters: 376

Updated version, now with more ? operator abuse!

Fully obfuscated solution:

static double e(String t){t="("+t+")";for(String s:new String[]{"+","-","*","/","(",")"})t=t.replace(s," "+s+" ");return f(new Scanner(t));}static double f(Scanner s){s.next();double a,v=s.hasNextDouble()?s.nextDouble():f(s);while(s.hasNext("[^)]")){char o=s.next().charAt(0);a=s.hasNextDouble()?s.nextDouble():f(s);v=o=='+'?v+a:o=='-'?v-a:o=='*'?v*a:v/a;}s.next();return v;}

Clear/semi-obfuscated function:

static double evaluate(String text) {
    text = "(" + text + ")";
    for (String s : new String[] {"+", "-", "*", "/", "(", ")" }) {
        text = text.replace(s, " " + s + " ");
    }
    return innerEval(new Scanner(text));
}

static double innerEval(Scanner s) {
    s.next();
    double arg, val = s.hasNextDouble() ? s.nextDouble() : innerEval(s);
    while (s.hasNext("[^)]")) {
        char op = s.next().charAt(0);
        arg = s.hasNextDouble() ? s.nextDouble() : innerEval(s);
        val =
            op == '+' ? val + arg :
            op == '-' ? val - arg :
            op == '*' ? val * arg :
            val / arg;
    }
    s.next();
    return val;
}

Licit

Answer 40

F#

Number of characters: 461

Here is Marc Gravell's solution (essentially) converted from C# to F#. The char count is scarecly better, but I thought I'd post it anyway out of interest.

Obfuscated code:

let e x=
 let rec f(s:string)=
  let i=s.IndexOf(')')
  if i>0 then
   let j=s.LastIndexOf('(',i)
   f(s.Substring(0,j)+f(s.Substring(j+1,i-j-1))+s.Substring(i+1))
  else
   let o=[|'+';'-';'*';'/'|]
   let i=s.LastIndexOfAny(o)
   let j=s.IndexOfAny(o,max(i-2)0,2)
   let k=if j<0 then i else j
   if k<0 then s else
    let o=s.[k]
    string((if o='+'then(+)else if o='-'then(-)else if o='*'then(*)else(/))(float(f(s.Substring(0,k))))(float(s.Substring(k+1))))
 float(f x)

Antrorse

Yeah I tried something similar with F# yesterday but it both feels very "non F#" and is still more chars then my other solution ;(. Silly that F# has so horrible string handling. – Jasmin

Answer 41

PHP

Number of characters: 170

Fully obfuscated function:

function a($a,$c='#\(([^()]*)\)#e',$d='a("$1","#^ *-?[\d.]+ *\S *-?[\d.]+ *#e","\$0")'){$e='preg_replace';while($a!=$b=$e($c,$d,$a))$a = $b;return$e('#^(.*)$#e',$d,$a);}

Clearer function:

function a($a, $c = '#\(([^()]*)\)#e', $d = 'a("$1", "#^ *-?[\d.]+ *\S *-?[\d.]+ *#e", "\$0")') {
    $e = 'preg_replace';
    while ($a != $b = $e($c, $d, $a)) {
        $a = $b;
    }
    return $e('#^(.*)$#e', $d, $a);
}

Tests:

assert(a('1 + 3 / -8') === '-0.5');
assert(a('2*3*4*5+99') === '219');
assert(a('4 * (9 - 4) / (2 * 6 - 2) + 8') === '10');
assert(a('1 + ((123 * 3 - 69) / 100)') === '4');
assert(a('2.45/8.5*9.27+(5*0.0023)') === '2.68344117647');
assert(a(' 2 * 3 * 4 * 5 + 99 ') === '219');

Pawsner

The e modifier to preg_replace violates the rule that evals are forbidden. – Countless

Answer 42

I'm surprised nobody did it in Lex / Yacc or equivalent.

That would seem to yield the shortest source code that was also readable / maintainable.

Reproduction

I was about to do it with ANTLR, but it was larger that you could think in first instance xD – Matildamatilde

Lex/Yacc is good for writing real parsers, but if your requirements are simple enough, you can do it better (smaller) without. – Insomnia

@Chris: I'm inclined to agree, but I thought somebody might have tried it. – Reproduction

I might try it, but I've currently got a plain C solution down to 209 characters. Getting there. – Insomnia

Answer 43

Perl

Number of characters: 93

Fully obfuscated function: (93 characters if you join these three lines into one)

$_="(@ARGV)";s/\s//g;$n=qr/(-?\d+(\.\d+)?)/;
while(s.\($n\)|(?<=\()$n[-+*/]$n.eval$&.e){}
print

Clear/semi-obfuscated function:

$_="(@ARGV)";            # Set the default var to "(" argument ")"
s/\s//g;                 # Strip all spaces from $_
$n=qr/(-?\d+(\.\d+)?)/;  # Compile a regex for "number"

# repeatedly replace the sequence "(" NUM ")" with NUM, or if there aren't
# any of those, replace "(" NUM OP NUM with the result
# of doing an eval on just the NUM OP NUM bit.
while(s{\($n\)|(?<=\()$n[-+*/]$n}{eval$&}e){}

# print $_
print

I think this is pretty well explained in the "clear" version. The two main insights are that you can make the code uniform by surrounding the argument with parentheses at the start (special cases cost characters), and that it is sufficient, albeit massively inefficient, to only process stuff right next to an open parenthesis, replacing it with its result.

It's probably easiest to run this code as:

perl -le '$_="(@ARGV)";s/\s//g;$n=qr/(-?\d+(\.\d+)?)/;while(s.\($n\)|(?<=\()$n[-+*/]$n.eval$&.e){}print' '4 * (9 - 4) / (2 * 6 - 2) + 8'

Grad

Interesting, but does the "eval" kinda break the rules? – Escarp

Ah, okay, it wasn't clear to me that "eval" was disallowed; I thought the description was saying that his "no BODMAS" rule was sufficient guard against that. Very well, I'll try another solution without 'eval'. – Grad

Yeah, sorry. The rules were to explicitly disallow "eval". It was just a suspicion that BODMAS ought to prevent against it, but not necessarily. – Antrorse