Code Golf: средство оценки математических выражений (в соответствии с PEMDAS)

Question

Code Golf: средство оценки математических выражений (в соответствии с PEMDAS)

Я призываю вас написать оценщик математических выражений, который учитывает PEMDAS (порядок операций: круглые скобки, возведение в степень, умножение, деление, сложение, вычитание) без использования регулярных выражений, уже существующей "Eval()"-подобной функции, библиотеки синтаксического анализа, так далее.

Я видел одну существовавшую ранее проблему с оценщиком для SO ( здесь), но она специально требовала оценки слева направо.

Образцы входов и выходов:

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

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

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

Я написал оценщик на C#, но хотел бы увидеть, насколько плохо он сравнивается с оценками более умных программистов на их языках.

Связанные с:

Code Golf: оценка математических выражений

Разъяснения:

Давайте сделаем это функцией, которая принимает строковый аргумент и возвращает строковый результат.
Что касается того, почему нет регулярных выражений, ну, это для выравнивания игрового поля. Я думаю, что должен быть отдельный вызов для "самого компактного регулярного выражения".
Использование StrToFloat() допустимо. Под "библиотекой разбора" я имел в виду исключить такие вещи, как парсеры грамматики общего назначения, а также для выравнивания игрового поля.
Поддержка плавает.
Поддержите паретезы, возведение в степень и четыре арифметических оператора.
Дайте умножение и деление равного приоритета.
Дайте сложение и вычитание равного приоритета.
Для простоты вы можете предположить, что все входные данные правильно сформированы.
У меня нет никаких предпочтений относительно того, принимает ли ваша функция такие вещи, как ".1" или "1e3", в качестве допустимых чисел, но принятие их принесет вам очки брауни.;)
Для делений на ноль вы, возможно, могли бы вернуть "NaN" (при условии, что вы хотите реализовать обработку ошибок).

26

parsing math code-golf rosetta-stone

Источник

user63844 06 сен '09 в 03:39

18 ответов

Решение

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

16

Источник

user100902 06 сен '09 в 19:33

J

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

10

Источник

user114916 07 сен '09 в 01:41

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>

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

9

Источник

user19299 06 сен '09 в 06:45

Парсер рекурсивного спуска в 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} ;

8

Источник

user120163 06 сен '09 в 04:58

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

5

Источник

user19299 06 сен '09 в 20:56

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

4

Источник

user19299 06 сен '09 в 08:59

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(), Входная строка является первым параметром, а выходной double - вторым параметром. Точка входа раньше 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 находится в 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;
}

2

Источник

user36388 10 сен '09 в 12:59

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

объяснение

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

2

Источник

user39992 06 сен '09 в 17:39

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

1

Источник

user19299 06 сен '09 в 12:10

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

1

Источник

user46754 13 янв '10 в 13:34

Рубин, теперь 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;
}

1

Источник

user140740 07 сен '09 в 01:41

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

1

Источник

user157259 06 сен '09 в 12:57

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 Paddy) Я смог сократить его на ~90 символов!

Характеристики

Поддерживает возведение в степень, умножение, деление, сложение и вычитание. Обратите внимание, что он НЕ поддерживает унарный минус, так как он не был упомянут в спецификации, даже если он использовался в тестовых примерах OP. Я думал, что это было достаточно двусмысленно, чтобы опустить
Это 249 символов
Поддерживает арифметику двойной точности
Это 249 символов
Поддерживает PEMDAS, хотя экспонента ассоциируется как "x^y^z"->"(x^y)^z", а не как "x^(y^z)"
Предполагается, что ввод не мусор. Мусор на входе, мусор на выходе.
Я упоминал, что это 249 символов в длину?:П

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

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

m(charPtr,0)

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

1

Источник

10 сен '09 в 20:50

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

Здесь это не-Golfified:

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

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

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

    const char UnaryMinus = '_';

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

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

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

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

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

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

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

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

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

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

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

        return E.Pop();
    }

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

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

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

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

0

Источник

user138304 11 сен '09 в 04:12

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

0

Источник

user140740 06 сен '09 в 10:24

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

0

Источник

user63844 06 сен '09 в 06:04

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

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

0

Источник

user53442 07 сен '09 в 10:33

Другие вопросы по тегам parsing math code-golf rosetta-stone

user36388 07 сен '09 в 01:06 2009-09-07 01:06 · Accepted Answer · 2009-09-07 01:06

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

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

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

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

Я бы тогда заменил все экземпляры double "в коде с" D Msgstr "Это добавило бы к коду 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 символ, потребовав, чтобы вызывающая сторона передала указатель на double для возвращаемого значения:

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

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