Evaluer une chaîne d’expressions mathématiques simples

Défi

Voici le défi (de ma propre invention, même si je ne serais pas surpris s’il est déjà apparu ailleurs sur le Web).

Écrivez une fonction qui prend un seul argument qui est une représentation sous forme de chaîne d’une expression mathématique simple et l’évalue comme une valeur à virgule flottante. Une “expression simple” peut inclure l’un des éléments suivants: nombres décimaux positifs ou négatifs, + , , * , / , ( , ) . Les expressions utilisent une notation infixe (normale). Les opérateurs doivent être évalués dans l’ordre où ils apparaissent, c’est-à-dire pas comme dans BODMAS , bien que les crochets doivent être correctement observés, bien sûr. La fonction doit renvoyer le résultat correct pour toute expression possible de cette forme. Cependant, la fonction n’a pas à gérer les expressions mal formées (c’est-à-dire avec une syntaxe incorrecte).

Exemples d’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... 

Règles

Je prévois une forme de “tromperie” / astuce ici, alors s’il vous plait, laissez-moi vous prévenir! En sortingchant, je fais référence à l’utilisation de la fonction eval ou équivalente dans des langages dynamics tels que JavaScript ou PHP, ou encore pour comstackr et exécuter du code à la volée. (Je pense que ma spécification de “no BODMAS” est pratiquement garantie). En dehors de cela, il n’y a pas de ressortingctions. Je prévois quelques solutions Regex ici, mais ce serait bien de voir plus que cela.

Maintenant, je suis principalement intéressé par une solution C # /. NET ici, mais tout autre langage serait parfaitement acceptable (en particulier, F # et Python pour les approches fonctionnelles / mixtes). Je n’ai pas encore décidé si j’allais accepter la solution la plus courte ou la plus ingénieuse (du moins pour le langage), mais j’accueillerais toute forme de solution dans n’importe quelle langue , sauf ce que je viens d’interdire !

Ma solution

J’ai maintenant posté ma solution C # ici (403 caractères). Mise à jour: Ma nouvelle solution a battu l’ancienne de manière significative avec 294 caractères , avec l’aide d’un peu de regex! Je soupçonnais que cela serait facilement battu par certains langages avec une syntaxe plus légère (en particulier les syntaxiques fonctionnelles / dynamics), et que cela avait été prouvé, mais je serais curieux de savoir si quelqu’un pouvait battre ça en C #.

Mettre à jour

J’ai déjà vu des solutions très astucieuses. Merci à tous ceux qui en ont posté un. Bien que je ne les ai pas encore testés, je vais faire confiance aux gens et supposer qu’ils travaillent au moins avec tous les exemples donnés.

Juste pour la note, la ré-appartenance (c’est-à-dire la sécurité des threads) n’est pas une exigence pour la fonction, bien que ce soit un bonus.


Format

Veuillez poster toutes les réponses dans le format suivant afin de faciliter la comparaison:

La langue

Nombre de caractères: ???

Fonction complètement obscurcie:

 (code here) 

Fonction claire / semi-masquée:

 (code here) 

Toutes les notes sur l’algorithme / raccourcis astucieux qu’il prend.


Perl (pas d’évaluation)

Nombre de caractères: 167 106 (voir ci-dessous pour la version de 106 caractères)

Fonction complètement obscurcie: (167 caractères si vous reliez ces trois lignes en une)

 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){}$_} 

Version claire / désencombrée:

 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 $_ } 

J'avais mal interprété les règles au départ, alors j'avais envoyé une version avec "eval". Voici une version sans elle.

Le dernier aperçu est venu quand j'ai réalisé que le dernier chiffre octal dans les codes de caractères pour + , - , / et * est différent, et que ord(undef) est 0. Cela me permet de configurer la table de dissortingbution @a comme un tableau, et appelez simplement le code à l'emplacement 7 & ord($3) .

Il y a un endroit évident pour raser un autre personnage - changez q"" en '' - mais cela rendrait plus difficile le copier-coller dans la shell.

Encore plus court

Nombre de caractères: 124 106

Compte tenu des modifications apscopes par ephemient , il ne rest plus que 124 caractères: (joignez les deux lignes en une seule)

 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;$_} 

Encore plus court

Nombre de caractères: 110 106

La solution rbuy ci-dessous me pousse plus loin, bien que je ne puisse pas atteindre ses 104 caractères:

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

Je devais céder et utiliser '' . Cette astuce d' send rbuy est vraiment utile pour ce problème.

Presser de l'eau d'une pierre

Nombre de caractères: 106

Une petite contorsion pour éviter le contrôle de la division par zéro.

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

Voici le harnais de test pour cette fonction:

 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' 

Assembleur

427 octets

Obfusqué, assemblé avec l’excellent A86 dans un exécutable .com:

 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: Source non masquée:

  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 

Rubis

Nombre de caractères: 103

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

Ceci est une version non récursive de la solution de The Wicked Flea. Les sous-expressions entre parenthèses sont évaluées de bas en haut plutôt que de haut en bas.

Edit : La conversion de ‘while’ en récursivité conditionnelle + tail a enregistré quelques caractères, elle n’est donc plus non récursive (bien que la récursivité ne soit pas sémantiquement nécessaire.)

Edit : Emprunter l’idée de Daniel Martin de fusionner les regexps permet d’économiser 11 caractères supplémentaires!

Edit : Cette récursivité est encore plus utile que je le pensais! x.to_f peut être réécrit comme e(x) , si x contient un seul numéro.

Edit : Utiliser ‘ or ‘ au lieu de ‘ || ‘permet de supprimer une paire de parenthèses.

Version longue:

 # 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 ssortingng 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 ssortingng doesn't look like a non-sortingvial expression, assume it is a # ssortingng representation of a real number and attempt to parse it x.to_f end end