Code Golf：数学表达式评估器（尊重 PEMDAS）

我挑战你编写一个遵守 PEMDAS（运算顺序：括号、求幂、乘法、除法、加法、减法）的数学表达式求值器，而不使用正则表达式、预先存在的类似“Eval()”的函数、解析库， ETC。

我看到了一项关于 SO 的现有评估员挑战（here），但是那个特别需要从左到右的评估。

输入和输出示例：

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

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

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

我用 C# 编写了一个评估器，但想看看它与那些使用自己选择的语言的聪明程序员的评估器相比有多糟糕。

Related:

Code Golf：评估数学表达式

澄清：

1. 让我们将其设为一个接受字符串参数并返回字符串结果的函数。

2. 至于为什么没有正则表达式，那是为了公平竞争。我认为“最紧凑的正则表达式”应该有一个单独的挑战。

3. 使用 StrToFloat() 是可以接受的。通过“解析库”，我的意思是排除通用语法解析器之类的东西，也是为了公平竞争。

4. 支持浮标。

5. 支持括号、指数和四个算术运算符。

6. 给予乘法和除法同等的优先级。

7. 加法和减法同等优先。

8. 为简单起见，您可以假设所有输入都是格式正确的。

9. 对于您的函数是否接受“.1”或“1e3”作为有效数字，我没有偏好，但接受它们将为您赢得布朗尼积分。 ;)

10. 对于被零除的情况，您也许可以返回“NaN”（假设您希望实现错误处理）。

C（465 个字符）

#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 行，具有足够的格式，我能够write它，但可能还不足以read它。你会想要#include <stdlib.h>, <stdio.h>, and <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()。它还处理任何一元+ and -运算符，将它们合并到常量中。

令牌数组的“operator”字段可以具有以下值之一：

0: (
1: )
2: *
3: +
4: 浮点常数值
5: -
6: ^
7: /
8: 令牌字符串结尾

该方案主要源自丹尼尔·马丁，他注意到本次挑战赛中每个运算符的 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}。解决方案非常简单。如果解析失败OR前面的标记是一个常量或一个右括号（实际上是一个将计算为常量的子表达式），那么当前标记是一个运算符，否则它是一个常量。

标记化完成后，通过调用完成计算和折叠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. */
}

^{Some amount of compression would probably make this function easier to read.}

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

这个电话给FoldTokens()发生在操作之后（^, *, /, +, or -) 已执行，或在处理子表达式（用括号括起来）之后。这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 and pow和功能。由于挑战只要求一个函数，而不是一个完整的程序，因此我认为这不应该是必需的。但是，可以通过添加以下代码以最小的成本添加前向声明：

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

然后我将替换“的所有实例double” 在代码中带有“D”。这会在代码中添加 19 个字符，使总数达到 484 个。另一方面，我也可以将函数转换为返回双精度值而不是字符串，就像他一样，这会删除 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 and 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;
}

我将让读者决定哪个版本合适。