代码高尔夫：数学表达式求值器（遵循PEMDAS规则）

Question

代码高尔夫：数学表达式求值器（遵循PEMDAS规则）

26

我向你发起挑战，要求你编写一个遵守PEMDAS运算规则（先计算括号内部分，指数，乘法，除法，加法和减法）的数学表达式计算器，但是不能使用正则表达式、预定义的“Eval()”函数、解析库等。

我在SO上看到过一个类似的挑战（这里），但是那个挑战特别要求按从左到右的顺序进行计算。

样例输入和输出：

"-1^(-3*4/-6)" -> "1"

"-2^(2^(4-1))" -> "256"

"2*6/4^2*4/3" -> "1"

我用C#编写了一个求值器，但想看看它与那些用他们选择的语言编写的更聪明的程序员相比有多糟糕。

J

:[[/%^(:[[+-/^,&i|:[$[' ']^j+0__:k<3:]]

- Alex

5

今天这已经是我做的第三次格式化编辑了。更重要的是，有人真的会在除了代码高尔夫之外的其他方面使用J吗？如果是这样，你是个受虐狂吗？ - Chris Lutz

2

该死，J！ - P Daddy

5

它实际上会做些什么，而不仅仅是冲你吐舌头？ - P Daddy

3

哦，等等。我刚才才明白这个笑话。Alex说：“让我试试J：：（：[ [：（：o：pO_O&i-:）$$。我写出了一个程序吗？”（来源：https://dev59.com/nnM_5IYBdhLWcg3wcSt_#1376201） - P Daddy

2

大家好：这个答案是一个玩笑，(: 不是一个合法的单词。 - Jader Dias

显示剩余2条评论

9

F#，70行代码

好的，我实现了一个单子解析器组合库，然后使用该库来解决这个问题。总共只有70行易读代码。

我假设指数运算从右到左结合，其他运算从左到右结合。所有的计算都基于浮点数（System.Doubles）。我没有处理错误输入或除以零的情况。

// Core Parser Library
open System
let Fail() = fun i -> None
type ParseMonad() =
    member p.Return x = fun i -> Some(x,i)
    member p.Bind(m,f) = fun i -> 
        match m i with
        | Some(x,i2) -> f x i2
        | None -> None
let parse = ParseMonad()
let (<|>) p1 p2 = fun i -> 
    match p1 i with
    | Some r -> Some(r)
    | None -> p2 i
let Sat pred = fun i -> 
    match i with
    | [] -> None
    | c::cs -> if pred c then Some(c, cs) else None
// Auxiliary Parser Library
let Digit = Sat Char.IsDigit
let Lit (c : char) r = 
    parse { let! _ = Sat ((=) c)
            return r }
let Opt p = p <|> parse { return [] }
let rec Many p = Opt (Many1 p)
and Many1 p = parse { let! x = p
                      let! xs = Many p
                      return x :: xs }
let Num = parse {
    let! sign = Opt(Lit '-' ['-'])
    let! beforeDec = Many Digit
    let! rest = parse { let! dec = Lit '.' '.'
                        let! afterDec = Many Digit
                        return dec :: afterDec } |> Opt
    let s = new string(List.concat([sign;beforeDec;rest])
                       |> List.to_array) 
    match(try Some(float s) with e -> None)with
    | Some(r) -> return r
    | None -> return! Fail() }
let Chainl1 p op = 
    let rec Help x = parse { let! f = op
                             let! y = p
                             return! Help (f x y) } 
                     <|> parse { return x }
    parse { let! x = p
            return! Help x }
let rec Chainr1 p op =
    parse { let! x = p
            return! parse { let! f = op
                            let! y = Chainr1 p op
                            return f x y }
                    <|> parse { return x } }
// Expression grammar of this code-golf question
let AddOp = Lit '+' (fun x y -> 0. + x + y) 
        <|> Lit '-' (fun x y -> 0. + x - y)
let MulOp = Lit '*' (fun x y -> 0. + x * y) 
        <|> Lit '/' (fun x y -> 0. + x / y)
let ExpOp = Lit '^' (fun x y -> Math.Pow(x,y))
let rec Expr = Chainl1 Term AddOp
and Term = Chainl1 Factor MulOp
and Factor = Chainr1 Part ExpOp
and Part = Num <|> Paren
and Paren = parse { do! Lit '(' ()
                    let! e = Expr
                    do! Lit ')' ()
                    return e }
let CodeGolf (s:string) =
    match Expr(Seq.to_list(s.ToCharArray())) with
    | None -> "bad input"
    | Some(r,_) -> r.ToString()
// Examples
printfn "%s" (CodeGolf "1.1+2.2+10^2^3") // 100000003.3
printfn "%s" (CodeGolf "10+3.14/2")      // 11.57
printfn "%s" (CodeGolf "(10+3.14)/2")    // 6.57
printfn "%s" (CodeGolf "-1^(-3*4/-6)")   // 1
printfn "%s" (CodeGolf "-2^(2^(4-1))")   // 256 
printfn "%s" (CodeGolf "2*6/4^2*4/3")    // 1

解析器表示类型是：

type P<'a> = char list -> option<'a * char list>

顺便说一下，这是非错误处理解析器中常见的一种情况。

- Brian

1

+1，我只是想说这激励我再次关注F#。 - Andrew Walker

处理程序 -(2+3)? 处理程序 1E7? - Ira Baxter

它不处理这些内容。在表达式之前使用一元减号似乎不是规范的一部分。'1e7' 的东西是可选的，而我选择不使用它。 - Brian

8

PARLANSE中的递归下降解析器是一种类似于C的语言，具有LISP语法。代码共70行，不包括SO所需的缩进4个字符在内，共1376个字符。规则已更改，现在支持浮点数，但除了浮点转换、输入和输出之外，不允许使用任何库函数。代码现在共94行，1825个字符。

(define main (procedure void)
   (local
      (;; (define f (function float void))
          (= [s string] (append (input) "$"))
          (= [i natural] 1)

         (define S (lambda f
            (let (= v (P))
               (value (loop
                          (case s:i)
                            "+" (;; (+= i) (+= v (P) );;
                            "-" (;; (+= i) (-= v (P) );;
                            else (return v)
                          )case
                       )loop
                  v
              )value
         )define

         (define P (lambda f
            (let (= v (T))
               (value (loop
                          (case s:i)
                            "*" (;; (+= i) (= v (* v (T)) );;
                            "/" (;; (+= i) (= v (/ v (T)) );;
                            else (return v)
                          )case
                       )loop
                  v
              )value
         )define

         (define T (lambda f
            (let (= v (O))
               (value (loop
                          (case s:i)
                            "^" (;; (+= i) (= v (** v (T)) );;
                            else (return v)
                          )case
                       )loop
                  v
              )value
         )define

         (define O (lambda f
           (let (= v +0)
            (value 
               (case s:i)
                  "(" (;; (+= i) (= v (E)) (+= i) );;
                  "-" (;; (+= i) (= v (- 0.0 (O))) );;
               else (= v (StringToFloat (F))
          )value
          v
        )let
     )define

     (define F (lambda f)
        (let (= n (N))
             (value
              (;; (ifthen (== s:i ".")
                     (;; (+= i)
                         (= n (append n "."))
                         (= n (concatenate n (N)))
                     );;
                  )ifthen
                  (ifthen (== s:i "E")
                     (;; (+= i)
                         (= n (append n "E"))
                         (ifthen (== s:i "-")
                         (;; (+= i)
                             (= n (append n "-"))
                             (= n (concatenate n (N)))
                         );;
                     );;
                  )ifthen
              );;
              n
         )let
     )define               

     (define N (lambda (function string string)
        (case s:i
            (any "0" "1" "2" "3" "4" "5" "6" "7" "8" "9")
               (value (+= i)
                      (append ? s:(-- i))
               )value
            else ?
        )case
     )define

      );;
      (print (S))
   )local
)define

假设表达式格式正确，浮点数至少有一个前导数字，指数可选为Enn或E-nnn。未编译和运行。

特别说明：定义f实际上是签名typedef。lambda是解析函数，每个语法规则一个。通过写(F args)调用函数F。 PARLANSE函数具有词法作用域，因此每个函数都可以隐式访问要评估的表达式s和字符串扫描索引i。

所实现的语法如下:

E = S $ ;
S = P ;
S = S + P ;
P = T ;
P = P * T ;  
T = O ;
T = O ^ T ;
O = ( S ) ;
O = - O ;
O = F ;
F = digits {. digits} { E {-} digits} ;

- Ira Baxter

5

F#，589个字符

我把之前的解决方案压缩成了这个宝石：

let rec D a=function|c::s when System.Char.IsDigit c->D(c::a)s|s->a,s
and L p o s=
 let rec K(a,s)=match o s with|None->a,s|Some(o,t)->let q,t=p t in K(o a q,t)
 K(p s)
and E=L(L F (function|'*'::s->Some((*),s)|'/'::s->Some((/),s)|_->None))(
function|'+'::s->Some((+),s)|'-'::s->Some((-),s)|_->None)
and F s=match P s with|x,'^'::s->let y,s=F s in x**y,s|r->r
and P=function|'('::s->let r,_::s=E s in r,s|s->(
let a,s=match(match s with|'-'::t->D['-']t|_->D[]s)with|a,'.'::t->D('.'::a)t|r->r
float(new string(Seq.to_array(List.rev a))),s)
and G s=string(fst(E(Seq.to_list s)))

测试：

printfn "%s" (G "1.1+2.2+10^2^3") // 100000003.3
printfn "%s" (G "10+3.14/2")      // 11.57
printfn "%s" (G "(10+3.14)/2")    // 6.57
printfn "%s" (G "-1^(-3*4/-6)")   // 1
printfn "%s" (G "-2^(2^(4-1))")   // 256 
printfn "%s" (G "2*6/4^2*4/3")    // 1
printfn "%s" (G "3-2-1")          // 0

- Brian

4

C#（使用大量LINQ），150行

好的，我实现了一个单子解析器组合库，并使用该库来解决此问题。总共大约有150行代码。（这基本上是我的F#解决方案的直接转写。）

我假设指数运算符从右往左结合，其他运算符从左往右结合。所有操作都基于System.Doubles进行。我没有为错误输入或除以零进行任何错误处理。

using System;
using System.Collections.Generic;
using System.Linq;
class Option<T>
{
    public T Value { get; set;  }
    public Option(T x) { Value = x; }
}
delegate Option<KeyValuePair<T,List<char>>> P<T>(List<char> input);
static class Program
{
    static List<T> Cons<T>(T x, List<T> xs)
    {
        var r = new List<T>(xs);
        r.Insert(0, x);
        return r;
    }
    static Option<T> Some<T>(T x) { return new Option<T>(x); }
    static KeyValuePair<T,List<char>> KVP<T>(T x, List<char> y) 
    { return new KeyValuePair<T,List<char>>(x,y); }
    // Core Parser Library
    static P<T> Fail<T>() { return i => null; }
    static P<U> Select<T, U>(this P<T> p, Func<T, U> f)
    {
        return i =>
        {
            var r = p(i);
            if (r == null) return null;
            return Some(KVP(f(r.Value.Key),(r.Value.Value)));
        };
    }
    public static P<V> SelectMany<T, U, V>(this P<T> p, Func<T, P<U>> sel, Func<T, U, V> prj)
    {
        return i =>
        {
            var r = p(i);
            if (r == null) return null;
            var p2 = sel(r.Value.Key);
            var r2 = p2(r.Value.Value);
            if (r2 == null) return null;
            return Some(KVP(prj(r.Value.Key, r2.Value.Key),(r2.Value.Value)));
        };
    }
    static P<T> Or<T>(this P<T> p1, P<T> p2)
    {
        return i =>
        {
            var r = p1(i);
            if (r == null) return p2(i);
            return r;
        };
    }
    static P<char> Sat(Func<char,bool> pred)
    {
        return i =>
        {
            if (i.Count == 0 || !pred(i[0])) return null;
            var rest = new List<char>(i);
            rest.RemoveAt(0);
            return Some(KVP(i[0], rest));
        };
    }
    static P<T> Return<T>(T x) 
    {
        return i => Some(KVP(x,i));
    }
    // Auxiliary Parser Library
    static P<char> Digit = Sat(Char.IsDigit);
    static P<T> Lit<T>(char c, T r)
    {
        return from dummy in Sat(x => x == c)
               select r;
    }
    static P<List<T>> Opt<T>(P<List<T>> p)
    {
        return p.Or(Return(new List<T>()));
    }
    static P<List<T>> Many<T>(P<T> p)
    {
        return Many1<T>(p).Or(Return(new List<T>()));
    }
    static P<List<T>> Many1<T>(P<T> p)
    {
        return from x in p
               from xs in Many(p)
               select Cons(x, xs);
    }
    static P<T> Chainl1<T>(this P<T> p, P<Func<T, T, T>> op)
    {
        return from x in p
               from r in Chainl1Helper(x, p, op)
               select r;
    }
    static P<T> Chainl1Helper<T>(T x, P<T> p, P<Func<T, T, T>> op)
    {
        return (from f in op
                from y in p
                from r in Chainl1Helper(f(x, y), p, op)
                select r)
        .Or(Return(x));
    }
    static P<T> Chainr1<T>(this P<T> p, P<Func<T, T, T>> op)
    {
        return (from x in p
                from r in (from f in op
                           from y in Chainr1(p, op)
                           select f(x, y))
                           .Or(Return(x))
                select r);
    }
    static P<double> TryParse(string s)
    {
        double d;
        if (Double.TryParse(s, out d)) return Return(d);
        return Fail<double>();
    }
    static void Main(string[] args)
    {
        var Num = from sign in Opt(Lit('-', new List<char>(new []{'-'})))
                  from beforeDec in Many(Digit)
                  from rest in Opt(from dec in Lit('.','.')
                                   from afterDec in Many(Digit)
                                   select Cons(dec, afterDec))
                  let s = new string(Enumerable.Concat(sign,
                                     Enumerable.Concat(beforeDec, rest))
                                     .ToArray())
                  from r in TryParse(s)
                  select r;
        // Expression grammar of this code-golf question
        var AddOp = Lit('+', new Func<double,double,double>((x,y) => x + y))
                .Or(Lit('-', new Func<double, double, double>((x, y) => x - y)));
        var MulOp = Lit('*', new Func<double, double, double>((x, y) => x * y))
                .Or(Lit('/', new Func<double, double, double>((x, y) => x / y)));
        var ExpOp = Lit('^', new Func<double, double, double>((x, y) => Math.Pow(x, y)));
        P<double> Expr = null;
        P<double> Term = null;
        P<double> Factor = null;
        P<double> Part = null;
        P<double> Paren = from _1 in Lit('(', 0)
                          from e in Expr
                          from _2 in Lit(')', 0)
                          select e;
        Part = Num.Or(Paren);
        Factor = Chainr1(Part, ExpOp);
        Term = Chainl1(Factor, MulOp);
        Expr = Chainl1(Term, AddOp);
        Func<string,string> CodeGolf = s => 
            Expr(new List<char>(s)).Value.Key.ToString();
        // Examples
        Console.WriteLine(CodeGolf("1.1+2.2+10^2^3")); // 100000003.3
        Console.WriteLine(CodeGolf("10+3.14/2"));      // 11.57
        Console.WriteLine(CodeGolf("(10+3.14)/2"));    // 6.57
        Console.WriteLine(CodeGolf("-1^(-3*4/-6)"));   // 1
        Console.WriteLine(CodeGolf("-2^(2^(4-1))"));   // 256 
        Console.WriteLine(CodeGolf("2*6/4^2*4/3"));    // 1
    }
}

- Brian

2

C99 (565 characters)

Minified

#include<stdio.h>
#include<string.h>
#include<math.h>
float X(char*c){struct{float f;int d,c;}N[99],*C,*E,*P;char*o="+-*/^()",*q,d=1,x
=0;for(C=N;*c;){C->f=C->c=0;if(q=strchr(o,*c)){if(*c<42)d+=*c-41?8:-8;else{if(C
==N|C[-1].c)goto F;C->d=d+(q-o)/2*2;C->c=q-o+1;++C;}++c;}else{int n=0;F:sscanf(c
,"%f%n",&C->f,&n);c+=n;C->d=d;++C;}}for(E=N;E-C;++E)x=E->d>x?E->d:x;for(;x>0;--x
)for(E=P=N;E-C;E->d&&!E->c?P=E:0,++E)if(E->d==x&&E->c){switch((E++)->c){
#define Z(x,n)case n:P->f=P->f x E->f;break;
Z(+,1)Z(-,2)Z(*,3)Z(/,4)case 5:P->f=powf(P->f,E->f);}E->d=0;}return N->f;}

扩展

#include<stdio.h>
#include<string.h>
#include<math.h>
float X(char*c){
    struct{
        float f;
        int d,c;
    }N[99],*C,*E,*P;
    char*o="+-*/^()",*q,d=1,x=0;

    for(C=N;*c;){
        C->f=C->c=0;
        if(q=strchr(o,*c)){
            if(*c<42)   // Parentheses.
                d+=*c-41?8:-8;
            else{       // +-*/^.
                if(C==N|C[-1].c)
                    goto F;
                C->d=d+(q-o)/2*2;
                C->c=q-o+1;
                ++C;
            }
            ++c;
        }else{
            int n=0;
            F:
            sscanf(c,"%f%n",&C->f,&n);
            c+=n;
            C->d=d;
            ++C;
        }
    }

    for(E=N;E-C;++E)
        x=E->d>x?E->d:x;

    for(;x>0;--x)
        for(E=P=N;E-C;E->d&&!E->c?P=E:0,++E)
            if(E->d==x&&E->c){
                switch((E++)->c){
#define Z(x,n)case n:P->f=P->f x E->f;break;
                    Z(+,1)
                    Z(-,2)
                    Z(*,3)
                    Z(/,4)
                    case 5:
                        P->f=powf(P->f,E->f);
                }
                E->d=0;
            }

    return N->f;
}

int main(){
    assert(X("2+2")==4);
    assert(X("-1^(-3*4/-6)")==1);
    assert(X("-2^(2^(4-1))")==256);
    assert(X("2*6/4^2*4/3")==1);
    puts("success");
}

解释

我开发了自己的技术。你需要自己琢磨。=]

- strager

我认为 #includes 不是必需的，因为只调用了一个函数。而且即使没有它们，它也应该能够编译和运行。 - P Daddy

2

@P Daddy，不是这样的。没有它们，函数签名就不存在了。这意味着powf将接收一个double，在期望char *的地方传递一个int，等等。不能假设指针适合于int，例如。 - strager

2

C (277 characters)

#define V(c)D o;for(**s-40?*r=strtod(*s,s):(++*s,M(s,r)),o=**s?strchr(t,*(*s)++)-t:0;c;)L(r,&o,s);
typedef char*S;typedef double D;D strtod(),pow();S*t=")+-*/^",strchr();
L(D*v,D*p,S*s){D u,*r=&u;V(*p<o)*v=*p-1?*p-2?*p-3?*p-4?pow(*v,u):*v/u:
*v*u:*v-u:*v+u;*p=o;}M(S*s,D*r){V(o)}

第一个换行符是必需的，我已将其计为一个字符。

这是与我其他答案完全不同的方法。它更像是一种功能性的方法。它不是通过标记化和多次循环来评估表达式，而是在一次遍历中评估表达式，对于高优先级运算符使用递归调用，在效果上使用调用堆栈来存储状态。

为了满足 strager ^;)，这次我包括了 strtod()、pow() 和 strchr() 的前向声明。去掉它们可以节省 26 个字符。

入口点是M()。输入字符串是第一个参数，输出双精度浮点数是第二个参数。入口点曾经是E()，它返回一个字符串，因为OP要求如此。但由于我的C实现是唯一一个这样做的，我决定将其删除（群众的眼睛是雪亮的）。如果加回去，会增加43个字符：

E(S s,S r){D v;M(&s,&v);sprintf(r,"%g",v);}

以下是我压缩之前的代码：

double strtod(),pow(),Solve();

int OpOrder(char op){
    int i=-1;
    while("\0)+-*/^"[++i] != op);
    return i/2;
}
double GetValue(char **s){
    if(**s == '('){
        ++*s;
        return Solve(s);
    }
    return strtod(*s, s);
}
double Calculate(double left, char *op, char **s){
    double right;
    char rightOp;
    if(*op == 0 || *op == ')')
        return left;

    right = GetValue(s);
    rightOp = *(*s)++;

    while(OpOrder(*op) < OpOrder(rightOp))
        right = Calculate(right, &rightOp, s);

    switch(*op){
        case '+': left += right; break;
        case '-': left -= right; break;
        case '*': left *= right; break;
        case '/': left /= right; break;
        case '^': left = pow(left, right); break;
    }
    *op = rightOp;
    return left;
}
double Solve(char **s){
    double value = GetValue(s);
    char op = *(*s)++;
    while(op != 0 && op != ')')
        value = Calculate(value, &op, s);
    return value;
}
void Evaluate(char *expression, char *result){
    sprintf(result, "%g", Solve(&expression));
}

由于楼主的“参考实现”是用C#编写的，因此我也编写了一个半压缩的C#版本：

D P(D o){
    return o!=6?o!=7&&o!=2?o<2?0:1:2:3;
}
D T(ref S s){
    int i;
    if(s[i=0]<48)
        i++;
    while(i<s.Length&&s[i]>47&s[i]<58|s[i]==46)
        i++;
    S t=s;
    s=s.Substring(i);
    return D.Parse(t.Substring(0,i));
}
D V(ref S s,out D o){
    D r;
    if(s[0]!=40)
        r=T(ref s);
    else{s=s.Substring(1);r=M(ref s);}
    if(s=="")
        o=0;
    else{o=s[0]&7;s=s.Substring(1);}
    return r;
}
void L(ref D v,ref D o,ref S s){
    D p,r=V(ref s,out p),u=v;
    for(;P(o)<P(p);)
        L(ref r,ref p,ref s);

    v = new Func<D>[]{()=>u*r,()=>u+r,()=>0,()=>u-r,()=>Math.Pow(u,r),()=>u/r}[(int)o-2]();
    o=p;
}
D M(ref S s){
    for(D o,r=V(ref s,out o);o>1)
        L(ref r,ref o,ref s);
    return r;
}

- P Daddy

1

F#，52行

这个程序主要避免了通用性，只专注于编写递归下降解析器来解决这个确切的问题。

open System
let rec Digits acc = function
    | c::cs when Char.IsDigit(c) -> Digits (c::acc) cs
    | rest -> acc,rest
let Num = function
    | cs ->
        let acc,cs = match cs with|'-'::t->['-'],t |_->[],cs
        let acc,cs = Digits acc cs
        let acc,cs = match cs with
                     | '.'::t -> Digits ('.'::acc) t
                     | _ -> acc, cs
        let s = new string(List.rev acc |> List.to_array) 
        float s, cs
let Chainl p op cs =
    let mutable r, cs = p cs
    let mutable finished = false
    while not finished do
        match op cs with
        | None -> finished <- true
        | Some(op, cs2) ->
            let r2, cs2 = p cs2
            r <- op r r2
            cs <- cs2
    r, cs
let rec Chainr p op cs =
    let x, cs = p cs
    match op cs with
    | None -> x, cs
    | Some(f, cs) ->  // TODO not tail-recursive
        let y, cs = Chainr p op cs
        f x y, cs
let AddOp = function
    | '+'::cs -> Some((fun x y -> 0. + x + y), cs)    
    | '-'::cs -> Some((fun x y -> 0. + x - y), cs)    
    | _ -> None
let MulOp = function
    | '*'::cs -> Some((fun x y -> 0. + x * y), cs)    
    | '/'::cs -> Some((fun x y -> 0. + x / y), cs)    
    | _ -> None
let ExpOp = function
    | '^'::cs -> Some((fun x y -> Math.Pow(x,y)), cs)    
    | _ -> None
let rec Expr = Chainl Term AddOp
and Term = Chainl Factor MulOp
and Factor = Chainr Part ExpOp
and Part = function
    | '('::cs -> let r, cs = Expr cs
                 if List.hd cs <> ')' then failwith "boom"
                 r, List.tl cs
    | cs -> Num cs
let CodeGolf (s:string) =
    Seq.to_list s |> Expr |> fst |> string
// Examples
printfn "%s" (CodeGolf "1.1+2.2+10^2^3") // 100000003.3
printfn "%s" (CodeGolf "10+3.14/2")      // 11.57
printfn "%s" (CodeGolf "(10+3.14)/2")    // 6.57
printfn "%s" (CodeGolf "-1^(-3*4/-6)")   // 1
printfn "%s" (CodeGolf "-2^(2^(4-1))")   // 256 
printfn "%s" (CodeGolf "2*6/4^2*4/3")    // 1
printfn "%s" (CodeGolf "3-2-1")          // 0

- Brian

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

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

- P Daddy · Accepted Answer

C (465 characters)

#define F for(i=0;P-8;i+=2)
#define V t[i
#define P V+1]
#define S V+2]),K(&L,4),i-=2)
#define L V-2]
K(double*t,int i){for(*++t=4;*t-8;*++t=V])*++t=V];}M(double*t){int i,p,b;
F if(!P)for(p=1,b=i;i+=2,p;)P?P-1||--p||(P=8,M(t+b+2),K(t+b,i-b),i=b):++p;
F P-6||(L=pow(L,S;F P-2&&P-7||(L*=(P-7?V+2]:1/S;F P-4&&(L+=(P-5?V+2]:-S;
F L=V];}E(char*s,char*r){double t[99];char*e,i=2,z=0;for(;*s;i+=2)V]=
strtod(s,&e),P=z=e-s&&z-4&&z-1?s=e,4:*s++&7;P=8;M(t+2);sprintf(r,"%g",*t);}

前五个换行符是必须的，其余的只是为了可读性。我将前五个换行符计算为一个字符。如果你想按行计算，那么在我删除所有空白字符之前，它有28行，但这是一个毫无意义的数字。它可能是从6行到一百万行，取决于我如何格式化它。

入口点是E()（表示“评估”）。第一个参数是输入字符串，第二个参数指向输出字符串，并且必须由调用者分配（根据通常的C标准）。它最多可以处理47个标记，其中标记是运算符之一（"+-*/^()"）或浮点数。一元符号运算符不算作单独的标记。

这段代码基于我多年前做的一个练习项目。我删除了所有的错误处理和跳过空格，并使用高尔夫技巧重新装备了它。下面是28行代码，有足够的格式化，我能够写出来，但可能不足以阅读。你需要#include <stdlib.h>、<stdio.h>和<math.h>（或参见底部的说明）。

请看代码后面的解释。

#define F for(i=0;P-8;i+=2)
#define V t[i
#define P V+1]
#define S V+2]),K(&L,4),i-=2)
#define L V-2]
K(double*t,int i){
    for(*++t=4;*t-8;*++t=V])
        *++t=V];
}
M(double*t){
    int i,p,b;
    F if(!P)
        for(p=1,b=i;i+=2,p;)
            P?P-1||--p||(P=8,M(t+b+2),K(t+b,i-b),i=b):++p;
    F P-6||(L=pow(L,S;
    F P-2&&P-7||(L*=(P-7?V+2]:1/S;
    F P-4&&(L+=(P-5?V+2]:-S;
    F L=V];
}
E(char*s,char*r){
    double t[99];
    char*e,i=2,z=0;
    for(;*s;i+=2)
        V]=strtod(s,&e),P=z=e-s&&z-4&&z-1?s=e,4:*s++&7;
    P=8;
    M(t+2);
    sprintf(r,"%g",*t);
}

第一步是进行标记化。每个标记的双倍数组都包含两个值，一个操作符（P，因为O看起来太像零）和一个值（V）。这种标记化是在E()中的for循环中完成的。它还处理任何一元的+和-运算符，并将它们合并到常量中。

标记数组的“操作符”字段可以具有以下值之一：

0：（
1：）
2：*
3：+
4：浮点常量值
5：-
6：^
7：/
8：标记字符串结束

这个方案在很大程度上是由Daniel Martin提出的，他注意到这个挑战中每个操作符的ASCII表示中的最后3位是唯一的。 E()的未压缩版本看起来像这样：

void Evaluate(char *expression, char *result){
    double tokenList[99];
    char *parseEnd;
    int i = 2, prevOperator = 0;
    /* i must start at 2, because the EvalTokens will write before the
     * beginning of the array.  This is to allow overwriting an opening
     * parenthesis with the value of the subexpression. */
    for(; *expression != 0; i += 2){
        /* try to parse a constant floating-point value */
        tokenList[i] = strtod(expression, &parseEnd);

        /* explanation below code */
        if(parseEnd != expression && prevOperator != 4/*constant*/ &&
           prevOperator != 1/*close paren*/){
            expression = parseEnd;
            prevOperator = tokenList[i + 1] = 4/*constant*/;
        }else{
            /* it's an operator */
            prevOperator = tokenList[i + 1] = *expression & 7;
            expression++;
        }
    }

    /* done parsing, add end-of-token-string operator */
    tokenList[i + 1] = 8/*end*/

    /* Evaluate the expression in the token list */
    EvalTokens(tokenList + 2); /* remember the offset by 2 above? */

    sprintf(result, "%g", tokenList[0]/* result ends up in first value */);
}

由于我们保证了输入的有效性，如果解析失败的原因只可能是下一个标记是运算符。如果这种情况发生，则parseEnd指针将与tokenStart相同。我们还必须处理解析成功的情况，但我们真正想要的是运算符。这将发生在加法和减法运算符中，除非直接跟随符号运算符。换句话说，给定表达式“4-6”，我们希望将其解析为{4, -, 6}，而不是{4, -6}。另一方面，给定“4+-6”，我们应该将其解析为{4, +, -6}。解决方案非常简单。如果解析失败或前面的标记是常量或关闭括号（实际上是将求值为常量的子表达式），则当前标记是运算符，否则则是常量。

完成标记化后，通过调用M()来完成计算和折叠，它首先寻找任何匹配的括号对，并处理其中包含的子表达式，方法是递归调用它本身。然后处理运算符，首先是幂运算，然后是乘法和除法一起，最后是加法和减法一起。由于期望输入格式正确（按照要求规定），因此它不会显式检查加法运算符，因为在处理完其他所有操作符之后，它是最后一个合法的操作符。

计算函数没有进行高尔夫压缩，可能长这个样子：

void EvalTokens(double *tokenList){
    int i, parenLevel, parenStart;

    for(i = 0; tokenList[i + 1] != 8/*end*/; i+= 2)
        if(tokenList[i + 1] == 0/*open paren*/)
            for(parenLevel = 1, parenStart = i; i += 2, parenLevel > 0){
                if(tokenList[i + 1] == 0/*another open paren*/)
                    parenLevel++;
                else if(tokenList[i + 1] == 1/*close paren*/)
                    if(--parenLevel == 0){
                        /* make this a temporary end of list */
                        tokenList[i + 1] = 8;
                        /* recursively handle the subexpression */
                        EvalTokens(tokenList + parenStart + 2);
                        /* fold the subexpression out */
                        FoldTokens(tokenList + parenStart, i - parenStart);
                        /* bring i back to where the folded value of the
                         * subexpression is now */
                        i = parenStart;
                    }
            }

    for(i = 0; tokenList[i + 1] != 8/*end*/; i+= 2)
        if(tokenList[i + 1] == 6/*exponentiation operator (^)*/){
            tokenList[i - 2] = pow(tokenList[i - 2], tokenList[i + 2]);
            FoldTokens(tokenList + i - 2, 4);
            i -= 2;
        }
    for(i = 0; tokenList[i + 1] != 8/*end*/; i+= 2)
        if(tokenList[i + 1] == 2/*multiplication operator (*)*/ ||
           tokenList[i + 1] == 7/*division operator (/)*/){
            tokenList[i - 2] *=
                (tokenList[i + 1] == 2 ?
                    tokenList[i + 2] :
                    1 / tokenList[i + 2]);
            FoldTokens(tokenList + i - 2, 4);
            i -= 2;
        }
    for(i = 0; tokenList[i + 1] != 8/*end*/; i+= 2)
        if(tokenList[i + 1] != 4/*constant*/){
            tokenList[i - 2] +=
                (tokenList[i + 1] == 3 ?
                    tokenList[i + 2] :
                    -tokenList[i + 2]);
            FoldTokens(tokenList + i - 2, 4);
            i -= 2;
        }
    tokenList[-2] = tokenList[0];
    /* the compressed code does the above in a loop, equivalent to:
     *
     * for(i = 0; tokenList[i + 1] != 8; i+= 2)
     *     tokenList[i - 2] = tokenList[i];
     *
     * This loop will actually only iterate once, and thanks to the
     * liberal use of macros, is shorter. */
}

^{一些压缩可能会使这个函数更易读。}

一旦操作执行完毕，操作数和运算符就会通过K()（通过宏S调用）从标记列表中折叠出来。操作的结果留在折叠表达式的常量位置。因此，最终结果留在标记数组的开头，所以当控制返回到E()时，它只是将其打印到一个字符串中，利用了数组中第一个值是令牌的值字段的事实。

这次对FoldTokens()的调用发生在操作(^, *, /, +或-)执行后，或者在子表达式(括号括起来)处理后。 FoldTokens()例程确保结果值具有正确的运算符类型(4)，然后复制子表达式的剩余部分。例如，当处理表达式"2+6*4+1"时，EvalTokens()首先计算6*4，将结果留在6的位置(2+24*4+1)。然后FoldTokens()删除子表达式"24*4"的其余部分，留下2+24+1。

void FoldTokens(double *tokenList, int offset){
    tokenList++;
    tokenList[0] = 4; // force value to constant

    while(tokenList[0] != 8/*end of token string*/){
        tokenList[0] = tokenList[offset];
        tokenList[1] = tokenList[offset + 1];
        tokenList += 2;
    }
}

那就是这样了。宏只是用来替换常见操作，其他的都是对以上内容进行高尔夫压缩。

Strager 坚持认为代码应包括 #include 语句，因为如果没有对 strtod 和 pow 函数进行适当的前向声明，代码将无法正常工作。由于挑战只要求一个函数而不是完整的程序，我认为这并不是必需的。但可以通过添加以下代码来以最小的代价添加前向声明:

#define D double
D strtod(),pow();

我会将代码中所有的"double"替换为"D"。这将增加19个字符，使总共达到484个字符。另一方面，我也可以像他那样将我的函数转换为返回一个double而不是一个字符串，这将减少15个字符，将E()函数更改为：

D E(char*s){
    D t[99];
    char*e,i=2,z=0;
    for(;*s;i+=2)
        V]=strtod(s,&e),P=z=e-s&&z-4&&z-1?s=e,4:*s++&7;
    P=8;
    M(t+2);
    return*t;
}

这将使得总代码大小为469个字符（或452个字符，如果不包括strtod和pow的前向声明，但包括D宏）。甚至可以通过要求调用者传递一个指向double类型返回值的指针来再次减少1个字符：

E(char*s,D*r){
    D t[99];
    char*e,i=2,z=0;
    for(;*s;i+=2)
        V=strtod(s,&e),P=z=e-s&&z-4&&z-1?s=e,4:*s++&7;
    P=8;
    M(t+2);
    *r=*t;
}

我将把决定留给读者，以确定哪个版本是合适的。

代码高尔夫：数学表达式求值器（遵循PEMDAS规则）

相关:

C (465 characters)

J

F#，70行代码

F#，589个字符

C#（使用大量LINQ），150行

C99 (565 characters)

Minified

扩展

解释

C (277 characters)

F#，52行