当前位置： 文江博客话题详情

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

发布于 2024-08-03 19:25:48 字数 1098 浏览 10 评论 0原文

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

我在 SO 上看到了一个预先存在的评估器挑战（此处），但是那一个特别需要从左到右的评估。

输入和输出示例：

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

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

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

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

有关的：

Code Golf：评估数学表达式

说明：

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

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

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

  4. 支持浮动。

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

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

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

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

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

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

原文

I challenge you to write a mathematical expression evaluator that respects PEMDAS (order of operations: parentheses, exponentiation, multiplication, division, addition, subtraction) without using regular expressions, a pre-existing "Eval()"-like function, a parsing library, etc.

I saw one pre-existing evaluator challenge on SO (here), but that one specifically required left-to-right evaluation.

Sample inputs and outputs:

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

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

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

I wrote an evaluator in C#, but would like to see how badly it compares to those of smarter programmers in their languages of choice.

Related:

Code Golf: Evaluating mathematical expressions

Clarifications:

  1. Let's make this a function that accepts a string argument and returns a string result.

  2. As for why no regexes, well, that's to level the playing field. I think there ought to be a separate challenge for "the most compact regex".

  3. Using StrToFloat() is acceptable. By "parsing library" I meant to exclude such things as general-purpose grammar parsers, also to level the playing-field.

  4. Support floats.

  5. Support paretheses, exponentiation, and the four arithmetic operators.

  6. Give multiplication and division equal precedence.

  7. Give addition and subtraction equal precedence.

  8. For simplicity, you may assume all inputs are well-formed.

  9. I don't have a preference as to whether your function accepts such things as ".1" or "1e3" as valid numbers, but accepting them would earn you brownie points. ;)

  10. For divide-by-zero cases, you could perhaps return "NaN" (assuming you wish to implement error handling).

如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论， 你可以免费 注册 一个本站的账号。

评论（18）

独木成林 2024-08-10 19:25:48

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 行，其格式足以让我编写它，但可能不足以阅读它。您需要 #include 、 和 （或参见底部的注释）。

请参阅代码后面的内容以了解其工作原理的说明。

#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 循环中完成的。它还处理任何一元 + 和 - 运算符，并将它们合并到常量中。

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

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}。解决方案非常简单。如果解析失败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. */
}

一些的压缩量可能会使该函数更容易阅读。

一旦执行操作时，操作数和运算符通过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 个。另一方面，我也可以将函数转换为返回双精度值而不是字符串，就像他所做的那样，这将删除 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 个字符（如果没有 strtod 和 pow< 的前向声明，则为 452 个字符） /code>，但使用 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;
}

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

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

The first five newlines are required, the rest are there just for readability. I've counted the first five newlines as one character each. If you want to measure it in lines, it was 28 lines before I removed all the whitespace, but that's a pretty meaningless number. It could have been anything from 6 lines to a million, depending on how I formatted it.

The entry point is E() (for "evaluate"). The first parameter is the input string, and the second parameter points to the output string, and must be allocated by the caller (as per usual C standards). It can handle up to 47 tokens, where a token is either an operator (one of "+-*/^()"), or a floating point number. Unary sign operators do not count as a separate token.

This code is loosely based on a project I did many years ago as an exercise. I took out all the error handling and whitespace skipping and retooled it using golf techniques. Below are the 28 lines, with enough formatting that I was able to write it, but probably not enough to read it. You'll want to #include <stdlib.h>, <stdio.h>, and <math.h> (or see note at the bottom).

See after the code for an explanation of how it works.

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

The first step is to tokenize. The array of doubles contains two values for each token, an operator (P, because O looks too much like zero), and a value (V). This tokenizing is what is done in the for loop in E(). It also deals with any unary + and - operators, incorporating them into the constant.

The "operator" field of the token array can have one of the following values:

0: (
1: )
2: *
3: +
4: a floating-point constant value
5: -
6: ^
7: /
8: end of token string

This scheme was largely derived by Daniel Martin, who noticed that the last 3 bits were unique in the ASCII representation of each of the operators in this challenge.

An uncompressed version of E() would look something like this:

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

Since we're guaranteed valid input, the only reason the parsing would fail would be because the next token is an operator. If this happens, the parseEnd pointer will be the same as, tokenStart. We must also handle the case where parsing succeeded, but what we really wanted was an operator. This would occur for the addition and subtraction operators, unless a sign operator directly followed. In other words, given the expression "4-6", we want to parse it as {4, -, 6}, and not as {4, -6}. On the other hand, given "4+-6", we should parse it as {4, +, -6}. The solution is quite simple. If parsing fails OR the preceding token was a constant or a closing parenthesis (effectively a subexpression which will evaluate to a constant), then the current token is an operator, otherwise it's a constant.

After tokenizing is done, calculating and folding are done by calling M(), which first looks for any matched pairs of parentheses and processes the subexpressions contained within by calling itself recursively. Then it processes operators, first exponentiation, then multiplication and division together, and finally addition and subtraction together. Because well-formed input is expected (as specified in the challenge), it doesn't check for the addition operator explicitly, since it's the last legal operator after all the others are processed.

The calculation function, lacking golf compression, would look something like this:

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.

Once an operation is performed, the operands and operator are folded out of the token list by K() (called through the macro S). The result of the operation is left as a constant in place of the folded expression. Consequently, the final result is left at the beginning of the token array, so when control returns to E(), it simply prints that to a string, taking advantage of the fact that the first value in the array is the value field of the token.

This call to FoldTokens() takes place either after an operation (^, *, /, +, or -) has been performed, or after a subexpression (surrounded by parentheses) has been processed. The FoldTokens() routine ensures that the result value has the correct operator type (4), and then copies the rest of the larger expression of the subexpression. For instance, when the expression "2+6*4+1" is processed, EvalTokens() first calculates 6*4, leaving the result in place of the 6 (2+24*4+1). FoldTokens() then removes the rest of the sub expression "24*4", leaving 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;
    }
}

That's it. The macros are just there to replace common operations, and everything else is just golf-compression of the above.

strager insists that the code should include #include statements, as it will not function correctly without a proper forward declation of the strtod and pow and functions. Since the challenge asks for just a function, and not a complete program, I hold that this should not be required. However, forward declarations could be added at minimal cost by adding the following code:

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

I would then replace all instances of "double" in the code with "D". This would add 19 characters to the code, bringing the total up to 484. On the other hand, I could also convert my function to return a double instead of a string, as did he, which would trim 15 characters, changing the E() function to this:

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

This would make the total code size 469 characters (or 452 without the forward declarations of strtod and pow, but with the D macro). It would even be possible to trim 1 more characters by requiring the caller to pass in a pointer to a double for the return value:

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

I'll leave it to the reader to decide which version is appropriate.

回复 原文
倾其所爱 2024-08-10 19:25:48

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

C#, 13 lines:

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

This compresses down to about 317 characters:

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

Thanks to Mark and P Daddy in the comments, is compresses to 195 characters:

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);}}
回复 原文
愁杀 2024-08-10 19:25:48

J

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

J

:[[/%^(:[[+-/^,&i|:[$[' ']^j+0__:k<3:]]
回复 原文
离旧人 2024-08-10 19:25:48

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>

错误处理解析器的常见类型。

F#, 70 lines

Ok, I implement a monadic parser combinator library, and then use that library to solve this problem. All told it's still just 70 lines of readable code.

I assume exponentiation associates to the right, and the other operators associate to the left. Everything works on floats (System.Doubles). I did not do any error handling for bad inputs or divide-by-zero.

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

The parser representation type is

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

by the way, a common one for non-error-handling parsers.

回复 原文
带刺的爱情 2024-08-10 19:25:48

PARLANSE 中的递归下降解析器，一种具有 LISP 语法的类 C 语言：
[70 行，1376 个字符，不包括 SO 所需的 4 缩进]
编辑：规则改变了，有人坚持使用浮点数，修复了。
除了浮点转换、输入和打印之外，没有库调用。
[现在 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} ;

Recursive descent parser in PARLANSE, a C-like langauge with LISP syntax:
[70 lines, 1376 characters not counting indent-by-4 needed by SO]
EDIT: Rules changed, somebody insisted on floating point numbers, fixed.
No library calls except the float conversion, input and print.
[now 94 lines, 1825 characters]

(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

Assumes a well-formed expression, float numbers with at least
one leading digit, exponents optional as Enn or E-nnn.
Not compiled and run.

Pecularities: the definition f is essentially signature typedef.
The lambdas are the parsing functions, one per grammar rule.
A function F is called by writing (F args).
PARLANSE functions are lexically scoped, so each function has
implicit access to the expression s to be evaluated and
a string scanning index i.

The grammar implemented is:

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} ;
回复 原文
孤檠 2024-08-10 19:25:48

F#，589 个字符

我将之前的解决方案压缩到这个 gem 中：

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

F#, 589 chars

I golf-compressed my prior solution into this gem:

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

Tests:

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
回复 原文
℉服软 2024-08-10 19:25:48

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

C# (with much LINQ), 150 lines

Ok, I implement a monadic parser combinator library, and then use that library to solve this problem. All told it's about 150 lines of code. (This is basically a straight transliteration of my F# solution.)

I assume exponentiation associates to the right, and the other operators associate to the left. Everything works on System.Doubles. I did not do any error handling for bad inputs or divide-by-zero.

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
    }
}
回复 原文
ぃ弥猫深巷。 2024-08-10 19:25:48

C99（565 个字符）

缩小

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

解释

开发了我自己的技术。你自己想办法吧。 =]

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

Expanded

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

Explanation

Developed my own technique. Figure it out yourself. =]

回复 原文
清旖 2024-08-10 19:25:48

C (277 个字符)

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

由于 OP 的“参考实现”是用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;
}

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

The first newline is required, and I've counted it as one character.

This is a completely different approach from my other answer. It's more of a functional approach. Instead of tokenizing and looping through several times, this one evaluates the expression in one pass, using recursive calls for higher-precedence operators, effectively using the call stack to store state.

To satisfy strager ;), this time I've included forward declarations of strtod(), pow(), and strchr(). Taking them out would save 26 characters.

The entry point is M(). The input string is the first parameter, and the output double is the second parameter. The entry point used to be E(), which returned a string, as the OP asked. But since mine was the only C implementation doing so, I decided to yank it out (peer pressure, and all). Adding it back in would add 43 characters:

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

Below is the code before I compressed it:

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

Since the OP's "reference implementation" is in C#, I wrote a semi-compressed C# version as well:

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;
}
回复 原文
清君侧 2024-08-10 19:25:48

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

F#, 52 lines

This one mostly eschews generality, and just focuses on writing a recursive descent parser to solve this exact problem.

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
回复 原文
痴情 2024-08-10 19:25:48

C，609 个字符

（625 个字符，包括如下格式以避免水平滚动，如果我使其可读，则为 42 行。）

double x(char*e,int*p);
D(char c){return c>=48&&c<=57;}
S(char c){return c==43||c==45;}
double h(char*e,int*p){double r=0,s=1,f=0,m=1;int P=*p;if(e[P]==40){
 P++;r=x(e,&P);P++;}else if(D(e[P])||S(e[P])){s=S(e[P])?44-e[P++]:s;
 while(D(e[P]))r=r*10+e[P++]-48;if(e[P]==46)while(D(e[++P])){f=f*10+e[P]-48;
 m*=10;}r=s*(r+f/m);}*p=P;return r;}
double x(char*e,int*p){double r=0,t,d,x,s=1;do{char o=42;t=1;do{d=h(e,p);
 while(e[*p]==94){(*p)++;x=h(e,p);d=pow(d,x);}t=o==42?t*d:t/d;o=e[*p];
 if(o==42||o==47)(*p)++;else o=0;}while(o);r+=s*t;s=S(e[*p])?44-e[(*p)++]:0;
}while(s);return r;}
double X(char*e){int p=0;return x(e,&p);}

这是我的第一个高尔夫代码。

我自己解析浮点数，我使用的唯一库函数是pow。

我纠正了多次幂提升和括号处理的错误。我还制作了仅接受字符串作为参数的主函数 X() 。但它仍然返回一个双精度值。

扩展

42 个非空行

double x(char*e, int*p);

D(char c) { return c>=48 && c<=57; }
S(char c) { return c==43 || c==45; }

double h(char*e, int*p) {
    double r=0, s=1, f=0, m=1;
    int P=*p;
    if(e[P]==40) {
        P++;
        r=x(e, &P);
        P++; }
    else if(D(e[P]) || S(e[P])) {
        s=S(e[P]) ? 44-e[P++] : s;
        while(D(e[P]))
            r=r*10+e[P++]-48;
        if(e[P]==46)
            while(D(e[++P])) {
                f=f*10+e[P]-48;
                m*=10; }
        r=s*(r+f/m); }
        *p=P;
    return r; }

double x(char*e, int*p) {
    double r=0, t, d, x, s=1;
    do {
        char o=42;
        t=1;
        do {
            d=h(e, p);
            while(e[*p]==94) {
                (*p)++;
                x=h(e, p);
                d=pow(d, x); }
            t=o==42 ? t*d : t/d;
            o=e[*p];
            if(o==42 || o==47) (*p)++;
            else o=0;
        } while(o);
        r+=s*t;
        s=S(e[*p]) ? 44-e[(*p)++] : 0;
    } while(s);
    return r; }

double X(char*e) {int p=0; return x(e, &p);}

C, 609 characters

(625 including formatted as below to avoid horizontal scrolling, 42 lines if I make it readable.)

double x(char*e,int*p);
D(char c){return c>=48&&c<=57;}
S(char c){return c==43||c==45;}
double h(char*e,int*p){double r=0,s=1,f=0,m=1;int P=*p;if(e[P]==40){
 P++;r=x(e,&P);P++;}else if(D(e[P])||S(e[P])){s=S(e[P])?44-e[P++]:s;
 while(D(e[P]))r=r*10+e[P++]-48;if(e[P]==46)while(D(e[++P])){f=f*10+e[P]-48;
 m*=10;}r=s*(r+f/m);}*p=P;return r;}
double x(char*e,int*p){double r=0,t,d,x,s=1;do{char o=42;t=1;do{d=h(e,p);
 while(e[*p]==94){(*p)++;x=h(e,p);d=pow(d,x);}t=o==42?t*d:t/d;o=e[*p];
 if(o==42||o==47)(*p)++;else o=0;}while(o);r+=s*t;s=S(e[*p])?44-e[(*p)++]:0;
}while(s);return r;}
double X(char*e){int p=0;return x(e,&p);}

It's my first code golf.

I'm parsing floats myself and the only library function I use is pow.

I corrected errors with multiple elevations to a power and handling of parentheses. I also made the main function X() that takes just a string as argument. It still returns a double, though.

Expanded

42 non-blank lines

double x(char*e, int*p);

D(char c) { return c>=48 && c<=57; }
S(char c) { return c==43 || c==45; }

double h(char*e, int*p) {
    double r=0, s=1, f=0, m=1;
    int P=*p;
    if(e[P]==40) {
        P++;
        r=x(e, &P);
        P++; }
    else if(D(e[P]) || S(e[P])) {
        s=S(e[P]) ? 44-e[P++] : s;
        while(D(e[P]))
            r=r*10+e[P++]-48;
        if(e[P]==46)
            while(D(e[++P])) {
                f=f*10+e[P]-48;
                m*=10; }
        r=s*(r+f/m); }
        *p=P;
    return r; }

double x(char*e, int*p) {
    double r=0, t, d, x, s=1;
    do {
        char o=42;
        t=1;
        do {
            d=h(e, p);
            while(e[*p]==94) {
                (*p)++;
                x=h(e, p);
                d=pow(d, x); }
            t=o==42 ? t*d : t/d;
            o=e[*p];
            if(o==42 || o==47) (*p)++;
            else o=0;
        } while(o);
        r+=s*t;
        s=S(e[*p]) ? 44-e[(*p)++] : 0;
    } while(s);
    return r; }

double X(char*e) {int p=0; return x(e, &p);}
回复 原文
小矜持 2024-08-10 19:25:48

Ruby，现在 44 行

C89，46 行

这些可能会塞满。 C 程序包含并非严格需要的标头以及其他一些条目未包含的 main() 程序。 Ruby 程序执行 I/O 来获取字符串，这在技术上不是必需的...

我意识到递归下降解析器实际上并不需要为每个优先级提供单独的例程，尽管这就是它在引用中始终显示的方式。因此，我修改了之前的 Ruby 条目，将三个二进制优先级合并为一个采用优先级参数的递归例程。我添加 C89 是为了好玩。有趣的是，这两个程序的行数大致相同。

红宝石

puts class RHEvaluator
  def setup e
    @opByPri, @x, @TOPPRI = [[?+,0],[?-,0],[?*,1],[?/,1],[?^,2]], e, 3
    getsym
    rhEval 0
  end
  def getsym
    @c = @x[0]
    @x = @x.drop 1
  end
  def flatEval(op, a, b)
    case op
      when ?* then a*b
      when ?/ then a/b
      when ?+ then a+b
      when ?- then a-b
      when ?^ then a**b
    end
  end
  def factor
    t = @c
    getsym
    t = case t
      when ?-     then -factor
      when ?0..?9 then t.to_f - ?0
      when ?(
    t = rhEval 0
    getsym  # eat )
    t
    end
    t
  end
  def rhEval pri
    return factor if pri >= @TOPPRI;
    v = rhEval pri + 1
    while (q = @opByPri.assoc(@c)) && q[1] == pri
      op = @c
      getsym
      v = flatEval op, v, rhEval(pri + 1)
    end
    v
  end
  RHEvaluator     # return an expression from the class def
end.new.setup gets.bytes.to_a

C89

#include <stdio.h>
#include <math.h>
#include <strings.h>
#define TOPPRI '3'
#define getsym() token = *x++;
const char opByPri[] = "+0-0*1/1^2";
char  token, *x;
double rhEval(int);
int main(int ac, char **av) {
    x = av[1];
    getsym();
    return printf("%f\n", rhEval('0')), 0;
}
double flatEval(char op, double a, double b) {
    switch (op) {
    case '*': return a * b;
    case '/': return a / b;
    case '+': return a + b;
    case '-': return a - b;
    case '^': return pow(a, b);
}   }
double factor(void) {
    double d; char t = token;
    getsym();
    switch (t) {
    case '-': return -factor();
    case '0': case '1': case '2': case '3': case '4':
    case '5': case '6': case '7': case '8': case '9':
              return t - '0';
    case '(': d = rhEval('0');
              getsym();
    }
    return d;
}
double rhEval(int pri) {
    double v; char *q;
    if (pri >= TOPPRI)
        return factor();
    v = rhEval(pri + 1);
    while ((q = index(opByPri, token)) && q[1] == pri) {
        char op = token;
        getsym();
        v = flatEval(op, v, rhEval(pri + 1));
    }
    return v;
}

Ruby, now 44 lines

C89, 46 lines

These could be crammed a lot. The C program includes headers that aren't strictly needed and a main() program that some other entries didn't include. The Ruby program does I/O to get the strings, which wasn't technically required...

I realized that the recursive descent parser doesn't really need separate routines for each priority level, even though that's how it's always shown in references. So I revised my previous Ruby entry by collapsing the three binary priority levels into one recursive routine that takes a priority parameter. I added C89 for fun. It's interesting that the two programs have about the same number of lines.

Ruby

puts class RHEvaluator
  def setup e
    @opByPri, @x, @TOPPRI = [[?+,0],[?-,0],[?*,1],[?/,1],[?^,2]], e, 3
    getsym
    rhEval 0
  end
  def getsym
    @c = @x[0]
    @x = @x.drop 1
  end
  def flatEval(op, a, b)
    case op
      when ?* then a*b
      when ?/ then a/b
      when ?+ then a+b
      when ?- then a-b
      when ?^ then a**b
    end
  end
  def factor
    t = @c
    getsym
    t = case t
      when ?-     then -factor
      when ?0..?9 then t.to_f - ?0
      when ?(
    t = rhEval 0
    getsym  # eat )
    t
    end
    t
  end
  def rhEval pri
    return factor if pri >= @TOPPRI;
    v = rhEval pri + 1
    while (q = @opByPri.assoc(@c)) && q[1] == pri
      op = @c
      getsym
      v = flatEval op, v, rhEval(pri + 1)
    end
    v
  end
  RHEvaluator     # return an expression from the class def
end.new.setup gets.bytes.to_a

C89

#include <stdio.h>
#include <math.h>
#include <strings.h>
#define TOPPRI '3'
#define getsym() token = *x++;
const char opByPri[] = "+0-0*1/1^2";
char  token, *x;
double rhEval(int);
int main(int ac, char **av) {
    x = av[1];
    getsym();
    return printf("%f\n", rhEval('0')), 0;
}
double flatEval(char op, double a, double b) {
    switch (op) {
    case '*': return a * b;
    case '/': return a / b;
    case '+': return a + b;
    case '-': return a - b;
    case '^': return pow(a, b);
}   }
double factor(void) {
    double d; char t = token;
    getsym();
    switch (t) {
    case '-': return -factor();
    case '0': case '1': case '2': case '3': case '4':
    case '5': case '6': case '7': case '8': case '9':
              return t - '0';
    case '(': d = rhEval('0');
              getsym();
    }
    return d;
}
double rhEval(int pri) {
    double v; char *q;
    if (pri >= TOPPRI)
        return factor();
    v = rhEval(pri + 1);
    while ((q = index(opByPri, token)) && q[1] == pri) {
        char op = token;
        getsym();
        v = flatEval(op, v, rhEval(pri + 1));
    }
    return v;
}
回复 原文
浅浅 2024-08-10 19:25:48

C（249 个字符）

char*c;double m(char*s,int o){int i;c=s;double x=*s-40?strtod(c,&s):m(c+1,0);double y;for(;*c&&c-41;c++){for(i=0;i<7&&*c-"``-+/*^"[i];i++);if(i<7){if(i/2<=o/2){c-=*c!=41;break;}y=m(c+1,i);x=i-6?i-5?i-4?i-3?i-2?x:x-y:x+y:x/y:x*y:pow(x,y);}}return x;}

这是我以前的版本的稍微修改的版本。通过使用 strtod 而不是 atof（P Daddy 的支持），我能够将其削减约 90 个字符！

功能

  • 支持指数、乘法、除法、加法和减法。请注意，它不支持一元减号，因为规范中没有提到这一点，尽管它已在 OP 的测试用例中使用。我认为它是含糊不清的，可以忽略
  • 它的长度为 249 个字符
  • 支持双精度算术
  • 它的长度为 249 个字符
  • 支持 PEMDAS，尽管指数关联为“x^y^z”->“(x^y)^z”，而不是as "x^(y^z)"
  • 假设输入不是垃圾。垃圾进来，垃圾出去。
  • 我有没有提到它有 249 个字符长？ :P

用法

将指针传递给以 null 结尾的字符数组，然后传递 0。如下所示：

m(charPtr,0)

您必须在调用该函数的源文件中包含 math.h 和 stdlib.h。另请注意，char*c 在代码开头全局定义。因此，不要在使用此的任何内容中定义任何名为 c 的变量。如果你必须有办法否定事物，“-[在此处插入表达式]”相当于“(0-[在此处插入表达式])”，OP 的优先顺序是这样的

C (249 characters)

char*c;double m(char*s,int o){int i;c=s;double x=*s-40?strtod(c,&s):m(c+1,0);double y;for(;*c&&c-41;c++){for(i=0;i<7&&*c-"``-+/*^"[i];i++);if(i<7){if(i/2<=o/2){c-=*c!=41;break;}y=m(c+1,i);x=i-6?i-5?i-4?i-3?i-2?x:x-y:x+y:x/y:x*y:pow(x,y);}}return x;}

This is a somewhat-revamped version of my previous version. By using strtod instead of atof (props to P Daddy) I was able to cut it by ~90 chars!

Features

  • Supports exponentation, multiplication, division, addition, and subtraction. Note that it DOES NOT support unary minus, since that wasn't mentioned in the spec, even though it was used in the OP's test cases. I thought it was ambiguous enough to leave out
  • It's 249 chars long
  • Supports double-precision arithmetic
  • It's 249 chars long
  • Supports PEMDAS, though exponentation associates as "x^y^z"->"(x^y)^z", not as "x^(y^z)"
  • Assumes that input isn't garbage. Garbage in, garbage out.
  • Did I mention it's 249 chars long? :P

Usage

Pass a pointer to a null-terminated array of chars, then 0. Like so:

m(charPtr,0)

You must include math.h and stdlib.h in the source file you call the function from. Also note that char*c is defined globally at the start of the code. So don't define any variable named c in anything using this. If you must have a way to negate things, "-[insert expression here]" is equivalent to "(0-[insert expression here])" the way the OP has precedence ordered

回复 原文
倾城°AllureLove 2024-08-10 19:25:48

我知道，我知道……这个代码高尔夫似乎已经结束了。
尽管如此，我还是很想用 erlang __ 编写这些东西，所以这里是一个 erlang 版本（没有找到高尔夫格式的意愿，所以这些是 58 行，大约 1400 个字符）

-module (math_eval).
-export ([eval/1]).
eval( Str ) ->
  ev(number, Str,[]).
ev( _, [], Stack ) -> [Num] = do(Stack), Num;
ev( State, [$ |Str], Stack ) ->
  ev( State,Str,Stack );
ev( number, [$(|Str], Stack ) ->
  ev( number,Str,[$(|Stack] );
ev( number, Str, Stack ) ->
  {Num,Str1} = r(Str),
  ev( operator,Str1,[Num|Stack] );
ev( operator, [$)|Str], Stack) ->
  ev( operator, Str, do(Stack) );
ev( operator, [Op2|Str], [N2,Op,N1|T]=Stack ) when is_float(N1) andalso is_float(N2) ->
  case p(Op2,Op) of
    true -> ev( number, Str, [Op2|Stack]);
    false -> ev( operator, [Op2|Str], [c(Op,N1,N2)|T] )
  end;
ev( operator, [Op|Str], Stack ) ->
  ev( number,Str,[Op|Stack] ).
do(Stack) ->
  do(Stack,0).
do([],V) -> [V];
  do([$(|Stack],V) -> [V|Stack];
do([N2,Op,N1|Stack],0) ->
  do(Stack,c(Op,N1,N2));
do([Op,N1|Stack],V) ->
  do(Stack,c(Op,N1,V)).
p(O1,O2) -> op(O1) < op(O2).
op(O) ->
  case O of
    $) -> 0; $( -> 0;
    $^ -> 1;
    $* -> 2; $/ -> 2;
    $+ -> 3; $- -> 3;
    $  -> 4; _ -> -1
  end.
r(L) ->
  r(L,[]).
r([], Out) ->
  {f( lists:reverse(Out) ),[]};
r([$-|R],[]) ->
  r(R,[$-]);
r([C|T]=R,O) ->
  if (C =< $9 andalso C >= $0) orelse C =:= $. -> r(T,[C|O]);
    true -> {f(lists:reverse(O)),R}
  end.
f(L) ->
  case lists:any(fun(C) -> C =:= $. end,L) of
    true -> list_to_float(L);
    false -> list_to_float(L++".0")
  end.
c($+,A,B) -> A+B;
c($-,A,B) -> A-B;
c($*,A,B) -> A*B;
c($/,A,B) -> A/B;
c($^,A,B) -> math:pow(A,B).

I know, I know..this code-golf seems to be closed.
Still, I felt the urge to code this stuff in erlang __, so here is an erlang version (didn't found the will to golf-format it, so these are 58 lines, about 1400 chars)

-module (math_eval).
-export ([eval/1]).
eval( Str ) ->
  ev(number, Str,[]).
ev( _, [], Stack ) -> [Num] = do(Stack), Num;
ev( State, [$ |Str], Stack ) ->
  ev( State,Str,Stack );
ev( number, [$(|Str], Stack ) ->
  ev( number,Str,[$(|Stack] );
ev( number, Str, Stack ) ->
  {Num,Str1} = r(Str),
  ev( operator,Str1,[Num|Stack] );
ev( operator, [$)|Str], Stack) ->
  ev( operator, Str, do(Stack) );
ev( operator, [Op2|Str], [N2,Op,N1|T]=Stack ) when is_float(N1) andalso is_float(N2) ->
  case p(Op2,Op) of
    true -> ev( number, Str, [Op2|Stack]);
    false -> ev( operator, [Op2|Str], [c(Op,N1,N2)|T] )
  end;
ev( operator, [Op|Str], Stack ) ->
  ev( number,Str,[Op|Stack] ).
do(Stack) ->
  do(Stack,0).
do([],V) -> [V];
  do([$(|Stack],V) -> [V|Stack];
do([N2,Op,N1|Stack],0) ->
  do(Stack,c(Op,N1,N2));
do([Op,N1|Stack],V) ->
  do(Stack,c(Op,N1,V)).
p(O1,O2) -> op(O1) < op(O2).
op(O) ->
  case O of
    $) -> 0; $( -> 0;
    $^ -> 1;
    $* -> 2; $/ -> 2;
    $+ -> 3; $- -> 3;
    $  -> 4; _ -> -1
  end.
r(L) ->
  r(L,[]).
r([], Out) ->
  {f( lists:reverse(Out) ),[]};
r([$-|R],[]) ->
  r(R,[$-]);
r([C|T]=R,O) ->
  if (C =< $9 andalso C >= $0) orelse C =:= $. -> r(T,[C|O]);
    true -> {f(lists:reverse(O)),R}
  end.
f(L) ->
  case lists:any(fun(C) -> C =:= $. end,L) of
    true -> list_to_float(L);
    false -> list_to_float(L++".0")
  end.
c($+,A,B) -> A+B;
c($-,A,B) -> A-B;
c($*,A,B) -> A*B;
c($/,A,B) -> A/B;
c($^,A,B) -> math:pow(A,B).
回复 原文
望喜 2024-08-10 19:25:48

这是我在 C# 中的“参考实现”（有点笨拙）。

    static int RevIndexOf(string S, char Ch, int StartPos)
    {
        for (int P = StartPos; P >= 0; P--)
            if (S[P] == Ch)
                return P;
        return -1;
    }

    static bool IsDigit(char Ch)
    {
        return (((Ch >= '0') && (Ch <= '9')) || (Ch == '.'));
    }

    static int GetNextOperator(List<string> Tokens)
    {
        int R = Tokens.IndexOf("^");

        if (R != -1)
            return R;

        int P1 = Tokens.IndexOf("*");
        int P2 = Tokens.IndexOf("/");

        if ((P1 == -1) && (P2 != -1))
            return P2;
        if ((P1 != -1) && (P2 == -1))
            return P1;
        if ((P1 != -1) && (P2 != -1))
            return Math.Min(P1, P2);

        P1 = Tokens.IndexOf("+");
        P2 = Tokens.IndexOf("-");

        if ((P1 == -1) && (P2 != -1))
            return P2;
        if ((P1 != -1) && (P2 == -1))
            return P1;
        if ((P1 != -1) && (P2 != -1))
            return Math.Min(P1, P2);

        return -1;
    }

    static string ParseSubExpression(string SubExpression)
    {
        string[] AA = new string[] { "--", "++", "+-", "-+" };
        string[] BB = new string[] { "+", "+", "-", "-" };

        for (int I = 0; I < 4; I++)
            while (SubExpression.IndexOf(AA[I]) != -1)
                SubExpression = SubExpression.Replace(AA[I], BB[I]);

        const string Operators = "^*/+-";

        List<string> Tokens = new List<string>();
        string Token = "";

        foreach (char Ch in SubExpression)
            if (IsDigit(Ch) || (("+-".IndexOf(Ch) != -1) && (Token == "")))
                Token += Ch;
            else
                if (Operators.IndexOf(Ch) != -1)
                {
                    Tokens.Add(Token);
                    Tokens.Add(Ch + "");
                    Token = "";
                }
                else
                    throw new Exception("Unhandled error: invalid expression.");

        Tokens.Add(Token);

        int P1 = GetNextOperator(Tokens);

        while (P1 != -1)
        {
            double A = double.Parse(Tokens[P1 - 1]);
            double B = double.Parse(Tokens[P1 + 1]);
            double R = 0;

            switch (Tokens[P1][0])
            {
                case '^':
                    R = Math.Pow(A, B);
                    break;
                case '*':
                    R = A * B;
                    break;
                case '/':
                    R = A / B;
                    break;
                case '+':
                    R = A + B;
                    break;
                case '-':
                    R = A - B;
                    break;
            }

            Tokens[P1] = R.ToString();
            Tokens.RemoveAt(P1 + 1);
            Tokens.RemoveAt(P1 - 1);
            P1 = GetNextOperator(Tokens);
        }

        if (Tokens.Count == 1)
            return Tokens[0];
        else
            throw new Exception("Unhandled error.");
    }

    static bool FindSubExpression(string Expression, out string Left, out string Middle, out string Right)
    {
        int P2 = Expression.IndexOf(')');
        if (P2 == -1)
        {
            Left = "";
            Middle = "";
            Right = "";
            return false;
        }
        else
        {
            int P1 = RevIndexOf(Expression, '(', P2);
            if (P1 == -1)
                throw new Exception("Unhandled error: unbalanced parentheses.");
            Left = Expression.Substring(0, P1);
            Middle = Expression.Substring(P1 + 1, P2 - P1 - 1);
            Right = Expression.Remove(0, P2 + 1);
            return true;
        }
    }

    static string ParseExpression(string Expression)
    {
        Expression = Expression.Replace(" ", "");

        string Left, Middle, Right;
        while (FindSubExpression(Expression, out Left, out Middle, out Right))
            Expression = Left + ParseSubExpression(Middle) + Right;

        return ParseSubExpression(Expression);
    }

This is my "reference implementation" in C# (somewhat unwieldy).

    static int RevIndexOf(string S, char Ch, int StartPos)
    {
        for (int P = StartPos; P >= 0; P--)
            if (S[P] == Ch)
                return P;
        return -1;
    }

    static bool IsDigit(char Ch)
    {
        return (((Ch >= '0') && (Ch <= '9')) || (Ch == '.'));
    }

    static int GetNextOperator(List<string> Tokens)
    {
        int R = Tokens.IndexOf("^");

        if (R != -1)
            return R;

        int P1 = Tokens.IndexOf("*");
        int P2 = Tokens.IndexOf("/");

        if ((P1 == -1) && (P2 != -1))
            return P2;
        if ((P1 != -1) && (P2 == -1))
            return P1;
        if ((P1 != -1) && (P2 != -1))
            return Math.Min(P1, P2);

        P1 = Tokens.IndexOf("+");
        P2 = Tokens.IndexOf("-");

        if ((P1 == -1) && (P2 != -1))
            return P2;
        if ((P1 != -1) && (P2 == -1))
            return P1;
        if ((P1 != -1) && (P2 != -1))
            return Math.Min(P1, P2);

        return -1;
    }

    static string ParseSubExpression(string SubExpression)
    {
        string[] AA = new string[] { "--", "++", "+-", "-+" };
        string[] BB = new string[] { "+", "+", "-", "-" };

        for (int I = 0; I < 4; I++)
            while (SubExpression.IndexOf(AA[I]) != -1)
                SubExpression = SubExpression.Replace(AA[I], BB[I]);

        const string Operators = "^*/+-";

        List<string> Tokens = new List<string>();
        string Token = "";

        foreach (char Ch in SubExpression)
            if (IsDigit(Ch) || (("+-".IndexOf(Ch) != -1) && (Token == "")))
                Token += Ch;
            else
                if (Operators.IndexOf(Ch) != -1)
                {
                    Tokens.Add(Token);
                    Tokens.Add(Ch + "");
                    Token = "";
                }
                else
                    throw new Exception("Unhandled error: invalid expression.");

        Tokens.Add(Token);

        int P1 = GetNextOperator(Tokens);

        while (P1 != -1)
        {
            double A = double.Parse(Tokens[P1 - 1]);
            double B = double.Parse(Tokens[P1 + 1]);
            double R = 0;

            switch (Tokens[P1][0])
            {
                case '^':
                    R = Math.Pow(A, B);
                    break;
                case '*':
                    R = A * B;
                    break;
                case '/':
                    R = A / B;
                    break;
                case '+':
                    R = A + B;
                    break;
                case '-':
                    R = A - B;
                    break;
            }

            Tokens[P1] = R.ToString();
            Tokens.RemoveAt(P1 + 1);
            Tokens.RemoveAt(P1 - 1);
            P1 = GetNextOperator(Tokens);
        }

        if (Tokens.Count == 1)
            return Tokens[0];
        else
            throw new Exception("Unhandled error.");
    }

    static bool FindSubExpression(string Expression, out string Left, out string Middle, out string Right)
    {
        int P2 = Expression.IndexOf(')');
        if (P2 == -1)
        {
            Left = "";
            Middle = "";
            Right = "";
            return false;
        }
        else
        {
            int P1 = RevIndexOf(Expression, '(', P2);
            if (P1 == -1)
                throw new Exception("Unhandled error: unbalanced parentheses.");
            Left = Expression.Substring(0, P1);
            Middle = Expression.Substring(P1 + 1, P2 - P1 - 1);
            Right = Expression.Remove(0, P2 + 1);
            return true;
        }
    }

    static string ParseExpression(string Expression)
    {
        Expression = Expression.Replace(" ", "");

        string Left, Middle, Right;
        while (FindSubExpression(Expression, out Left, out Middle, out Right))
            Expression = Left + ParseSubExpression(Middle) + Right;

        return ParseSubExpression(Expression);
    }
回复 原文
冰雪之触 2024-08-10 19:25:48

Ruby，61 行，包括控制台输入

puts class RHEvaluator
  def setup e
    @x = e
    getsym
    rhEval
  end
  def getsym
    @c = @x[0]
    @x = @x.drop 1
  end
  def flatEval(op, a, b)
    case op
      when ?* then a*b
      when ?/ then a/b
      when ?+ then a+b
      when ?- then a-b
      when ?^ then a**b
    end
  end
  def factor
    t = @c
    getsym
    t = case t
      when ?-     then -factor
      when ?0..?9 then t.to_f - ?0
      when ?(
    t = rhEval
    getsym  # eat )
    t
    end
    t
  end
  def power
    v = factor
    while @c == ?^
      op = @c
      getsym
      v = flatEval op, v, factor
    end
    v
  end
  def multiplier
    v = power
    while @c == ?* or @c == ?/
      op = @c
      getsym
      v = flatEval op, v, power
    end
    v
  end
  def rhEval
    v = multiplier
    while @c == ?+ or @c == ?-
      op = @c
      getsym
      v = flatEval op, v, multiplier
    end
    v
  end
  RHEvaluator     # return an expression from the class def
end.new.setup gets.bytes.to_a

Ruby, 61 lines, includes console input

puts class RHEvaluator
  def setup e
    @x = e
    getsym
    rhEval
  end
  def getsym
    @c = @x[0]
    @x = @x.drop 1
  end
  def flatEval(op, a, b)
    case op
      when ?* then a*b
      when ?/ then a/b
      when ?+ then a+b
      when ?- then a-b
      when ?^ then a**b
    end
  end
  def factor
    t = @c
    getsym
    t = case t
      when ?-     then -factor
      when ?0..?9 then t.to_f - ?0
      when ?(
    t = rhEval
    getsym  # eat )
    t
    end
    t
  end
  def power
    v = factor
    while @c == ?^
      op = @c
      getsym
      v = flatEval op, v, factor
    end
    v
  end
  def multiplier
    v = power
    while @c == ?* or @c == ?/
      op = @c
      getsym
      v = flatEval op, v, power
    end
    v
  end
  def rhEval
    v = multiplier
    while @c == ?+ or @c == ?-
      op = @c
      getsym
      v = flatEval op, v, multiplier
    end
    v
  end
  RHEvaluator     # return an expression from the class def
end.new.setup gets.bytes.to_a
回复 原文
那片花海 2024-08-10 19:25:48

C#，1328 字节

我的第一次尝试。这是一个带有控制台 IO 的完整程序。

using System;using System.Collections.Generic;using System.Linq;
using F3 = System.Func<double, double, double>;using C = System.Char;using D = System.Double;
using I = System.Int32;using S = System.String;using W = System.Action;

class F{public static void Main(){Console.WriteLine(new F().EE(Console.ReadLine()));}
D EE(S s){s="("+s.Replace(" ","")+")";
return V(LT(s.Select((c,i)=>c!='-'||P(s[i-1])<0||s[i-1]==')'?c:'_')).GroupBy(t=>t.Item2).Select(g=>new S(g.Select(t=>t.Item1).ToArray())));}
I P(C c){return (" __^^*/+-()".IndexOf(c)-1)/2;}
D V(IEnumerable<S> s){Func<S,C,I>I=(_,c)=>_.IndexOf(c);
I l=0,n=0;var U=new List<S>();var E=new Stack<D>();var O=new Stack<C>();
Func<D>X=E.Pop;Action<D>Y=E.Push;F3 rpow=(x,y)=>Math.Pow(y,x);F3 rdiv=(x,y)=>y/x;
W[]OA={()=>Y(rpow(X(),X())),()=>Y(X()*X()),()=>Y(rdiv(X(),X())),()=>Y(X()+X()),()=>Y(-X()+X()),()=>Y(-X()),};
O.Push(')');foreach(S k in s.TakeWhile(t=>l>0||n==0)){n++;I a=I("(",k[0])-I(")",k[0]);l+=a;
if(l>1||l==-a)U.Add(k);else{if(U.Count>0)E.Push(V(U));U.Clear();I p = Math.Min(P(k[0]),P('-'));
if(p<0)E.Push(D.Parse(k));else{while(P(O.Peek())<=p)OA[I("^*/+-_",O.Pop())]();O.Push(k[0]);}}}
return X();}
IEnumerable<Tuple<C,I>> LT(IEnumerable<C> s){I i=-1,l=-2;foreach(C c in s){I p=P(c);if(p>=0||p!=l)i++;l=P(c);yield return Tuple.Create(c,i);}}}

这是未打高尔夫球的：

using System;
using System.Collections.Generic;
using System.Linq;

class E
{
    public static void Main()
    {
        Console.WriteLine(EvalEntry(Console.ReadLine()));
    }

    public static double EvalEntry(string s)
    {
        return Eval(Tokenize("(" + s.Replace(" ", "") + ")"));
    }

    const char UnaryMinus = '_';

    static int Precedence(char op)
    {
        // __ and () have special (illogical at first glance) placement as an "optimization" aka hack
        return (" __^^*/+-()".IndexOf(op) - 1) / 2;
    }

    static double Eval(IEnumerable<string> s)
    {
        Func<string, char, int> I = (_, c) => _.IndexOf(c);
        Func<char, int> L = c => I("(", c) - I(")", c);

        // level
        int l = 0;
        // token count
        int n = 0;
        // subeval
        var U = new List<string>();
        // evaluation stack
        var E = new Stack<double>();
        // operation stack
        var O = new Stack<char>();

        Func<double> pop = E.Pop;
        Action<double> push = E.Push;
        Func<double, double, double> rpow = (x, y) => Math.Pow(y, x);
        Func<double, double, double> rdiv = (x, y) => y / x;
        // ^*/+-_
        Action[] operationActions =
                {
                    () => push(rpow(pop(), pop())),
                    () => push(pop()*pop()),
                    () => push(rdiv(pop(),pop())),
                    () => push(pop()+pop()),
                    () => push(-pop()+pop()),
                    () => push(-pop()),
                };

        Func<char, Action> getAction = c => operationActions["^*/+-_".IndexOf(c)];

        // ohhhhh here we have another hack!
        O.Push(')');

        foreach (var k in s.TakeWhile(t => l > 0 || n == 0))
        {
            n++;
            int adjust = L(k[0]);
            l += L(k[0]);
            /* major abuse of input conditioning here to catch the ')' of a subgroup
             *   (level == 1 && adjust == -1) => (level == -adjust)
             */
            if (l > 1 || l == -adjust)
            {
                U.Add(k);
                continue;
            }

            if (U.Count > 0)
            {
                E.Push(Eval(U));
                U.Clear();
            }

            int prec = Math.Min(Precedence(k[0]), Precedence('-'));

            // just push the number if it's a number
            if (prec == -1)
            {
                E.Push(double.Parse(k));
            }
            else
            {
                while (Precedence(O.Peek()) <= prec)
                {
                    // apply op
                    getAction(O.Pop())();
                }

                O.Push(k[0]);
            }
        }

        return E.Pop();
    }

    static IEnumerable<string> Tokenize(string s)
    {
        return
            LocateTokens(PreprocessUnary(s))
            .GroupBy(t => t.Item2)
            .Select(g => new string(g.Select(t => t.Item1).ToArray()));
    }

    // make sure the string doesn't start with -
    static IEnumerable<char> PreprocessUnary(string s)
    {
        return s.Select((c, i) => c != '-' || Precedence(s[i - 1]) < 0 || s[i - 1] == ')' ? c : UnaryMinus);
    }

    static IEnumerable<Tuple<char, int>> LocateTokens(IEnumerable<char> chars)
    {
        int i = -1;
        int lastPrec = -2;
        foreach (char c in chars)
        {
            var prec = Precedence(c);
            if (prec >= 0 || prec != lastPrec)
            {
                i++;
                lastPrec = Precedence(c);
            }

            yield return Tuple.Create(c, i);
        }
    }
}

C#, 1328 bytes

My first try. It's a full program with console IO.

using System;using System.Collections.Generic;using System.Linq;
using F3 = System.Func<double, double, double>;using C = System.Char;using D = System.Double;
using I = System.Int32;using S = System.String;using W = System.Action;

class F{public static void Main(){Console.WriteLine(new F().EE(Console.ReadLine()));}
D EE(S s){s="("+s.Replace(" ","")+")";
return V(LT(s.Select((c,i)=>c!='-'||P(s[i-1])<0||s[i-1]==')'?c:'_')).GroupBy(t=>t.Item2).Select(g=>new S(g.Select(t=>t.Item1).ToArray())));}
I P(C c){return (" __^^*/+-()".IndexOf(c)-1)/2;}
D V(IEnumerable<S> s){Func<S,C,I>I=(_,c)=>_.IndexOf(c);
I l=0,n=0;var U=new List<S>();var E=new Stack<D>();var O=new Stack<C>();
Func<D>X=E.Pop;Action<D>Y=E.Push;F3 rpow=(x,y)=>Math.Pow(y,x);F3 rdiv=(x,y)=>y/x;
W[]OA={()=>Y(rpow(X(),X())),()=>Y(X()*X()),()=>Y(rdiv(X(),X())),()=>Y(X()+X()),()=>Y(-X()+X()),()=>Y(-X()),};
O.Push(')');foreach(S k in s.TakeWhile(t=>l>0||n==0)){n++;I a=I("(",k[0])-I(")",k[0]);l+=a;
if(l>1||l==-a)U.Add(k);else{if(U.Count>0)E.Push(V(U));U.Clear();I p = Math.Min(P(k[0]),P('-'));
if(p<0)E.Push(D.Parse(k));else{while(P(O.Peek())<=p)OA[I("^*/+-_",O.Pop())]();O.Push(k[0]);}}}
return X();}
IEnumerable<Tuple<C,I>> LT(IEnumerable<C> s){I i=-1,l=-2;foreach(C c in s){I p=P(c);if(p>=0||p!=l)i++;l=P(c);yield return Tuple.Create(c,i);}}}

Here it is un-golfified:

using System;
using System.Collections.Generic;
using System.Linq;

class E
{
    public static void Main()
    {
        Console.WriteLine(EvalEntry(Console.ReadLine()));
    }

    public static double EvalEntry(string s)
    {
        return Eval(Tokenize("(" + s.Replace(" ", "") + ")"));
    }

    const char UnaryMinus = '_';

    static int Precedence(char op)
    {
        // __ and () have special (illogical at first glance) placement as an "optimization" aka hack
        return (" __^^*/+-()".IndexOf(op) - 1) / 2;
    }

    static double Eval(IEnumerable<string> s)
    {
        Func<string, char, int> I = (_, c) => _.IndexOf(c);
        Func<char, int> L = c => I("(", c) - I(")", c);

        // level
        int l = 0;
        // token count
        int n = 0;
        // subeval
        var U = new List<string>();
        // evaluation stack
        var E = new Stack<double>();
        // operation stack
        var O = new Stack<char>();

        Func<double> pop = E.Pop;
        Action<double> push = E.Push;
        Func<double, double, double> rpow = (x, y) => Math.Pow(y, x);
        Func<double, double, double> rdiv = (x, y) => y / x;
        // ^*/+-_
        Action[] operationActions =
                {
                    () => push(rpow(pop(), pop())),
                    () => push(pop()*pop()),
                    () => push(rdiv(pop(),pop())),
                    () => push(pop()+pop()),
                    () => push(-pop()+pop()),
                    () => push(-pop()),
                };

        Func<char, Action> getAction = c => operationActions["^*/+-_".IndexOf(c)];

        // ohhhhh here we have another hack!
        O.Push(')');

        foreach (var k in s.TakeWhile(t => l > 0 || n == 0))
        {
            n++;
            int adjust = L(k[0]);
            l += L(k[0]);
            /* major abuse of input conditioning here to catch the ')' of a subgroup
             *   (level == 1 && adjust == -1) => (level == -adjust)
             */
            if (l > 1 || l == -adjust)
            {
                U.Add(k);
                continue;
            }

            if (U.Count > 0)
            {
                E.Push(Eval(U));
                U.Clear();
            }

            int prec = Math.Min(Precedence(k[0]), Precedence('-'));

            // just push the number if it's a number
            if (prec == -1)
            {
                E.Push(double.Parse(k));
            }
            else
            {
                while (Precedence(O.Peek()) <= prec)
                {
                    // apply op
                    getAction(O.Pop())();
                }

                O.Push(k[0]);
            }
        }

        return E.Pop();
    }

    static IEnumerable<string> Tokenize(string s)
    {
        return
            LocateTokens(PreprocessUnary(s))
            .GroupBy(t => t.Item2)
            .Select(g => new string(g.Select(t => t.Item1).ToArray()));
    }

    // make sure the string doesn't start with -
    static IEnumerable<char> PreprocessUnary(string s)
    {
        return s.Select((c, i) => c != '-' || Precedence(s[i - 1]) < 0 || s[i - 1] == ')' ? c : UnaryMinus);
    }

    static IEnumerable<Tuple<char, int>> LocateTokens(IEnumerable<char> chars)
    {
        int i = -1;
        int lastPrec = -2;
        foreach (char c in chars)
        {
            var prec = Precedence(c);
            if (prec >= 0 || prec != lastPrec)
            {
                i++;
                lastPrec = Precedence(c);
            }

            yield return Tuple.Create(c, i);
        }
    }
}
回复 原文
划一舟意中人 2024-08-10 19:25:48

我在 http://www.sumtree.com 上编写了一个 attp，作为教师执行此操作的教育工具。

使用 bison 进行解析，使用 wxwidgets 进行 GUI。

I wrote an attp at http://www.sumtree.com as an educational tool for teachers that does this.

Used bison for the parsing and wxwidgets for the GUI.

回复 原文
~没有更多了~

关于作者

清醇

暂无简介

0 文章
0 评论
24 人气
发私信

相关话题

更多

热门标签

操作系统 程序设计 IT运维 Linux系统管理 JavaScript 服务器应用 solaris C/C++ PHP Shell BSD Vue.js aix Oracle Python HTML 系统管理 HTML5 CSS 前端
更多

推荐作者

游缘惊梦

文章 0 评论 0

小兔几

文章 0 评论 0

Glik

文章 0 评论 0

生生漫

文章 0 评论 0

Luxian

文章 0 评论 0

Champion-Ming

文章 0 评论 0

更多

友情链接

文江博客
    我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站，即表示您同意使用 Cookies 和您的相关数据。
    原文