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

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 提供, 点击上面的

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

- gnovice · Answer 1

MATLAB (v7.8.0)

字符数: 239

混淆函数:

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

清除（更清晰）函数：

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

测试:

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

简介：正则表达式和递归的结合。这是我目前为止能够做到的最好的，没有作弊使用EVAL。

- Marc Gravell · Answer 2

C#

字符数目：396（已更新）

但它在你添加的“/ -8”测试中失败了，我不想修复它...

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

来自：

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

- elifiner · Answer 3

Python与正则表达式

字符数：283

完全混淆的函数：

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]

未混淆：

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]

我想看看是否可以使用正则表达式击败其他Python解决方案。

不行。

我正在使用的正则表达式创建了一个对（val，op）进行配对的列表，其中每个对中只有一个项目是有效的。其余的代码是一个相当标准的基于堆栈的解析器，具有使用Python列表分配语法将堆栈中的前3个单元格替换为计算结果的巧妙技巧。仅需两个额外的字符（-？在正则表达式中）即可使负数起作用。

- elifiner · Answer 4

Python

字符数：382

这是另一个使用正则表达式替换的 Python 解决方案。每次循环时都会计算最简单的表达式，并将结果放回字符串中。

这是未经混淆的代码，除非您认为正则表达式是混淆的。

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

我刚要睡觉时突然有了这个想法，一直想不通直到写下来并让它实现。

- stephan · Answer 5

Python

字符数：235

完全混淆的函数：

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('--',''))

半混淆：

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，以下是第n+1个Python解决方案。我滥用了try-except并采用了试错法。它应该可以正确处理所有情况，包括像-(8)，--8和g('-(1 - 3)')这样的内容。它是可重入的。不支持许多实现不支持的--情况，长度为217个字符（请参见以前的版本）。

感谢一个有趣的周日和另外30分钟的星期一。感谢krubo提供的漂亮字典。

- samuil · Answer 6

Ruby

字符数： ~~217~~ 179

~~这是迄今为止最短的Ruby解决方案（基于RegExp的解决方案在字符串包含少量括号组时会产生错误答案）~~ ——不再正确。基于正则表达式和替换的解决方案更短。这个解决方案基于累加器堆栈，并从左到右解析整个表达式。它是可重入的，并且不修改输入字符串。它可能被指责违反不使用eval的规则，因为它调用Float的方法与它们的数学助记符（+，-，/，*）名称相同。

混淆代码（旧版本，在下面进行了微调）：

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

更多的混淆代码：

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

清晰易懂的代码：

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

- Daniel Huckstep · Answer 7

Ruby 1.9

（由于正则表达式）

字符数量：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

编辑：包括Martin的优化。

- Robert K · Answer 8

Ruby 1.8.7

字符数：620

请对我的实现温柔一点，这是我生命中第一次编写表达式解析器！我保证它不是最好的。

混淆：

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

易读性：

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

- finnw · Answer 9

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

这是一个半欺骗的方法。它使用code()（eval的变体）来解压缩自身，但不用于评估输入表达式。

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

策略：

首先，删除所有空格 (spaces)
尽可能地删除括号中的数字 (paren)
否则，查找涉及两个数字的简单表达式，以 '(' 为前缀或在字符串开头
如果以上规则都不适用，则完全计算表达式。现在，如果输入格式正确，我们应该得到一个数字。

例子：

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

- Crispy · Answer 10

C#

字符数：355

我采用了Noldorin的答案并对其进行了修改，因此99%的功劳归于Noldorin。使用该算法最好的结果是408个字符。请参见Noldorin的答案以获得更清晰的代码版本。

所做的更改：
将字符比较更改为与数字进行比较。
删除了一些默认声明并组合了相同类型的声明。
重新设计了一些if语句。

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

编辑：通过删除一个返回语句，将其从361降至355。