评估一串简单的数学表达式 [英] Evaluating a string of simple mathematical expressions
问题描述
挑战
这是我自己的发明所面临的挑战，尽管如果它以前出现在网络上的其他地方，我也不会感到惊讶.
编写一个需要一个函数的函数 这是一个论点 简单字符串的表示形式 数学表达式和求值 它作为浮点值.一种 简单表达"可以包括以下任何一种 以下内容:正面或负面 十进制数字， + ，-， * ，/，(，). 表达式使用(正常)前缀表示法. 运营商应在 它们出现的顺序，即 not BODMAS ， 虽然括号应该正确 观察，当然.该函数应返回 any 可能表达式的正确结果 这种形式的.但是，该功能没有 处理格式错误的表达式(即语法错误的表达式).
表达式示例:
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或等效函数，或者即时编译和执行代码. (但是，我对"no BODMAS"的说明几乎可以保证这一点.)除此之外，没有任何限制.我期待在这里找到一些Regex解决方案，但不仅仅可以看到更多.
现在，我主要对这里的C#/.NET解决方案感兴趣，但是任何其他语言也完全可以接受(特别是对于功能/混合方法，是F#和Python).我尚未决定是否接受最短或最巧妙的解决方案(至少对于语言而言)作为答案，但是我欢迎使用任何语言的任何形式的解决方案，除非我上面刚刚禁止的内容！
我的解决方案
我现在在此处发布了我的C#解决方案(403字符). 更新:我的新解决方案已被击败旧版本在 294个字符的帮助下，经过一些可爱的正则表达式的帮助！我怀疑这会以较轻的语法(尤其是函数/动态语言)轻松地被某些语言所击败，并且已经被证明是正确的，但是我很好奇是否有人还能在C#中击败它. >
更新
我已经看到了一些非常狡猾的解决方案.感谢所有发表过的人.尽管我还没有测试过它们中的任何一个，但我还是要相信人们，并假设他们至少可以使用所有给定的示例.
仅需注意，重入功能(即线程安全性)不是对该功能的要求，尽管这是一个奖励.
格式
为了便于比较，请以以下格式发布所有答案:
语言
字符数:???
完全模糊的功能:
(code here)清除/半混淆功能:
(code here)关于使用的算法/智能快捷键的任何注释.
Perl(无评估)
字符数: 167 106 (有关106个字符的版本，请参见下文)
完全模糊的功能:(如果将这三行合并为一个，则为167个字符)
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){}$_}
清除/模糊化版本:
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
$_
}
我最初误读了规则，所以我提交了带有"eval"的版本.这是一个没有它的版本.
当我意识到+，-，/和*的字符代码中的最后一个八进制数字不同并且ord(undef)为0时，才有了最新的见解.让我将调度表@a设置为数组，然后仅在位置7 & ord($3)处调用代码.
有一个明显的地方可以剃掉另一个字符-将q""更改为''-但这将使其更难剪切并粘贴到外壳中.
更短
字符数: 124 106
考虑到 ephemient 所做的编辑，现在减少到124个字符:(将两行合并为一个)
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;$_}
仍要保持镇静
字符数: 110 106
下面的红宝石解决方案使我进一步前进，尽管我无法达到其104个字符:
sub e{($_)=@_;$n='( *-?[.\d]++ *)';
s:\($n\)|$n(.)$n:(($1,$2-$4,$4&&$2/$4,$2*$4,$2+$4)x9)[.8*ord$3]:e?e($_):$_}
我不得不屈服并使用''.红宝石send技巧对解决这个问题确实有用.
从石头里榨水
字符数:106
为了避免被零除检查而小的扭曲.
sub e{($_)=@_;$n='( *-?[.\d]++ *)';
s:\($n\)|$n(.)$n:($1,0,$2*$4,$2+$4,0,$2-$4)[7&ord$3]//$2/$4:e?e($_):$_}
以下是此功能的测试工具:
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'
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.
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'
这篇关于评估一串简单的数学表达式的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
