gar*_*ary 26 math parsing code-golf rosetta-stone
我挑战你写一个数学表达式评估器,它尊重PEMDAS(操作顺序:括号,取幂,乘法,除法,加法,减法)而不使用正则表达式,一个预先存在的"Eval()" - 类似函数,一个解析库等
我在SO(这里)看到了一个预先存在的评估者挑战,但那个特别需要从左到右的评估.
样本输入和输出:
"-1^(-3*4/-6)" -> "1"
"-2^(2^(4-1))" -> "256"
"2*6/4^2*4/3" -> "1"
我在C#中编写了一个评估器,但是我想看看它与那些选择语言的智能程序员相比有多糟糕.
澄清:
让我们使这个函数接受一个字符串参数并返回一个字符串结果.
至于为什么没有正则表达式,那就是平衡竞争环境.我认为"最紧凑的正则表达式"应该有一个单独的挑战.
使用StrToFloat()是可以接受的.通过"解析库",我的意思是排除诸如通用语法解析器之类的东西,也用于平衡游戏场.
支持浮动.
支持paretheses,取幂和四个算术运算符.
赋予乘法和除法优先权.
赋予加法和减法相同的优先权.
为简单起见,您可以假设所有输入都是格式良好的.
我不喜欢你的函数是否接受".1"或"1e3"之类的东西作为有效数字,但是接受它们会获得布朗尼积分.;)
对于除零情况,您可能会返回"NaN"(假设您希望实现错误处理).
P D*_*ddy 27
#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行到100万之间的任何东西,具体取决于我如何格式化它.
入口点是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).这种标记化是在for循环中完成的E().它还涉及任何一元+和-运算符,将它们合并到常量中.
令牌数组的"operator"字段可以具有以下值之一:
0:
(
1:)
2:*
3:+
4:浮点常量值
5:-
6:^
7:/
8:令牌字符串结束
这个方案主要是由Daniel Martin推导出来的,他注意到最后3位在这次挑战中每个运营商的ASCII表示中是唯一的.
未压缩的版本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;
}
我会留给读者来决定哪个版本是合适的.
Jas*_*son 16
C#,13行:
static string Calc(string exp)
{
WebRequest request = WebRequest.Create("http://google.com/search?q=" +
HttpUtility.UrlDecode(exp));
using (WebResponse response = request.GetResponse())
using (Stream dataStream = response.GetResponseStream())
using (StreamReader reader = new StreamReader(dataStream))
{
string r = reader.ReadToEnd();
int start = r.IndexOf(" = ") + 3;
int end = r.IndexOf("<", start);
return r.Substring(start, end - start);
}
}
这压缩到大约317个字符:
static string C(string e){var q = WebRequest.Create("http://google.com/search?q="
+HttpUtility.UrlDecode(e));using (var p=q.GetResponse()) using (var s=
p.GetResponseStream()) using (var d = new StreamReader(dataStream)){var
r=d.ReadToEnd();var t=r.IndexOf(" = ") + 3;var e=r.IndexOf("<",t);return
r.Substring(t,e-t);}}
感谢Mark和P Daddy的评论,压缩到195个字符:
string C(string f){using(var c=new WebClient()){var r=c.DownloadString
("http://google.com/search?q="+HttpUtility.UrlDecode(f));int s=r.IndexOf(
" = ")+3;return r.Substring(s,r.IndexOf("<",f)-s);}}
Ale*_*lex 10
:[[/%^(:[[+-/^,&i|:[$[' ']^j+0__:k<3:]]
好的,我实现了一个monadic解析器组合库,然后使用该库来解决这个问题.所有人都告诉它仍然只有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>
顺便说一下,非错误处理解析器的常见问题.
PARLANSE中的递归下降解析器,具有LISP语法的类C语言:[70行,1376个字符不计算SO所需的缩进量]编辑:规则已更改,有人坚持浮点数,已修复.没有库调用,浮动转换,输入和打印除外.[现在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.没有编译和运行.
Pecularities:定义f本质上是签名typedef.lambdas是解析函数,每个语法规则一个.通过写(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} ;
我将之前的解决方案高尔夫压缩到这个宝石:
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