评估一串简单数学表达式的字符串

Question

评估一串简单数学表达式的字符串

mathparsingcode-golftext-parsinginfix-notation

76

挑战

这是我的编写的一个挑战（尽管我不会感到惊讶，如果它在网上以前已出现）。

编写一个函数，该函数接受一个单一参数，该参数是一个简单数学表达式的字符串表示形式，并将其评估为浮点值。 "简单表达式" 可以包括以下任何内容：正或负十进制数、+, -, *, /, (, )。表达式使用 (常规) 中缀表示法。操作符应按照它们出现的顺序进行求值,即不像BODMAS那样，当然，必须正确观察括号。该函数应返回此形式的任何可能表达式的正确结果。但是，该函数不需要处理格式错误的表达式（即具有错误语法的表达式）。

表达式示例：
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...
规则

我预计会有某种形式的“作弊”/聪明才智，所以请允许我提前警告！通过作弊，我指的是在动态语言（例如JavaScript或PHP）中使用eval或等效函数，或者即时编译和执行代码。（然而，我的“禁止BODMAS”规定几乎已经保证了此项。）除此之外，没有任何限制。我预计会有几个正则表达式解决方案，但很高兴看到不仅仅是这样。

现在，我主要关注的是一个C#/.NET解决方案，但任何其他语言也完全可以接受（特别是函数式/mixed方法的F#和Python）。至少对于该语言，我尚未决定是否接受最短或最巧妙的解决方案作为答案，但我欢迎任何语言的任何形式的解决方案，除了上面刚才禁止的东西！

我的解决方案

我现在已经发布了我的C#解决方案here（403 chars）。更新：我的新解决方案使用一些可爱的正则表达式，在294 chars显著打败了旧的版本！我怀疑这将轻松被一些语法更轻的语言（特别是funcional/dynamic ones）所击败，并且已经被证明是正确的，但如果有人仍然可以在C#中击败这个问题，我会感到好奇。

更新

我已经看到了一些非常聪明的解决方案。感谢所有发布过解决方案的人。虽然我还没有测试任何一个，但我会相信人们并假设它们至少能够处理所有给定的示例。

只为记录，重入性（即线程安全）不是该函数的要求，尽管它是一个奖励。

格式

请按以下格式发布所有答案，以便易于比较：
语言

字符数：???

完全混淆的函数：
(code here)
清晰/半模糊的函数：
(code here)
关于算法/巧妙的快捷方式，有何说明。

- Noldorin

2

你可能想让你的第一个例子等于0.125（移动小数点），而你的第二个例子左边应该是99（多了一个9）。 - John Y

我也将此设为社区维基（最初忘记这样做了），因为这似乎是这种问题最合适的方式。 - Noldorin

1

你应该添加一个缺少BODMAS的重要示例，例如“1 + 1 * 3 = 6”。 - Ben Blank

3

啊，我一直在想第一次关闭投票会是什么时候。向所有投票者说明：StackOverflow上已经有足够多的开放式代码高尔夫问题了。共识似乎是它们很好——主要只是一些乐趣。 - Noldorin

3

我倾向于同意这很好，特别是因为“维基”。 - Marc Gravell

显示剩余12条评论

43个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- eisberg · Answer 1

PHP

字符数：170个

完全混淆的函数：

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);}

更清晰的函数：

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);
}

测试：

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');

- Mike Dunlavey · Answer 2

0

我很惊讶没有人用Lex/Yacc或等效工具来完成它。

这似乎可以产生最短的源代码，同时也易于阅读和维护。

- Mike Dunlavey

我本来想用ANTLR来做这件事，但它比你最初想象的要大xD。 - fortran

2

Lex/Yacc适合编写真正的解析器，但如果您的要求足够简单，那么不使用它们可以更好（更小）。 - Chris Lutz

@Chris：我倾向于同意，但我认为可能有人尝试过。 - Mike Dunlavey

我可能会尝试一下，但目前我已经将一个简单的C语言解决方案缩减到了209个字符。正在努力中。 - Chris Lutz

- Daniel Martin · Answer 3

Perl

字符数：93个

完全混淆函数：（如果将这三行合并为一行，则有93个字符）

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

清晰/半混淆函数：

$_="(@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

我认为在“清晰”版本中已经很好地解释了这一点。两个主要的见解是，你可以通过在开头用括号括起参数来使代码统一（特殊情况会增加字符数），并且仅处理紧挨着开括号旁边的内容就足够了，虽然效率极低，但可以将其替换为其结果。

最简单的运行此代码的方法可能是：

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'