Ответ 1

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 до миллиона, в зависимости от того, как я отформатировал его.

Точка входа E() (для "оценки" ). Первым параметром является входная строка, а второй параметр указывает на выходную строку и должен быть выделен вызывающим абонентом (согласно обычным стандартам C). Он может обрабатывать до 47 токенов, где токен - это либо оператор (один из "+-*/^()" ), либо номер с плавающей запятой. Унарные знаковые операторы не считаются отдельным токеном.

Этот код свободно основан на проекте, который я сделал много лет назад в качестве упражнения. Я достал всю обработку ошибок и пробелы, пропустив и переделав их с помощью техники для гольфа. Ниже приведены 28 строк, с достаточным количеством форматирования, которые я смог написать, но, вероятно, недостаточно, чтобы их прочитать. Вы хотите #include <stdlib.h>, <stdio.h> и <math.h> (или см. Примечание внизу).

Обратитесь к коду для объяснения того, как он работает.

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

Первый шаг - tokenize. Массив удвоений содержит два значения для каждого токена, оператор (P, потому что O выглядит слишком сильно, как ноль) и значение (V). Этот токенизация - это то, что делается в цикле for в E(). Он также имеет дело с любыми унарными операторами + и -, включающими их в константу.

Поле "operator" массива токенов может иметь одно из следующих значений:

0: (
1: )
2: *
3: +
4: значение постоянной с плавающей запятой
5: -
6: ^
7: /
8: конец строки токена

Эта схема была в основном получена Daniel Martin, которая заметила, что последние 3 бита были уникальными в представлении ASCII каждого из операторов в этой проблеме.

Несжатая версия E() будет выглядеть примерно так:

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

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

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

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

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

Поскольку нам гарантирован действительный ввод, единственная причина, по которой синтаксический разбор завершится, будет заключаться в том, что следующий токен является оператором. Если это произойдет, указатель parseEnd будет таким же, как, tokenStart. Мы также должны рассмотреть случай, когда синтаксический анализ завершился успешно, но мы действительно хотели, чтобы оператор был. Это будет происходить для операторов сложения и вычитания, если только оператор знака не будет следовать. Другими словами, учитывая выражение "4-6", мы хотим проанализировать его как {4, -, 6}, а не как {4, -6}. С другой стороны, учитывая "4+-6", мы должны проанализировать его как {4, +, -6}. Решение довольно простое. Если синтаксический анализ не выполняется ИЛИ предыдущий токен был константой или закрывающей скобкой (фактически это подвыражение, которое будет оцениваться константой), то текущий токен является оператором, в противном случае он является константой.

После того, как выполняется токенизация, вычисление и сворачивание выполняются путем вызова M(), который сначала ищет любые согласованные пары круглых скобок и обрабатывает подвыражения, содержащиеся внутри, вызывая себя рекурсивно. Затем он обрабатывает операторы, сначала возведение в степень, затем умножение и деление вместе, и, наконец, сложение и вычитание вместе. Поскольку ожидается корректный ввод (как указано в задаче), он не проверяет оператор сложения явно, так как последний обработчик после всех остальных обрабатывается.

Функция вычисления, не имеющая сжатия для гольфа, будет выглядеть примерно так:

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

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

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

^{Некоторая степень сжатия, вероятно, облегчит чтение этой функции.}

После выполнения операции операнды и оператор складываются из списка токенов K() (вызывается через макрос S). Результат операции оставлен как константа вместо сложенного выражения. Следовательно, конечный результат остается в начале массива токенов, поэтому, когда элемент управления возвращается к E(), он просто печатает это в строке, используя тот факт, что первое значение в array - это поле значения токена.

Этот вызов 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 символов (или 452 без форвардных объявлений strtod и pow, но с макросом D). Можно было бы обрезать еще 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;
}

Я оставлю это читателю, чтобы решить, какая версия подходит.

Ответ 2

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

Забастовкa >

Спасибо 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);}}

Ответ 3

J

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

Ответ 4

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>

кстати, общий для парсеров без ошибок.

Ответ 5

Рекурсивный парсер спуска в PARLANSE, C-подобный langauge с синтаксисом LISP: [70 строк, 1376 символов, не считая отступа-4, необходимых SO] EDIT: изменились правила, кто-то настаивал на числах с плавающей запятой, исправлен. Нет вызовов библиотеки, кроме преобразования float, ввода и печати. [теперь 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. Лямбды - это функции разбора, по одному на грамматическое правило. Функция F вызывается путем записи (F args). Функции 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} ;

Ответ 6

F #, 589 символов

Я сдал в гольф свое предыдущее решение в этом камне:

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

Тесты:

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

Ответ 7

С# (с большим количеством 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
    }
}

Ответ 8

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

Объяснение

Разработал мою собственную технику. Подумайте сами. =]

Ответ 9

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(), которая возвращала строку, как задавал ОП. Но поскольку моя была единственной реализацией 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 reference implementation" находится в С#, я написал также полу-сжатую версию С#:

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

Ответ 10

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

Ответ 11

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(), которая принимает только строку в качестве аргумента. Тем не менее, он все равно возвращает double.

Расширенные

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

Ответ 12

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

Ответ 13

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", а не как "x ^ (y ^ z)"
• Предполагается, что вход не является мусором. Мусор, мусор.
• Я уже упоминал об этом 249 символов?: P

Использование

Передайте указатель на массив символов с нулевым символом, затем 0. Пример:

m(charPtr,0)

Вы должны включить math.h и stdlib.h в исходный файл, из которого вы вызываете функцию. Также обратите внимание, что char * c определяется глобально в начале кода. Поэтому не следует определять какую-либо переменную c с чем-либо, используя это. Если у вас есть способ отрицать вещи, "- [insert expression here]" эквивалентно "(0- [insert expression здесь])", как упорядочен приоритет OP

Ответ 14

Я знаю, я знаю... этот код-гольф кажется закрытым. Тем не менее, я почувствовал желание кодировать этот материал в 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).

Ответ 15

Это моя "эталонная реализация" на С# (несколько громоздкая).

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

Ответ 16

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

Ответ 17

Я написал attp в http://www.sumtree.com в качестве образовательного инструмента для учителей, который это делает.

Используется бизон для синтаксического анализа и wxwidgets для графического интерфейса.

Ответ 18

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