Оценка строки простых математических выражений
Вызов
Вот проблема (моего собственного изобретения, хотя я не удивлюсь, если бы оно ранее появилось в Интернете).
Напишите функцию, которая принимает единственный аргумент, представляющий собой строковое представление простого математического выражения, и оценивает его как значение с плавающей запятой. "Простое выражение" может включать в себя любое из следующих: положительные или отрицательные десятичные числа, +, -, *, /, (, ). В выражениях используется (нормальная) инфиксная запись. Операторы должны оцениваться в том порядке, в котором они появляются, то есть не так, как в 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'