Golf de code : Évaluation des Expressions mathématiques

Question

Défi

Voici le défi (de ma propre invention, bien que je ne serais pas surpris si elle a déjà paru ailleurs sur le web).

Écrire une fonction qui prend un seul argument qui est un représentation sous forme de chaîne d'un simple expression mathématique et évalue comme une valeur à virgule flottante. Un "la simple expression" peuvent inclure suivantes: positif ou négatif les nombres décimaux, +, -, *, /, (, ). Expressions (normal) notation infixe. Les opérateurs devraient être évalués dans le ordre où ils apparaissent, c'est à dire pas comme dans BODMAS, bien que les crochets devraient être correctement observé, bien sûr. La fonction doit retourner le résultat correct pour toute expression possible de cette forme. Cependant, la fonction n'a pas pour traiter la malformation de expressions (c'est à dire ceux avec une mauvaise syntaxe).

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

Les règles

Je prévois une certaine forme de "tricher"/astuces ici, donc merci de me prévenir contre elle! En trichant, je me réfère à l'utilisation de l' eval ou l'équivalent de la fonction dans les langages dynamiques tels que JavaScript ou PHP, ou également la compilation et l'exécution de code à la volée. (Je pense que mon spécification de "pas de BODMAS" a à peu près garanti à cela, cependant.) En dehors de cela, il n'y a pas de restrictions. J'anticipe un peu de Regex solutions ici, mais il serait agréable de voir plus que ça.

Maintenant, je m'intéresse principalement en C#/.NET solution ici, mais toute autre langue serait parfaitement acceptable (en particulier, F# et Python pour la fonctionnelle/approches mixtes). Je n'ai pas encore décidé si je vais accepter le plus court ou le plus ingénieux de la solution (au moins pour la langue) comme la réponse, mais je suis favorable à toute forme de solution dans n'importe quelle langue, à l'exception de ce que je viens interdit au-dessus!

Ma Solution

Maintenant, j'ai posté mon C# solution ici (403 caractères). Mise à jour: Ma nouvelle solution a battu l'ancienne de manière significative à 294 caractères, avec l'aide d'un peu de belle regex! Je me doutais bien que cela permettra d'obtenir facilement battu par certains des langues avec le plus léger de la syntaxe (en particulier le fonctionnel/dynamique), et ont été prouvés à droite, mais je serais curieux de savoir si quelqu'un pourrait battre ce en C# encore.

Mise à jour

J'ai vu quelques très rusé déjà des solutions. Merci à tous ceux qui ont posté. Bien que je n'ai pas testé l'un d'eux encore, je vais faire confiance aux gens et assument-ils au moins travailler avec tous les exemples donnés.

Juste pour la remarque, re-entrancy (c'est à dire thread-safety) n'est pas une exigence pour la fonction, si c'est un bonus.

---

Format

Merci de poster toutes les réponses dans le format suivant dans le but de faciliter la comparaison:

Langue

Nombre de caractères: ???

Entièrement codé à la fonction:

(code here)

Clair/semi-caché de la fonction:

(code here)

Toutes les notes sur l'algorithme/intelligent raccourcis qu'il faut.

---

Answer 1

<h2>Assembleur<p><strong>427 octets</strong></p><p>Obscurcis, assemblés avec l' excellent <a href="http://eji.com/a86/" rel="nofollow">A86</a> en un exécutable .com :</p><pre><code></code></pre><p><strong>EDIT :</strong> Source unobfuscated :</p><pre><code></code></pre></h2>

Answer 2

Perl (pas d'eval)

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

Entièrement obscurci fonction: (167 caractères si vous vous joignez à ces trois lignes en un)

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

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

J'avais mal lu les règles au départ, donc, j'avais présenté une version avec "eval". Voici une version sans elle.

Les dernières peu de perspicacité est venu quand j'ai réalisé que le dernier chiffre octal dans les codes de caractère pour +, -, /, et * est différent, et que c' ord(undef) est de 0. Cela me permet de configurer l'envoi de la table @a comme un tableau, et il suffit d'invoquer le code à l'emplacement de 7 & ord($3).

Il y a un endroit parfait pour se raser un caractère de plus - variation q"" en '' - mais qui rendrait plus difficile à couper et coller dans la coque.

Encore plus court

Nombre de caractères: 124 106

La prise de modifications par ephemient en compte, c'est maintenant à 124 caractères: (joindre les deux lignes sur un seul)

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

Plus courte encore

Nombre de caractères: 110 106

Le rubis de la solution vers le bas ci-dessous est de me pousser plus loin, si je ne peux 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($_):$_}

J'ai eu à donner et utiliser ''. Que ruby send astuce est très utile pour ce problème.

Presser l'eau de la pierre

Nombre de caractères: 106

Une petite contorsion pour éviter la division par zéro de la vérifier.

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 test du harnais 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'

Answer 3

Ruby

Nombre de caractères: 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

C'est un non-récursive version des Méchants aux Puces de la solution. Entre parenthèses sous-expressions sont évaluées bottom-up plutôt que top-down.

Edit: la Conversion de l'", alors que " à une condition + queue de récursivité a sauvé quelques caractères, de sorte qu'il n'est plus non-récursive (bien que la récursivité n'est pas sémantiquement nécessaire.)

Edit: l'Emprunt Daniel Martin, l'idée de fusionner les expressions régulières enregistre encore 11 caractères!

Edit: Que la récursivité est encore plus utile que je ne le pensais! x.to_f peut être réécrit en e(x), si x contient un numéro unique.

Edit: à l'Aide de 'or"au lieu de"||' permet à une paire de parenthèses pour être abandonné.

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

Answer 4

<h1>C (VS2005)<p><strong>Nombre de caractères : 1360</strong></p><p>Abus de préprocesseur et mises en garde pour le plaisir du code mise en page (défiler vers le bas pour voir) :</p><pre><code></code></pre></h1>

Answer 5

<h2>Haskell<p><strong>Nombre de caractères : 182</strong></p><p>Aucune tentative d’intelligence, juste quelques compression : 4 lignes, 312 octets.</p><pre><code></code></pre><p>Et maintenant, vraiment entrer dans l’esprit du golf, de 3 lignes et de 182 octets :</p><pre><code></code></pre><p>A explosé :</p><pre><code></code></pre></h2>