Оценка строки простых математических выражений

Вызов

Вот проблема (моего собственного изобретения, хотя я не удивлюсь, если бы оно ранее появилось в Интернете).

Напишите функцию, которая принимает единственный аргумент, представляющий собой строковое представление простого математического выражения, и оценивает его как значение с плавающей запятой. "Простое выражение" может включать в себя любое из следующих: положительные или отрицательные десятичные числа, +, -, *, /, (, ). В выражениях используется (нормальная) инфиксная запись. Операторы должны оцениваться в том порядке, в котором они появляются, то есть не так, как в BODMAS, хотя, конечно, должны соблюдаться квадратные скобки. Функция должна возвращать правильный результат для любого возможного выражения этой формы. Однако функция не должна обрабатывать искаженные выражения (т. Е. С плохим синтаксисом).

Примеры выражений:

1 + 3 / -8                            = -0.5       (No BODMAS)
2*3*4*5+99                            = 219
4 * (9 - 4) / (2 * 6 - 2) + 8         = 10
1 + ((123 * 3 - 69) / 100)            = 4
2.45/8.5*9.27+(5*0.0023)              = 2.68...

правила

Я ожидаю некоторой формы "обмана" / хитрости здесь, поэтому, пожалуйста, позвольте мне предупредить об этом! Обманывая, я имею в виду использование eval или эквивалентную функцию в динамических языках, таких как JavaScript или PHP, или в равной степени компилирование и выполнение кода на лету. (Я думаю, что моя спецификация "no BODMAS" в значительной степени гарантировала это.) Кроме этого, нет никаких ограничений. Я ожидаю несколько решений Regex здесь, но было бы неплохо увидеть больше, чем просто это.

Теперь я в основном заинтересован в решении C#/.NET, но любой другой язык также будет вполне приемлемым (в частности, F# и Python для функциональных / смешанных подходов). Я еще не решил, собираюсь ли я принять самое короткое или самое оригинальное решение (по крайней мере для языка) в качестве ответа, но я бы приветствовал любую форму решения на любом языке, кроме того, что я только что запретил выше!

Мое решение

Я разместил свое решение C# здесь (403 символа). Обновление: мое новое решение значительно превзошло старое с 294 символами с помощью небольшого количества регулярного выражения! Я подозревал, что некоторые языки с легким синтаксисом (особенно с функциональным / динамическим) легко победят его, и это было доказано правильно, но мне было бы любопытно, если бы кто-то смог победить это в C#.

Обновить

Я уже видел несколько очень хитрых решений. Спасибо всем, кто опубликовал один. Хотя я еще не тестировал ни одного из них, я собираюсь доверять людям и предполагать, что они хотя бы работают со всеми приведенными примерами.

Просто для заметки, повторный вход (то есть потокобезопасность) не является обязательным требованием для функции, хотя это и бонус.


Формат

Пожалуйста, опубликуйте все ответы в следующем формате для удобства сравнения:

язык

Количество символов:???

Полностью запутанная функция:

(code here)

Очистить / полуобфусцировать функцию:

(code here)

Любые замечания по алгоритму / умные ярлыки, которые он принимает.


43 ответа

C#

Количество символов: 355

Я взял ответ Нолдорина и изменил его, поэтому отдаю Нолдорину 99% кредита за это. Лучшее, что я мог сделать с использованием алгоритма - 408 символов. См . Ответ Нолдорина для более ясной версии кода.

Изменения сделаны:
Изменить сравнение символов для сравнения с числами.
Удалены некоторые объявления по умолчанию и объединены объявления одного типа.
Переработал некоторые из if ifments.

float q(string x){float v,n;if(!float.TryParse(x,out v)){x+=';';int t=0,l=0,i=0;char o,s='?',p='+';for(;i<x.Length;i++){o=s;if(x[i]!=32){s=x[i];if(char.IsDigit(x[i])|s==46|(s==45&o!=49))s='1';if(s==41)l--;if(s!=o&l==0){if(o==49|o==41){n=q(x.Substring(t,i-t));v=p==43?v+n:p==45?v-n:p==42?v*n:p==47?v/n:v;p=x[i];}t=i;if(s==40)t++;}if(s==40)l++;}}}return v;}

Изменить: сбил его еще немного, с 361 до 355, удалив один из возвращаемых показателей.

Рубин

Количество символов: 302

Semi-затемненный:

def e(l)
  t=0.0;o=nil
  while l!=''
    l.sub!(/^\s+/,'')
    l.sub!(/^(-?\d+|-?\d+\.\d+)/,'')
    t=o ? t.send(o, $1.to_f) : $1.to_f if $~
    l.sub!(/^(\+|-|\*|\/)/,'')
    o=$1 if $~
    l.sub!(/^\(/,'')
    t=o ? t.send(o, e(l)) : e(l) if $~
    l.sub!(/^\)/,'')
    return t if $~
  end
  t
end

Уничтожает исходную строку, а также предполагает, что выражение правильно сформировано (только допустимые символы и соответствующие скобки).

Не запутано:

def evaluate_expression(expression)
  result_so_far = 0.0
  last_operator = nil

  while (expression != '')
    # remove any leading whitespace
    expression.sub!(/^\s+/, '') 

    # extract and remove leading integer or decimal number
    expression.sub!(/^(-?\d+|-?\d+\.\d+)/, '')
    if $~
      # match was successful
      number = $1.to_f
      if last_operator.nil?
        # first number, just store it
        result_so_far = number
      else
        # we have an operator, use it!
        # last_operator is a string matching '+', '-', '*' or '/'
        # just invoke the method of that name on our result_so_far
        # since these operators are just method calls in Ruby
        result_so_far = result_so_far.send(last_operator, number)
       end
    end

    # extract and remove leading operator +-*/
    expression.sub!(/^(\+|-|\*|\/)/, '')
    if $~
      # match was successful
      last_operator = $1
    end

    # extract and remove leading open bracket
    l.sub!(/^\(/, '')
    if $~
      # match successful
      if last_operator.nil?
        # first element in the expression is an open bracket
        # so just evaluate its contents recursively
        result_so_far = evaluate_expression(expression)
      else
        # combine the content of the bracketing with the
        # result so far using the last_operator
        result_so_far.send(last_operator, evaluate_expression(expression))
      end
    end

    # extract and remove leading close bracket
    l.sub!(/^\)/, '')
    if $~
      # match successful
      # this must be the end of a recursive call so
      # return the result so far without consuming the rest
      # of the expression
      return result_so_far
    end
  end
  t
end

Рекурсивный вызов управляется модификацией строки выражения, которая немного неприятна, но, похоже, работает.

Python 3K

(его 3K, потому что / конвертирует результат в число с плавающей запятой)

Количество символов: 808

Очистить (я не могу написать запутанный код в Python XD):

def parse(line):
  ops = {"+": lambda x,y:x+y,
       "-": lambda x,y:x-y,
       "*": lambda x,y:x*y,
       "/": lambda x,y:x/y}
  def tpp(s, t):
    if len(s) > 0 and s[-1] in ops:
      f = ops[s.pop()]
      t = f(s.pop(), t)
    return t
  line = line + " "
  s = []
  t = 0
  m = None
  for c in line:
    if c in "0123456789":
      if not m:
        m = "i"
      if m == "i":
        t = t*10 + ord(c)-ord("0")
      elif m =="d":
        t = t + e*(ord(c)-ord("0"))
        e*=0.1
    elif c == ".":
      m = "d"
      e = 0.1
    elif m:
      t = tpp(s,t)
      s.append(t)
      m = None
      t = 0

    if c in ops or c == "(":
      s.append(c)
    elif c == ")":
      t = s.pop()
      s.pop()
      s.append(tpp(s,t))
      t = 0
  t = s.pop()
  if int(t) == t:
    t = int(t)
  return t

Я не использую какие-либо регулярные выражения, даже разбор чисел производится вручную;-)

Очень просто, сканирует строку, она может быть в 3 различных режимах (m), None, что означает, что нет разбираемого числа, "i", что означает, что он анализирует целочисленную часть, и "d", что означает, что анализирует десятичная часть.

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

Довольно просто и понятно:-)

питон

Количество символов: 492

Мягко запутанная функция (короткие имена переменных, без пробелов вокруг операторов):

def e(s):
    q=[]
    b=1
    v=[]
    for c in s.replace(' ','')+'$':
        if c in '.0123456789' or c in '+-' and b and not v:
            v+=[c]
        else:
            if v:
                q+=[float(''.join(v))]
                v=[]
            while len(q)>=3:
                x,y,z=q[-3:]
                if type(x)==type(z)==float:
                    if y=='+':q[-3:]=[x+z]
                    elif y=='-':q[-3:]=[x-z]
                    elif y=='*':q[-3:]=[x*z]
                    elif y=='/':q[-3:]=[x/z]
                elif (x,z)==('(',')'):q[-3:]=[y]
                else:break
            if c=='$':break
            q+=[c]
            b=c!=')'
    return q[0]

Я думаю, что это относительно легко понять. Это довольно простой, наивный подход. Он ничего не импортирует, не использует регулярные выражения, полностью самодостаточен (одиночная функция, без глобальных переменных, без побочных эффектов) и должен обрабатывать подписанные литералы (положительные или отрицательные). Использование более разумных имен переменных и соблюдение рекомендуемого форматирования Python увеличивает количество символов до 850-900, что в значительной степени связано с использованием четырех пробелов вместо одной вкладки для отступа.

OCaml, используя Camlp4 напрямую:

open Camlp4.PreCast

let expr = Gram.Entry.mk "expr"

EXTEND Gram
  expr:
  [   [ e1 = expr; "+"; e2 = expr -> e1 + e2
      | e1 = expr; "-"; e2 = expr -> e1 - e2 ]
  |   [ e1 = expr; "*"; e2 = expr -> e1 * e2
      | e1 = expr; "/"; e2 = expr -> e1 / e2 ]
  |   [ n = INT -> int_of_string n
      | "("; e = expr; ")" -> e ]   ];
END

let () = Gram.parse expr Loc.ghost (Stream.of_string "1-2+3*4")

OCaml с использованием расширения анализатора потока Camlp4:

open Genlex

let lex = make_lexer ["+"; "-"; "*"; "/"; "("; ")"]

let rec parse_atom = parser
  | [< 'Int n >] -> n
  | [< 'Kwd "("; e=parse_expr; 'Kwd ")" >] -> e
and parse_factor = parser
  | [< e1=parse_atom; stream >] ->
      (parser
         | [< 'Kwd "*"; e2=parse_factor >] -> e1 * e2
         | [< 'Kwd "/"; e2=parse_factor >] -> e1 / e2
         | [< >] -> e1) stream
and parse_expr = parser
  | [< e1=parse_factor; stream >] ->
      (parser
         | [< 'Kwd "+"; e2=parse_expr >] -> e1 + e2
         | [< 'Kwd "-"; e2=parse_expr >] -> e1 - e2
         | [< >] -> e1) stream

let () =
  Printf.printf "%d\n" (parse_expr(lex(Stream.of_string "1 + 2 * (3 + 4)")));;

F#

Количество символов: 461

Вот решение Марка Гравелла (по сути), преобразованное из C# в F#. Количество символов намного лучше, но я решил опубликовать его в любом случае из интереса.

Запутанный код:

let e x=
 let rec f(s:string)=
  let i=s.IndexOf(')')
  if i>0 then
   let j=s.LastIndexOf('(',i)
   f(s.Substring(0,j)+f(s.Substring(j+1,i-j-1))+s.Substring(i+1))
  else
   let o=[|'+';'-';'*';'/'|]
   let i=s.LastIndexOfAny(o)
   let j=s.IndexOfAny(o,max(i-2)0,2)
   let k=if j<0 then i else j
   if k<0 then s else
    let o=s.[k]
    string((if o='+'then(+)else if o='-'then(-)else if o='*'then(*)else(/))(float(f(s.Substring(0,k))))(float(s.Substring(k+1))))
 float(f x)

PowerBASIC

Количество символов: ~ 400

Немного некрасиво, но это работает.:) Я уверен, что регулярное выражение сделало бы его еще меньше.

DEFDBL E,f,i,z,q,a,v,o  
DEFSTR s,c,k,p

FUNCTION E(s)  

    i=LEN(s)  
    DO  
        IF MID$(s,i,1)="("THEN  
            q=INSTR(i,s,")")  
            s=LEFT$(s,i-1)+STR$(E(MID$(s,i+1,q-i-1)))+MID$(s,q+1)  
        END IF  
        i-=1  
    LOOP UNTIL i=0  

    k="+-*/"  
    DIM p(PARSECOUNT(s,ANY k))  
    PARSE s,p(),ANY k  

    a=VAL(p(0))

    FOR i=1TO LEN(s)
        c=MID$(s,i,1)
        q=INSTR(k,c)
        IF q THEN
            z+=1
            IF o=0 THEN o=q ELSE p(z)=c+p(z)
            IF TRIM$(p(z))<>"" THEN
                v=VAL(p(z))
                a=CHOOSE(o,a+v,a-v,a*v,a/v)
                o=0
            END IF
        END IF
    NEXT

    E=a  
END FUNCTION  

C#, 264 символа

Стратегия: первые 2 строки избавляются от скобок по индукции. Затем я разделил на \-?[\d.]+ получить номера и операторов. затем используя агрегат, чтобы уменьшить массив строк до двойного значения.

Переменные объяснения

m - выражение в скобках без вложенных скобок.
d является заполнителем для этого неуклюжего синтаксиса TryParse.
v - аккумулятор для конечного значения
t является текущим токеном.

float E(string s){var d=999f;while(d-->1)s=Regex.Replace(s,@"(([^(]?))",m=>E(m.Groups[1].Value)+"");return Regex.Split(s,@"(-?[\d.]+)").Aggregate(d,(v,t)=>(t=t.Trim()).Length==0?v:!float.TryParse(t,out d)?(s=t)==""?0:v:s=="/"?v/d:s=="-"?v-d:s==""?v*d:v+d);}

    float F(string s) {
        var d=999f;
        while(d-->1)
            s=Regex.Replace(s,@"\(([^\(]*?)\)",m=>F(m.Groups[1].Value)+"");
        return Regex.Split(s, @"(\-?[\d\.]+)")
            .Aggregate(d, (v, t) => 
                (t=t.Trim()).Length == 0 ? v :
                !float.TryParse(t, out d) ? (s=t) == "" ? 0 : v :
                s == "/" ? v / d :
                s == "-" ? v - d :
                s == "*" ? v * d :
                           v + d);
    }

РЕДАКТИРОВАТЬ: бесстыдно украл части из ответа нолдорин, повторно используя s в качестве переменной оператора.

РЕДАКТИРОВАТЬ: 999 вложенных скобок должно быть достаточно для всех.

C++

Чарс: 1670

 // not trying to be terse here
#define DIGIT(c)((c)>='0' && (c) <= '9')
#define WHITE(pc) while(*pc == ' ') pc++
#define LP '('
#define RP ')'

bool SeeNum(const char* &pc, float& fNum){
    WHITE(pc);
    if (!(DIGIT(*pc) || (*pc=='.'&& DIGIT(pc[1])))) return false;
    const char* pc0 = pc;
    while(DIGIT(*pc)) pc++;
    if (*pc == '.'){
        pc++;
        while(DIGIT(*pc)) pc++;
    }
    char buf[200];
    int len = pc - pc0;
    strncpy(buf, pc0, len); buf[len] = 0;
    fNum = atof(buf);
    return true;
}

bool SeeChar(const char* &pc, char c){
    WHITE(pc);
    if (*pc != c) return false;
    pc++;
    return true;
}

void ParsExpr(const char* &pc, float &fNum);

void ParsPrim(const char* &pc, float &fNum){
    if (SeeNum(pc, fNum));
    else if (SeeChar(pc, LP)){
        ParsExpr(pc, fNum);
        if (!SeeChar(pc, RP)) exit(0);
    }
    else exit(0); // you can abort better than this
}

void ParsUnary(const char* &pc, float &fNum){
    if (SeeChar(pc, '-')){
        pc+;
        ParsUnary(pc, fNum);
        fNum = -fNum;
    }
    else {
        ParsPrim(pc, fNum);
    }
}

void ParsExpr(const char* &pc, float &fNum){
    ParsUnary(pc, fNum);
    float f1 = 0;
    while(true){
        if (SeeChar(pc, '+')){
            ParsUnary(pc, f1);
            fNum += f1;
        }
        else if (SeeChar(pc, '-')){
            ParsUnary(pc, f1);
            fNum -= f1;
        }
        else if (SeeChar(pc, '*')){
            ParsUnary(pc, f1);
            fNum *= f1;
        }
        else if (SeeChar(pc, '/')){
            ParsUnary(pc, f1);
            fNum /= f1;
        }
        else break;
    }
}

Это просто LL1 (рекурсивный спуск). Мне нравится делать это таким образом (хотя я использую удвоения), потому что это достаточно быстро, и легко вставлять подпрограммы для обработки уровней приоритета.

Джава

Количество символов: 376

Обновленная версия, теперь с большим? злоупотребление оператором!

Полностью запутанный раствор:

static double e(String t){t="("+t+")";for(String s:new String[]{"+","-","*","/","(",")"})t=t.replace(s," "+s+" ");return f(new Scanner(t));}static double f(Scanner s){s.next();double a,v=s.hasNextDouble()?s.nextDouble():f(s);while(s.hasNext("[^)]")){char o=s.next().charAt(0);a=s.hasNextDouble()?s.nextDouble():f(s);v=o=='+'?v+a:o=='-'?v-a:o=='*'?v*a:v/a;}s.next();return v;}

Очистить / полуобфусцировать функцию:

static double evaluate(String text) {
    text = "(" + text + ")";
    for (String s : new String[] {"+", "-", "*", "/", "(", ")" }) {
        text = text.replace(s, " " + s + " ");
    }
    return innerEval(new Scanner(text));
}

static double innerEval(Scanner s) {
    s.next();
    double arg, val = s.hasNextDouble() ? s.nextDouble() : innerEval(s);
    while (s.hasNext("[^)]")) {
        char op = s.next().charAt(0);
        arg = s.hasNextDouble() ? s.nextDouble() : innerEval(s);
        val =
            op == '+' ? val + arg :
            op == '-' ? val - arg :
            op == '*' ? val * arg :
            val / arg;
    }
    s.next();
    return val;
}

PHP

Количество символов: 170

Полностью запутанная функция:

function a($a,$c='#\(([^()]*)\)#e',$d='a("$1","#^ *-?[\d.]+ *\S *-?[\d.]+ *#e","\$0")'){$e='preg_replace';while($a!=$b=$e($c,$d,$a))$a = $b;return$e('#^(.*)$#e',$d,$a);}

Более четкая функция:

function a($a, $c = '#\(([^()]*)\)#e', $d = 'a("$1", "#^ *-?[\d.]+ *\S *-?[\d.]+ *#e", "\$0")') {
    $e = 'preg_replace';
    while ($a != $b = $e($c, $d, $a)) {
        $a = $b;
    }
    return $e('#^(.*)$#e', $d, $a);
}

тесты:

assert(a('1 + 3 / -8') === '-0.5');
assert(a('2*3*4*5+99') === '219');
assert(a('4 * (9 - 4) / (2 * 6 - 2) + 8') === '10');
assert(a('1 + ((123 * 3 - 69) / 100)') === '4');
assert(a('2.45/8.5*9.27+(5*0.0023)') === '2.68344117647');
assert(a(' 2 * 3 * 4 * 5 + 99 ') === '219');

Я удивлен, что никто не делал это в Lex / Yacc или его эквиваленте.

Казалось бы, это приведет к самому короткому исходному коду, который также будет доступен для чтения / сопровождения.

Perl

Количество символов: 93

Полностью запутанная функция: (93 символа, если объединить эти три строки в одну)

$_="(@ARGV)";s/\s//g;$n=qr/(-?\d+(\.\d+)?)/;
while(s.\($n\)|(?<=\()$n[-+*/]$n.eval$&.e){}
print

Очистить / полуобфусцировать функцию:

$_="(@ARGV)";            # Set the default var to "(" argument ")"
s/\s//g;                 # Strip all spaces from $_
$n=qr/(-?\d+(\.\d+)?)/;  # Compile a regex for "number"

# repeatedly replace the sequence "(" NUM ")" with NUM, or if there aren't
# any of those, replace "(" NUM OP NUM with the result
# of doing an eval on just the NUM OP NUM bit.
while(s{\($n\)|(?<=\()$n[-+*/]$n}{eval$&}e){}

# print $_
print

Я думаю, что это довольно хорошо объяснено в "чистой" версии. Две основные идеи заключаются в том, что вы можете сделать код единообразным, заключив аргумент в круглые скобки в начале (особые случаи стоят символов), и что достаточно, хотя и крайне неэффективно, обрабатывать вещи только рядом с открытой скобкой, заменяя это с его результатом.

Вероятно, проще всего запустить этот код как:

perl -le '$_="(@ARGV)";s/\s//g;$n=qr/(-?\d+(\.\d+)?)/;while(s.\($n\)|(?<=\()$n[-+*/]$n.eval$&.e){}print' '4 * (9 - 4) / (2 * 6 - 2) + 8'
Другие вопросы по тегам