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

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

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

- Noldorin · Answer 1

C#正则表达式

字符数：294

这部分内容基于Jeff Moser的回答，但使用了大大简化的评估技术。可能还有其他方法来减少字符数，但我现在很高兴能够在300个字符以下提供C#解决方案!

完全混淆的代码:

float e(string x){while(x.Contains("("))x=Regex.Replace(x,@"\(([^\(]*?)\)",m=>e(m.Groups[1].Value).ToString());float r=0;foreach(Match m in Regex.Matches("+"+x,@"\D ?-?[\d.]+")){var o=m.Value[0];var v=float.Parse(m.Value.Substring(1));r=o=='+'?r+v:o=='-'?r-v:o=='*'?r*v:r/v;}return r;}

更清晰的代码：

float e(string x)
{
    while (x.Contains("("))
        x = Regex.Replace(x, @"\(([^\(]*?)\)", m => e(m.Groups[1].Value).ToString());
    float r = 0;
    foreach (Match m in Regex.Matches("+" + x, @"\D ?-?[\d.]+"))
    {
        var o = m.Value[0];
        var v = float.Parse(m.Value.Substring(1));
        r = o == '+' ? r + v : o == '-' ? r - v : o == '*' ? r * v : r / v;
    }
    return r;
}

- John Y · Answer 2

Python

字符数：492

轻度混淆函数（短变量名，运算符周围没有空格）：

def e(s):
    q=[]
    b=1
    v=[]
    for c in s.replace(' ','')+'$':
        if c in '.0123456789' or c in '+-' and b and not v:
            v+=[c]
        else:
            if v:
                q+=[float(''.join(v))]
                v=[]
            while len(q)>=3:
                x,y,z=q[-3:]
                if type(x)==type(z)==float:
                    if y=='+':q[-3:]=[x+z]
                    elif y=='-':q[-3:]=[x-z]
                    elif y=='*':q[-3:]=[x*z]
                    elif y=='/':q[-3:]=[x/z]
                elif (x,z)==('(',')'):q[-3:]=[y]
                else:break
            if c=='$':break
            q+=[c]
            b=c!=')'
    return q[0]

我认为这相对容易理解。这是一种相当直接、天真的方法。它不导入任何东西，不使用正则表达式，是完全自包含的（单个函数，没有全局变量，没有副作用），并且应该处理带符号的字面量（正数或负数）。使用更合理的变量名称并遵守推荐的Python格式将字符计数增加到大约850-900，其中很大一部分来自于使用四个空格而不是单个制表符进行缩进。

- fortran · Answer 3

Python 3K

(之所以称为3K，是因为“/”将结果转换为浮点数)

字符数：808

清晰明了（我无法在Python中编写模糊代码XD）：

def parse(line):
  ops = {"+": lambda x,y:x+y,
       "-": lambda x,y:x-y,
       "*": lambda x,y:x*y,
       "/": lambda x,y:x/y}
  def tpp(s, t):
    if len(s) > 0 and s[-1] in ops:
      f = ops[s.pop()]
      t = f(s.pop(), t)
    return t
  line = line + " "
  s = []
  t = 0
  m = None
  for c in line:
    if c in "0123456789":
      if not m:
        m = "i"
      if m == "i":
        t = t*10 + ord(c)-ord("0")
      elif m =="d":
        t = t + e*(ord(c)-ord("0"))
        e*=0.1
    elif c == ".":
      m = "d"
      e = 0.1
    elif m:
      t = tpp(s,t)
      s.append(t)
      m = None
      t = 0

    if c in ops or c == "(":
      s.append(c)
    elif c == ")":
      t = s.pop()
      s.pop()
      s.append(tpp(s,t))
      t = 0
  t = s.pop()
  if int(t) == t:
    t = int(t)
  return t

我没有使用任何正则表达式，甚至数字解析都是手动完成的 ;-)

非常简单，扫描每一行，它可以处于3种不同的模式（m），None表示没有被解析的数字，“i”表示正在解析整数部分，“d”表示正在解析小数部分。

它使用堆栈来存储临时计算结果，当它完成一个数字的解析后，如果堆栈中有运算符，则对其进行求值并推入堆栈。左括号只是被推入堆栈，而右括号会移除相应的左括号，并重新将当前求值结果推入堆栈。

非常简单和直接 :-)

- Mike Tunnicliffe · Answer 4

Ruby

字符数量： 302

半混淆：

def e(l)
  t=0.0;o=nil
  while l!=''
    l.sub!(/^\s+/,'')
    l.sub!(/^(-?\d+|-?\d+\.\d+)/,'')
    t=o ? t.send(o, $1.to_f) : $1.to_f if $~
    l.sub!(/^(\+|-|\*|\/)/,'')
    o=$1 if $~
    l.sub!(/^\(/,'')
    t=o ? t.send(o, e(l)) : e(l) if $~
    l.sub!(/^\)/,'')
    return t if $~
  end
  t
end

销毁原始字符串，同时假定表达式是格式良好的（仅包含有效字符和匹配的括号）。

非混淆：

def evaluate_expression(expression)
  result_so_far = 0.0
  last_operator = nil

  while (expression != '')
    # remove any leading whitespace
    expression.sub!(/^\s+/, '') 

    # extract and remove leading integer or decimal number
    expression.sub!(/^(-?\d+|-?\d+\.\d+)/, '')
    if $~
      # match was successful
      number = $1.to_f
      if last_operator.nil?
        # first number, just store it
        result_so_far = number
      else
        # we have an operator, use it!
        # last_operator is a string matching '+', '-', '*' or '/'
        # just invoke the method of that name on our result_so_far
        # since these operators are just method calls in Ruby
        result_so_far = result_so_far.send(last_operator, number)
       end
    end

    # extract and remove leading operator +-*/
    expression.sub!(/^(\+|-|\*|\/)/, '')
    if $~
      # match was successful
      last_operator = $1
    end

    # extract and remove leading open bracket
    l.sub!(/^\(/, '')
    if $~
      # match successful
      if last_operator.nil?
        # first element in the expression is an open bracket
        # so just evaluate its contents recursively
        result_so_far = evaluate_expression(expression)
      else
        # combine the content of the bracketing with the
        # result so far using the last_operator
        result_so_far.send(last_operator, evaluate_expression(expression))
      end
    end

    # extract and remove leading close bracket
    l.sub!(/^\)/, '')
    if $~
      # match successful
      # this must be the end of a recursive call so
      # return the result so far without consuming the rest
      # of the expression
      return result_so_far
    end
  end
  t
end

递归调用受表达式字符串修改的控制，这有点棘手，但看起来似乎可以工作。

- J D · Answer 5

OCaml 直接使用Camlp4：

open Camlp4.PreCast

let expr = Gram.Entry.mk "expr"

EXTEND Gram
  expr:
  [   [ e1 = expr; "+"; e2 = expr -> e1 + e2
      | e1 = expr; "-"; e2 = expr -> e1 - e2 ]
  |   [ e1 = expr; "*"; e2 = expr -> e1 * e2
      | e1 = expr; "/"; e2 = expr -> e1 / e2 ]
  |   [ n = INT -> int_of_string n
      | "("; e = expr; ")" -> e ]   ];
END

let () = Gram.parse expr Loc.ghost (Stream.of_string "1-2+3*4")

OCaml 使用Camlp4流解析器扩展：

open Genlex

let lex = make_lexer ["+"; "-"; "*"; "/"; "("; ")"]

let rec parse_atom = parser
  | [< 'Int n >] -> n
  | [< 'Kwd "("; e=parse_expr; 'Kwd ")" >] -> e
and parse_factor = parser
  | [< e1=parse_atom; stream >] ->
      (parser
         | [< 'Kwd "*"; e2=parse_factor >] -> e1 * e2
         | [< 'Kwd "/"; e2=parse_factor >] -> e1 / e2
         | [< >] -> e1) stream
and parse_expr = parser
  | [< e1=parse_factor; stream >] ->
      (parser
         | [< 'Kwd "+"; e2=parse_expr >] -> e1 + e2
         | [< 'Kwd "-"; e2=parse_expr >] -> e1 - e2
         | [< >] -> e1) stream

let () =
  Printf.printf "%d\n" (parse_expr(lex(Stream.of_string "1 + 2 * (3 + 4)")));;

- Noldorin · Answer 6

F#

字符数：461

这里是Marc Gravell的解决方案（本质上）从C#转换为F＃。字符计数几乎没有变好，但我还是想出于兴趣发布它。

混淆代码：

let e x=
 let rec f(s:string)=
  let i=s.IndexOf(')')
  if i>0 then
   let j=s.LastIndexOf('(',i)
   f(s.Substring(0,j)+f(s.Substring(j+1,i-j-1))+s.Substring(i+1))
  else
   let o=[|'+';'-';'*';'/'|]
   let i=s.LastIndexOfAny(o)
   let j=s.IndexOfAny(o,max(i-2)0,2)
   let k=if j<0 then i else j
   if k<0 then s else
    let o=s.[k]
    string((if o='+'then(+)else if o='-'then(-)else if o='*'then(*)else(/))(float(f(s.Substring(0,k))))(float(s.Substring(k+1))))
 float(f x)

- Zarkonnen · Answer 7

Java

字符数：376

更新版本，现在使用更多的？操作符滥用！

完全混淆的解决方案：

static double e(String t){t="("+t+")";for(String s:new String[]{"+","-","*","/","(",")"})t=t.replace(s," "+s+" ");return f(new Scanner(t));}static double f(Scanner s){s.next();double a,v=s.hasNextDouble()?s.nextDouble():f(s);while(s.hasNext("[^)]")){char o=s.next().charAt(0);a=s.hasNextDouble()?s.nextDouble():f(s);v=o=='+'?v+a:o=='-'?v-a:o=='*'?v*a:v/a;}s.next();return v;}

清晰/半混淆函数：

static double evaluate(String text) {
    text = "(" + text + ")";
    for (String s : new String[] {"+", "-", "*", "/", "(", ")" }) {
        text = text.replace(s, " " + s + " ");
    }
    return innerEval(new Scanner(text));
}

static double innerEval(Scanner s) {
    s.next();
    double arg, val = s.hasNextDouble() ? s.nextDouble() : innerEval(s);
    while (s.hasNext("[^)]")) {
        char op = s.next().charAt(0);
        arg = s.hasNextDouble() ? s.nextDouble() : innerEval(s);
        val =
            op == '+' ? val + arg :
            op == '-' ? val - arg :
            op == '*' ? val * arg :
            val / arg;
    }
    s.next();
    return val;
}

- Mike Dunlavey · Answer 8

C++

字符数：1670

 // not trying to be terse here
#define DIGIT(c)((c)>='0' && (c) <= '9')
#define WHITE(pc) while(*pc == ' ') pc++
#define LP '('
#define RP ')'

bool SeeNum(const char* &pc, float& fNum){
    WHITE(pc);
    if (!(DIGIT(*pc) || (*pc=='.'&& DIGIT(pc[1])))) return false;
    const char* pc0 = pc;
    while(DIGIT(*pc)) pc++;
    if (*pc == '.'){
        pc++;
        while(DIGIT(*pc)) pc++;
    }
    char buf[200];
    int len = pc - pc0;
    strncpy(buf, pc0, len); buf[len] = 0;
    fNum = atof(buf);
    return true;
}

bool SeeChar(const char* &pc, char c){
    WHITE(pc);
    if (*pc != c) return false;
    pc++;
    return true;
}

void ParsExpr(const char* &pc, float &fNum);

void ParsPrim(const char* &pc, float &fNum){
    if (SeeNum(pc, fNum));
    else if (SeeChar(pc, LP)){
        ParsExpr(pc, fNum);
        if (!SeeChar(pc, RP)) exit(0);
    }
    else exit(0); // you can abort better than this
}

void ParsUnary(const char* &pc, float &fNum){
    if (SeeChar(pc, '-')){
        pc+;
        ParsUnary(pc, fNum);
        fNum = -fNum;
    }
    else {
        ParsPrim(pc, fNum);
    }
}

void ParsExpr(const char* &pc, float &fNum){
    ParsUnary(pc, fNum);
    float f1 = 0;
    while(true){
        if (SeeChar(pc, '+')){
            ParsUnary(pc, f1);
            fNum += f1;
        }
        else if (SeeChar(pc, '-')){
            ParsUnary(pc, f1);
            fNum -= f1;
        }
        else if (SeeChar(pc, '*')){
            ParsUnary(pc, f1);
            fNum *= f1;
        }
        else if (SeeChar(pc, '/')){
            ParsUnary(pc, f1);
            fNum /= f1;
        }
        else break;
    }
}

这只是LL1（递归下降）。

我喜欢用这种方式（尽管我使用双精度），因为它非常快，并且很容易插入处理优先级的例程。

- bud meyer · Answer 9

PowerBASIC

字符数：约400个

有点丑，但它能用。 :) 我相信正则表达式会使它更小。

DEFDBL E,f,i,z,q,a,v,o  
DEFSTR s,c,k,p

FUNCTION E(s)  

    i=LEN(s)  
    DO  
        IF MID$(s,i,1)="("THEN  
            q=INSTR(i,s,")")  
            s=LEFT$(s,i-1)+STR$(E(MID$(s,i+1,q-i-1)))+MID$(s,q+1)  
        END IF  
        i-=1  
    LOOP UNTIL i=0  

    k="+-*/"  
    DIM p(PARSECOUNT(s,ANY k))  
    PARSE s,p(),ANY k  

    a=VAL(p(0))

    FOR i=1TO LEN(s)
        c=MID$(s,i,1)
        q=INSTR(k,c)
        IF q THEN
            z+=1
            IF o=0 THEN o=q ELSE p(z)=c+p(z)
            IF TRIM$(p(z))<>"" THEN
                v=VAL(p(z))
                a=CHOOSE(o,a+v,a-v,a*v,a/v)
                o=0
            END IF
        END IF
    NEXT

    E=a  
END FUNCTION

- Jimmy · Answer 10

C#, 264个字符

策略：首先通过归纳消除括号的前两行。然后我通过\-?[\d.]+进行分割以获取数字和运算符，然后使用聚合将字符串数组减少为双精度值。

变量解释

m是没有嵌套括号的括号表达式。
d是那个尴尬的TryParse语法的占位符。
v是最终值的累加器
t是当前标记。

float E(string s){var d=999f;while(d-->1)s=Regex.Replace(s,@"(([^(]?))",m=>E(m.Groups[1].Value)+"");return Regex.Split(s,@"(-?[\d.]+)").Aggregate(d,(v,t)=>(t=t.Trim()).Length==0?v:!float.TryParse(t,out d)?(s=t)==""?0:v:s=="/"?v/d:s=="-"?v-d:s==""?v*d:v+d);}

    float F(string s) {
        var d=999f;
        while(d-->1)
            s=Regex.Replace(s,@"\(([^\(]*?)\)",m=>F(m.Groups[1].Value)+"");
        return Regex.Split(s, @"(\-?[\d\.]+)")
            .Aggregate(d, (v, t) => 
                (t=t.Trim()).Length == 0 ? v :
                !float.TryParse(t, out d) ? (s=t) == "" ? 0 : v :
                s == "/" ? v / d :
                s == "-" ? v - d :
                s == "*" ? v * d :
                           v + d);
    }

编辑：无耻地从noldorin的答案中窃取了部分内容，重用s作为操作变量。

编辑：999个嵌套括号对于任何人来说应该足够了。