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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Этот вызов FoldTokens() происходит либо после выполнения операции (^, *, /, + или -), или после обработки части выражения (заключенной в круглые скобки). Подпрограмма FoldTokens() гарантирует, что значение результата имеет правильный тип оператора (4), а затем копирует остальную часть большего выражения подвыражения. Например, когда выражение 2+6*4+1 обрабатывается, EvalTokens() сначала вычисляет 6*4, оставляя результат вместо 6 (2+24*4+1). FoldTokens() затем удаляет остальную часть подвыражения 24*4, оставляя 2+24+1.

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

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

Вот и все. Макросы предназначены только для замены обычных операций, а все остальное - это просто сжатие вышеуказанного.

strager настаивает, чтобы код содержал #include инструкции, так как он не будет работать правильно без надлежащего прямого удаления strtod и pow и функций. Поскольку задача требует только функции, а не полной программы, я считаю, что этого не требуется. Однако форвардные объявления можно добавить с минимальными затратами, добавив следующий код:

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

Затем я бы заменил все экземпляры double в коде на D. Это добавило бы к коду 19 символов, в результате чего общее количество увеличилось бы до 484. С другой стороны, я мог бы также преобразовать свою функцию так, чтобы она возвращала двойное значение вместо строки, как он, который обрезал бы 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;
}

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

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

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>

кстати, общий для парсеров, не обрабатывающих ошибки.

Парсер с рекурсивным спуском в PARLANSE, C-подобном языке с синтаксисом LISP: [70 строк, 1376 символов, не считая отступа на 4, необходимого для SO] РЕДАКТИРОВАТЬ: Правила изменены, кто-то настаивал на числах с плавающей запятой, исправлено. Никаких библиотечных вызовов, кроме преобразования с плавающей запятой, ввода и печати. [сейчас 94 строки, 1825 символов]

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

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

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

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

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

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

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

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

Предполагает правильное выражение, числа с плавающей запятой, по крайней мере, с одной ведущей цифрой, степень необязательна как Enn или E-nnn. Не компилируется и не запускается.

Особенности: определение 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} ;

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

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

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

Объяснение

Разработал собственную методику. Разберитесь сами. знак равно

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

Первая новая строка обязательна, и я посчитал ее как один символ.

Это полностью отличается от другого моего ответа . Это больше функциональный подход. Вместо того, чтобы размечать и повторять цикл несколько раз, он оценивает выражение за один проход, используя рекурсивные вызовы для операторов с более высоким приоритетом, эффективно используя стек вызовов для хранения состояния.

Чтобы удовлетворить незнакомца ^;), на этот раз я включил форвардные объявления 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;
}

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

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

Ruby, сейчас 44 строки

C89, 46 строк

Их можно было забить много. Программа C включает заголовки, которые не являются строго необходимыми, и программу main (), которая не включена в некоторые другие записи. Программа Ruby выполняет ввод-вывод для получения строк, что технически не требуется ...

Я понял, что синтаксическому анализатору рекурсивного спуска не нужны отдельные процедуры для каждого уровня приоритета, хотя это всегда отображается в ссылках. Поэтому я пересмотрел свою предыдущую запись 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;
}

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

Это моя «эталонная реализация» на 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);
    }

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

C #, 1328 байт

Моя первая попытка. Это полноценная программа с консольным вводом-выводом.

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

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

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