Вычисление строки простых математических выражений [закрыто]
https://stackoverflow.com/questions/928563
-
06-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Вызов
Вот задача (моего собственного изобретения, хотя я не удивлюсь, если она ранее появлялась где-либо в Интернете).
Напишите функцию, которая принимает единственный аргумент, представляющий собой строковое представление простого математического выражения, и вычисляет его как значение с плавающей запятой. "простое выражение" может включать любое из следующего:положительные или отрицательные десятичные числа, +, -, *, /, (, ).Использование выражений (обычное) инфиксная нотация.Операторы должны оцениваться в том порядке, в котором они появляются, т.е. нет как в БОДМЫ, хотя скобки, конечно, должны быть правильно расставлены соблюдены.Функция должна вернуть правильный результат для Любой возможное выражение этой формы.Однако функция не обязана обрабатывать искаженные выражения (т.е.те, что с плохим синтаксисом).
Примеры выражений:
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" в значительной степени гарантировала это, однако.) Помимо этого, нет никаких ограничений.Я ожидаю увидеть здесь несколько решений для регулярных выражений, но было бы неплохо увидеть нечто большее, чем просто это.
Сейчас меня в основном интересует решение на C # / .NET, но любой другой язык тоже был бы вполне приемлем (в частности, F # и Python для функциональных / смешанных подходов).Я еще не решил, приму ли я в качестве ответа самое короткое или остроумное решение (по крайней мере, для языка), но я бы приветствовал любая форма решения на любом языке, за исключением того, что я только что запретил выше!
Мое Решение
Теперь я опубликовал свое решение на C # здесь (403 символа). Обновить: Мое новое решение значительно превзошел старый на 294 символа, с помощью небольшого количества милых регулярных выражений!Я подозревал, что это будет легко превзойдено некоторыми языками с более легким синтаксисом (особенно функциональными / динамическими), и было доказано, что они правы, но мне было бы любопытно, сможет ли кто-нибудь превзойти это в C #.
Обновить
Я уже видел несколько очень хитроумных решений.Спасибо всем, кто опубликовал его.Хотя я еще не тестировал ни один из них, я собираюсь доверять людям и предполагать, что они, по крайней мере, работают со всеми приведенными примерами.
Просто на заметку, повторный вход (т.е.потокобезопасность) - это нет обязательное условие для этой функции, хотя это и бонус.
Формат
Пожалуйста, разместите все ответы в следующем формате для удобства сравнения:
Язык
Количество символов:???
Полностью запутанная функция:
(code here)Четкая /полу затемненная функция:
(code here)Любые заметки об алгоритме / умных ярлыках, которые для этого требуются.
Решение
Perl (без оценки)
Количество символов: 167 106 (смотрите ниже версию со 106 символами)
Полностью запутанная функция:(167 символов, если объединить эти три строки в одну)
sub e{my$_="($_[0])";s/\s//g;$n=q"(-?\d++(\.\d+)?+)";
@a=(sub{$1},1,sub{$3*$6},sub{$3+$6},4,sub{$3-$6},6,sub{$3/$6});
while(s:\($n\)|(?<=\()$n(.)$n:$a[7&ord$5]():e){}$_}
Прозрачная / деобфусцированная версия:
sub e {
my $_ = "($_[0])";
s/\s//g;
$n=q"(-?\d++(\.\d+)?+)"; # a regex for "number", including capturing groups
# q"foo" in perl means the same as 'foo'
# Note the use of ++ and ?+ to tell perl
# "no backtracking"
@a=(sub{$1}, # 0 - no operator found
1, # placeholder
sub{$3*$6}, # 2 - ord('*') = 052
sub{$3+$6}, # 3 - ord('+') = 053
4, # placeholder
sub{$3-$6}, # 5 - ord('-') = 055
6, # placeholder
sub{$3/$6}); # 7 - ord('/') = 057
# The (?<=... bit means "find a NUM WHATEVER NUM sequence that happens
# immediately after a left paren", without including the left
# paren. The while loop repeatedly replaces "(" NUM WHATEVER NUM with
# "(" RESULT and "(" NUM ")" with NUM. The while loop keeps going
# so long as those replacements can be made.
while(s:\($n\)|(?<=\()$n(.)$n:$a[7&ord$5]():e){}
# A perl function returns the value of the last statement
$_
}
Изначально я неправильно прочитал правила, поэтому отправил версию с "eval".Вот версия без этого.
Последнее озарение пришло, когда я понял, что последняя восьмеричная цифра в кодах символов для +, -, /, и * отличается, и это ord(undef) равно 0.Это позволяет мне настроить таблицу отправки @a как массив, и просто вызовите код в нужном месте 7 & ord($3).
Есть очевидное место, где нужно сбрить еще одно изменение характера q"" в '' - но тогда было бы сложнее вырезать и вставить в скорлупу.
Еще короче
Количество символов: 124 106
Внесение изменений с помощью эфемерный принимая во внимание, что теперь он сократился до 124 символов:(соедините две строки в одну)
sub e{$_=$_[0];s/\s//g;$n=q"(-?\d++(\.\d+)?+)";
1while s:\($n\)|$n(.)$n:($1,1,$3*$6,$3+$6,4,$3-$6,6,$6&&$3/$6)[7&ord$5]:e;$_}
Еще короче
Количество символов: 110 106
Приведенное ниже решение ruby подталкивает меня еще дальше, хотя я не могу дотянуться до его 104 символов:
sub e{($_)=@_;$n='( *-?[.\d]++ *)';
s:\($n\)|$n(.)$n:(($1,$2-$4,$4&&$2/$4,$2*$4,$2+$4)x9)[.8*ord$3]:e?e($_):$_}
Я должен был сдаться и использовать ''.Этот рубин send трюк действительно полезен для решения этой проблемы.
Выжимание воды из камня
Количество символов:106
Небольшое искажение, чтобы избежать проверки деления на ноль.
sub e{($_)=@_;$n='( *-?[.\d]++ *)';
s:\($n\)|$n(.)$n:($1,0,$2*$4,$2+$4,0,$2-$4)[7&ord$3]//$2/$4:e?e($_):$_}
Вот тестовый жгут для этой функции:
perl -le 'sub e{($_)=@_;$n='\''( *-?[.\d]++ *)'\'';s:\($n\)|$n(.)$n:($1,0,$2*$4,$2+$4,0,$2-$4)[7&ord$3]//$2/$4:e?e($_):$_}' -e 'print e($_) for @ARGV' '1 + 3' '1 + ((123 * 3 - 69) / 100)' '4 * (9 - 4) / (2 * 6 - 2) + 8' '2*3*4*5+99' '2.45/8.5*9.27+(5*0.0023) ' '1 + 3 / -8'
Другие советы
Ассемблер
427 байт
Запутанный, собранный с помощью превосходного A86 в исполняемый файл .com:
dd 0db9b1f89h, 081bee3h, 0e8af789h, 0d9080080h, 0bdac7674h, 013b40286h
dd 07400463ah, 0ccfe4508h, 08ce9f675h, 02fc8000h, 013b0057eh, 0feaac42ah
dd 0bedf75c9h, 0ba680081h, 04de801h, 04874f73bh, 04474103ch, 0e8e8b60fh
dd 08e8a003fh, 0e880290h, 0de0153h, 08b57e6ebh, 0d902a93eh, 046d891dh
dd 08906c783h, 05f02a93eh, 03cffcee8h, 057197510h, 02a93e8bh, 08b06ef83h
dd 05d9046dh, 02a93e89h, 03bc9d95fh, 0ac0174f7h, 074f73bc3h, 0f3cac24h
dd 0eed9c474h, 0197f0b3ch, 07cc4940fh, 074f73b09h, 0103cac09h, 0a3ce274h
dd 0e40a537eh, 0e0d90274h, 02a3bac3h, 021cd09b4h, 03e8b20cdh, 0ff8102a9h
dd 0ed7502abh, 0474103ch, 0e57d0b3ch, 0be02a3bfh, 014d903a3h, 0800344f6h
dd 02db00574h, 0d9e0d9aah, 0d9029f2eh, 0bb34dfc0h, 08a0009h, 01c75f0a8h
dd 020750fa8h, 0b0f3794bh, 021e9aa30h, 0de607400h, 08802990eh, 0de07df07h
dd 0c392ebc1h, 0e8c0008ah, 0aa300404h, 0f24008ah, 04baa3004h, 02eb0ee79h
dd 03005c6aah, 0c0d90ab1h, 0e9defcd9h, 02a116deh, 0e480e0dfh, 040fc8045h
dd 0ede1274h, 0c0d90299h, 015dffcd9h, 047300580h, 0de75c9feh, 0303d804fh
dd 03d80fa74h, 04f01752eh, 0240145c6h, 0dfff52e9h, 0d9029906h, 0f73b025fh
dd 03caca174h, 07fed740ah, 0df07889ah, 0277d807h, 047d9c1deh, 0990ede02h
dd 025fd902h, 03130e0ebh, 035343332h, 039383736h, 02f2b2d2eh, 02029282ah
dd 0e9000a09h, 07fc9f9c1h, 04500000fh, 0726f7272h
db 024h, 0abh, 02h
Редактировать: Неискаженный источник:
mov [bx],bx
finit
mov si,81h
mov di,si
mov cl,[80h]
or cl,bl
jz ret
l1:
lodsb
mov bp,d1
mov ah,19
l2:
cmp al,[bp]
je l3
inc bp
dec ah
jne l2
jmp exit
l3:
cmp ah,2
jle l4
mov al,19
sub al,ah
stosb
l4:
dec cl
jnz l1
mov si,81h
push done
decode:
l5:
call l7
l50:
cmp si,di
je ret
cmp al,16
je ret
db 0fh, 0b6h, 0e8h ; movzx bp,al
call l7
mov cl,[bp+op-11]
mov byte ptr [sm1],cl
db 0deh
sm1:db ?
jmp l50
open:
push di
mov di,word ptr [s]
fstp dword ptr [di]
mov [di+4],bp
add di,6
mov word ptr [s],di
pop di
call decode
cmp al,16
jne ret
push di
mov di,word ptr [s]
sub di,6
mov bp,[di+4]
fld dword ptr [di]
mov word ptr [s],di
pop di
fxch st(1)
cmp si,di
je ret
lodsb
ret
l7: cmp si,di
je exit
lodsb
cmp al,15
je open
fldz
cmp al,11
jg exit
db 0fh, 94h, 0c4h ; sete ah
jl l10
l9:
cmp si,di
je l12
lodsb
cmp al,16
je ret
l10:
cmp al,10
jle l12i
l12:
or ah,ah
je l13
fchs
l13:
ret
exit:
mov dx,offset res
mov ah,9
int 21h
int 20h
done:
mov di,word ptr [s]
cmp di,(offset s)+2
jne exit
cmp al,16
je ok
cmp al,11
jge exit
ok:
mov di,res
mov si,res+100h
fst dword ptr [si]
test byte ptr [si+3],80h
jz pos
mov al,'-'
stosb
fchs
pos:
fldcw word ptr [cw]
fld st(0)
fbstp [si]
mov bx,9
l1000:
mov al,[si+bx]
test al,0f0h
jne startu
test al,0fh
jne startl
dec bx
jns l1000
mov al,'0'
stosb
jmp frac
l12i:
je l11
fimul word ptr [d3]
mov [bx],al
fild word ptr [bx]
faddp
jmp l9
ret
startu:
mov al,[si+bx]
shr al,4
add al,'0'
stosb
startl:
mov al,[si+bx]
and al,0fh
add al,'0'
stosb
dec bx
jns startu
frac:
mov al,'.'
stosb
mov byte ptr [di],'0'
mov cl,10
fld st(0)
frndint
frac1:
fsubp st(1)
ficom word ptr [zero]
fstsw ax
and ah,045h
cmp ah,040h
je finished
fimul word ptr [d3]
fld st(0)
frndint
fist word ptr [di]
add byte ptr [di],'0'
inc di
dec cl
jnz frac1
finished:
dec di
cmp byte ptr [di],'0'
je finished
cmp byte ptr [di],'.'
jne f2
dec di
f2:
mov byte ptr [di+1],'$'
exit2:
jmp exit
l11:
fild word ptr [d3]
fstp dword ptr [bx+2]
l111:
cmp si,di
je ret
lodsb
cmp al,10
je exit2
jg ret
mov [bx],al
fild word ptr [bx]
fdiv dword ptr [bx+2]
faddp
fld dword ptr [bx+2]
fimul word ptr [d3]
fstp dword ptr [bx+2]
jmp l111
d1: db '0123456789.-+/*()', 32, 9
d3: dw 10
op: db 0e9h, 0c1h, 0f9h, 0c9h
cw: dw 0f7fh
zero: dw 0
res:db 'Error$'
s: dw (offset s)+2
Рубин
Количество символов:103
N='( *-?[\d.]+ *)'
def e x
x.sub!(/\(#{N}\)|#{N}([^.\d])#{N}/){$1or(e$2).send$3,e($4)}?e(x):x.to_f
end
Это настоящий нерекурсивный версия решения Злой Блохи.Вложенные выражения, заключенные в скобки, вычисляются снизу вверх, а не сверху вниз.
Редактировать:Преобразование 'while' в условную рекурсию + tail сохранило несколько символов, поэтому оно больше не является нерекурсивным (хотя рекурсия не является семантически необходимой).
Редактировать:Заимствование идеи Дэниела Мартина об объединении регулярных выражений экономит еще 11 символов!
Редактировать:Эта рекурсия даже полезнее, чем я думал сначала! x.to_f может быть переписан как e(x), если x случается, что он содержит одно число.
Редактировать:Используя 'or" вместо "||' позволяет опустить пару круглых скобок.
Длинная версия:
# Decimal number, as a capturing group, for substitution
# in the main regexp below.
N='( *-?[\d.]+ *)'
# The evaluation function
def e(x)
matched = x.sub!(/\(#{N}\)|#{N}([^\d.])#{N}/) do
# Group 1 is a numeric literal in parentheses. If this is present then
# just return it.
if $1
$1
# Otherwise, $3 is an operator symbol and $2 and $4 are the operands
else
# Recursively call e to parse the operands (we already know from the
# regexp that they are numeric literals, and this is slightly shorter
# than using :to_f)
e($2).send($3, e($4))
# We could have converted $3 to a symbol ($3.to_s) or converted the
# result back to string form, but both are done automatically anyway
end
end
if matched then
# We did one reduction. Now recurse back and look for more.
e(x)
else
# If the string doesn't look like a non-trivial expression, assume it is a
# string representation of a real number and attempt to parse it
x.to_f
end
end
C (VS2005)
Количество символов:1360
Злоупотребление препроцессором и предупреждения для забавной компоновки кода (прокрутите вниз, чтобы увидеть):
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define b main
#define c(a) b(a,0)
#define d -1
#define e -2
#define g break
#define h case
#define hh h
#define hhh h
#define w(i) case i
#define i return
#define j switch
#define k float
#define l realloc
#define m sscanf
#define n int _
#define o char
#define t(u) #u
#define q(r) "%f" t(r) "n"
#define s while
#define v default
#define ex exit
#define W printf
#define x fn()
#define y strcat
#define z strcpy
#define Z strlen
char*p =0 ;k *b (n,o** a){k*f
;j(_){ hh e: i* p==40? (++p,c
(d )) :( f= l( 0,
4) ,m (p ,q (% ),
f,&_), p+=_ ,f ); hh
d:f=c( e);s (1 ){ j(
*p ++ ){ hh 0: hh
41 :i f; hh 43 :*
f+=*c( e) ;g ;h 45:*f= *f-*c(
e);g;h 42 :* f= *f**c( e);g;h
47:*f /=*c (e); g; v: c(0);}
}w(1): if(p&& printf (q (( "\\"))
,* c( d) )) g; hh 0: ex (W
(x )) ;v :p =( p?y: z)(l(p
,Z(1[ a] )+ (p ?Z(p )+
1:1)) ,1 [a ]) ;b (_ -1 ,a
+1 ); g; }i 0;};fn () {n =42,p=
43 ;i "Er" "ro" t( r) "\n";}
Визуальный Basic.NET
Количество символов:9759
Я сам больше играю в котелок.
ПРИМЕЧАНИЕ:вложенные круглые скобки не принимаются во внимание.Тоже непроверенный, но я почти уверен, что это работает.
Imports Microsoft.VisualBasic
Imports System.Text
Imports System.Collections.Generic
Public Class Main
Public Shared Function DoArithmaticFunctionFromStringInput(ByVal MathematicalString As String) As Double
Dim numberList As New List(Of Number)
Dim operationsList As New List(Of IOperatable)
Dim currentNumber As New Number
Dim currentParentheticalStatement As New Parenthetical
Dim isInParentheticalMode As Boolean = False
Dim allCharactersInString() As Char = MathematicalString.ToCharArray
For Each mathChar In allCharactersInString
If mathChar = Number.ZERO_STRING_REPRESENTATION Then
currentNumber.UpdateNumber(mathChar)
ElseIf mathChar = Number.ONE_STRING_REPRESENTATION Then
currentNumber.UpdateNumber(mathChar)
ElseIf mathChar = Number.TWO_STRING_REPRESENTATION Then
currentNumber.UpdateNumber(mathChar)
ElseIf mathChar = Number.THREE_STRING_REPRESENTATION Then
currentNumber.UpdateNumber(mathChar)
ElseIf mathChar = Number.FOUR_STRING_REPRESENTATION Then
currentNumber.UpdateNumber(mathChar)
ElseIf mathChar = Number.FIVE_STRING_REPRESENTATION Then
currentNumber.UpdateNumber(mathChar)
ElseIf mathChar = Number.SIX_STRING_REPRESENTATION Then
currentNumber.UpdateNumber(mathChar)
ElseIf mathChar = Number.SEVEN_STRING_REPRESENTATION Then
currentNumber.UpdateNumber(mathChar)
ElseIf mathChar = Number.EIGHT_STRING_REPRESENTATION Then
currentNumber.UpdateNumber(mathChar)
ElseIf mathChar = Number.NINE_STRING_REPRESENTATION Then
currentNumber.UpdateNumber(mathChar)
ElseIf mathChar = Number.DECIMAL_POINT_STRING_REPRESENTATION Then
currentNumber.UpdateNumber(mathChar)
ElseIf mathChar = Addition.ADDITION_STRING_REPRESENTATION Then
Dim addition As New Addition
If Not isInParentheticalMode Then
operationsList.Add(addition)
numberList.Add(currentNumber)
Else
currentParentheticalStatement.AllNumbers.Add(currentNumber)
currentParentheticalStatement.AllOperators.Add(addition)
End If
currentNumber = New Number
ElseIf mathChar = Number.NEGATIVE_NUMBER_STRING_REPRESENTATION Then
If currentNumber.StringOfNumbers.Length > 0 Then
currentNumber.UpdateNumber(mathChar)
Dim subtraction As New Addition
If Not isInParentheticalMode Then
operationsList.Add(subtraction)
numberList.Add(currentNumber)
Else
currentParentheticalStatement.AllNumbers.Add(currentNumber)
currentParentheticalStatement.AllOperators.Add(subtraction)
End If
currentNumber = New Number
Else
currentNumber.UpdateNumber(mathChar)
End If
ElseIf mathChar = Multiplication.MULTIPLICATION_STRING_REPRESENTATION Then
Dim multiplication As New Multiplication
If Not isInParentheticalMode Then
operationsList.Add(multiplication)
numberList.Add(currentNumber)
Else
currentParentheticalStatement.AllNumbers.Add(currentNumber)
currentParentheticalStatement.AllOperators.Add(multiplication)
End If
currentNumber = New Number
ElseIf mathChar = Division.DIVISION_STRING_REPRESENTATION Then
Dim division As New Division
If Not isInParentheticalMode Then
operationsList.Add(division)
numberList.Add(currentNumber)
Else
currentParentheticalStatement.AllNumbers.Add(currentNumber)
currentParentheticalStatement.AllOperators.Add(division)
End If
currentNumber = New Number
ElseIf mathChar = Parenthetical.LEFT_PARENTHESIS_STRING_REPRESENTATION Then
isInParentheticalMode = True
ElseIf mathChar = Parenthetical.RIGHT_PARENTHESIS_STRING_REPRESENTATION Then
currentNumber = currentParentheticalStatement.EvaluateParentheticalStatement
numberList.Add(currentNumber)
isInParentheticalMode = False
End If
Next
Dim result As Double = 0
Dim operationIndex As Integer = 0
For Each numberOnWhichToPerformOperations As Number In numberList
result = operationsList(operationIndex).PerformOperation(result, numberOnWhichToPerformOperations)
operationIndex = operationIndex + 1
Next
Return result
End Function
Public Class Number
Public Const DECIMAL_POINT_STRING_REPRESENTATION As Char = "."
Public Const NEGATIVE_NUMBER_STRING_REPRESENTATION As Char = "-"
Public Const ZERO_STRING_REPRESENTATION As Char = "0"
Public Const ONE_STRING_REPRESENTATION As Char = "1"
Public Const TWO_STRING_REPRESENTATION As Char = "2"
Public Const THREE_STRING_REPRESENTATION As Char = "3"
Public Const FOUR_STRING_REPRESENTATION As Char = "4"
Public Const FIVE_STRING_REPRESENTATION As Char = "5"
Public Const SIX_STRING_REPRESENTATION As Char = "6"
Public Const SEVEN_STRING_REPRESENTATION As Char = "7"
Public Const EIGHT_STRING_REPRESENTATION As Char = "8"
Public Const NINE_STRING_REPRESENTATION As Char = "9"
Private _isNegative As Boolean
Public ReadOnly Property IsNegative() As Boolean
Get
Return _isNegative
End Get
End Property
Public ReadOnly Property ActualNumber() As Double
Get
Dim result As String = ""
If HasDecimal Then
If DecimalIndex = StringOfNumbers.Length - 1 Then
result = StringOfNumbers.ToString
Else
result = StringOfNumbers.Insert(DecimalIndex, DECIMAL_POINT_STRING_REPRESENTATION).ToString
End If
Else
result = StringOfNumbers.ToString
End If
If IsNegative Then
result = NEGATIVE_NUMBER_STRING_REPRESENTATION & result
End If
Return CType(result, Double)
End Get
End Property
Private _hasDecimal As Boolean
Public ReadOnly Property HasDecimal() As Boolean
Get
Return _hasDecimal
End Get
End Property
Private _decimalIndex As Integer
Public ReadOnly Property DecimalIndex() As Integer
Get
Return _decimalIndex
End Get
End Property
Private _stringOfNumbers As New StringBuilder
Public ReadOnly Property StringOfNumbers() As StringBuilder
Get
Return _stringOfNumbers
End Get
End Property
Public Sub UpdateNumber(ByVal theDigitToAppend As Char)
If IsNumeric(theDigitToAppend) Then
Me._stringOfNumbers.Append(theDigitToAppend)
ElseIf theDigitToAppend = DECIMAL_POINT_STRING_REPRESENTATION Then
Me._hasDecimal = True
Me._decimalIndex = Me._stringOfNumbers.Length
ElseIf theDigitToAppend = NEGATIVE_NUMBER_STRING_REPRESENTATION Then
Me._isNegative = Not Me._isNegative
End If
End Sub
Public Shared Function ConvertDoubleToNumber(ByVal numberThatIsADouble As Double) As Number
Dim numberResult As New Number
For Each character As Char In numberThatIsADouble.ToString.ToCharArray
numberResult.UpdateNumber(character)
Next
Return numberResult
End Function
End Class
Public MustInherit Class Operation
Protected _firstnumber As New Number
Protected _secondnumber As New Number
Public Property FirstNumber() As Number
Get
Return _firstnumber
End Get
Set(ByVal value As Number)
_firstnumber = value
End Set
End Property
Public Property SecondNumber() As Number
Get
Return _secondnumber
End Get
Set(ByVal value As Number)
_secondnumber = value
End Set
End Property
End Class
Public Interface IOperatable
Function PerformOperation(ByVal number1 As Double, ByVal number2 As Number) As Double
End Interface
Public Class Addition
Inherits Operation
Implements IOperatable
Public Const ADDITION_STRING_REPRESENTATION As String = "+"
Public Sub New()
End Sub
Public Function PerformOperation(ByVal number1 As Double, ByVal number2 As Number) As Double Implements IOperatable.PerformOperation
Dim result As Double = 0
result = number1 + number2.ActualNumber
Return result
End Function
End Class
Public Class Multiplication
Inherits Operation
Implements IOperatable
Public Const MULTIPLICATION_STRING_REPRESENTATION As String = "*"
Public Sub New()
End Sub
Public Function PerformOperation(ByVal number1 As Double, ByVal number2 As Number) As Double Implements IOperatable.PerformOperation
Dim result As Double = 0
result = number1 * number2.ActualNumber
Return result
End Function
End Class
Public Class Division
Inherits Operation
Implements IOperatable
Public Const DIVISION_STRING_REPRESENTATION As String = "/"
Public Const DIVIDE_BY_ZERO_ERROR_MESSAGE As String = "I took a lot of time to write this program. Please don't be a child and try to defile it by dividing by zero. Nobody thinks you are funny."
Public Sub New()
End Sub
Public Function PerformOperation(ByVal number1 As Double, ByVal number2 As Number) As Double Implements IOperatable.PerformOperation
If Not number2.ActualNumber = 0 Then
Dim result As Double = 0
result = number1 / number2.ActualNumber
Return result
Else
Dim divideByZeroException As New Exception(DIVIDE_BY_ZERO_ERROR_MESSAGE)
Throw divideByZeroException
End If
End Function
End Class
Public Class Parenthetical
Public Const LEFT_PARENTHESIS_STRING_REPRESENTATION As String = "("
Public Const RIGHT_PARENTHESIS_STRING_REPRESENTATION As String = ")"
Private _allNumbers As New List(Of Number)
Public Property AllNumbers() As List(Of Number)
Get
Return _allNumbers
End Get
Set(ByVal value As List(Of Number))
_allNumbers = value
End Set
End Property
Private _allOperators As New List(Of IOperatable)
Public Property AllOperators() As List(Of IOperatable)
Get
Return _allOperators
End Get
Set(ByVal value As List(Of IOperatable))
_allOperators = value
End Set
End Property
Public Sub New()
End Sub
Public Function EvaluateParentheticalStatement() As Number
Dim result As Double = 0
Dim operationIndex As Integer = 0
For Each numberOnWhichToPerformOperations As Number In AllNumbers
result = AllOperators(operationIndex).PerformOperation(result, numberOnWhichToPerformOperations)
operationIndex = operationIndex + 1
Next
Dim numberToReturn As New Number
numberToReturn = Number.ConvertDoubleToNumber(result)
Return numberToReturn
End Function
End Class
End Class
Хаскелл
Количество символов:182
Никаких попыток поумнеть, просто небольшое сжатие:4 строки, 312 байт.
import Data.Char;import Text.ParserCombinators.Parsec
q=either(error.show)id.runParser t id"".filter(' '/=);t=do
s<-getState;a<-fmap read(many1$oneOf".-"<|>digit)<|>between(char '('>>setState id)(char ')'>>setState s)t
option(s a)$choice(zipWith(\c o->char c>>return(o$s a))"+-*/"[(+),(-),(*),(/)])>>=setState>>t
А теперь, по-настоящему проникнувшись духом гольфа, 3 строки и 182 байта:
q=snd.(`e`id).filter(' '/=)
e s c|[(f,h)]<-readsPrec 0 s=g h(c f);e('(':s)c=g h(c f)where(')':h,f)=e s id
g('+':h)=e h.(+);g('-':h)=e h.(-);g('*':h)=e h.(*);g('/':h)=e h.(/);g h=(,)h
Взорвался:
-- Strip spaces from the input, evaluate with empty accumulator,
-- and output the second field of the result.
q :: String -> Double
q = snd . flip eval id . filter (not . isSpace)
-- eval takes a string and an accumulator, and returns
-- the final value and what’s left unused from the string.
eval :: (Fractional a, Read a) => String -> (a -> a) -> (String, a)
-- If the beginning of the string parses as a number, add it to the accumulator,
-- then try to read an operator and further.
eval str accum | [(num, rest)] <- readsPrec 0 str = oper rest (accum num)
-- If the string starts parentheses, evaluate the inside with a fresh
-- accumulator, and continue after the closing paren.
eval ('(':str) accum = oper rest (accum num) where (')':rest, num) = eval str id
-- oper takes a string and current value, and tries to read an operator
-- to apply to the value. If there is none, it’s okay.
oper :: (Fractional a, Read a) => String -> a -> (String, a)
-- Handle operations by giving eval a pre-seeded accumulator.
oper ('+':str) num = eval str (num +)
oper ('-':str) num = eval str (num -)
oper ('*':str) num = eval str (num *)
oper ('/':str) num = eval str (num /)
-- If there’s no operation parsable, just return.
oper str num = (str, num)
Питон
Количество символов:237
Полностью запутанная функция:
from operator import*
def e(s,l=[]):
if s:l+=list(s.replace(' ','')+')')
a=0;o=add;d=dict(zip(')*+-/',(0,mul,o,sub,div)));p=l.pop
while o:
c=p(0)
if c=='(':c=e(0)
while l[0]not in d:c+=p(0)
a=o(a,float(c));o=d[p(0)]
return a
Четкая /полу затемненная функция:
import operator
def calc(source, stack=[]):
if source:
stack += list(source.replace(' ', '') + ')')
answer = 0
ops = {
')': 0,
'*': operator.mul,
'+': operator.add,
'-': operator.sub,
'/': operator.div,
}
op = operator.add
while op:
cur = stack.pop(0)
if cur == '(':
cur = calc(0)
while stack[0] not in ops:
cur += stack.pop(0)
answer = op(answer, float(cur))
op = ops[stack.pop(0)]
return answer
Fortran 77 (диалект gfortran, теперь с поддержкой g77)
Количество символов: 2059
Запутанная версия:
function e(c)
character*99 c
character b
real f(24)
integer i(24)
nf=0
ni=0
20 nf=kf(0.0,nf,f)
ni=ki(43,ni,i)
30 if (isp(c).eq.1) goto 20
h=fr(c)
31 g=fp(nf,f)
j=ip(ni,i)
select case(j)
case (40)
goto 20
case (42)
d=g*h
case (43)
d=g+h
case (45)
d=g-h
case (47)
d=g/h
end select
50 nf=kf(d,nf,f)
60 j=nop(c)
goto (20, 70, 75, 75, 60, 75, 60, 75) (j-39)
65 e=fp(nf,f)
return
70 h=fp(nf,f)
goto 31
75 ni=ki(j,ni,i)
goto 30
end
function kf(v,n,f)
real f(24)
kf=n+1
f(n+1)=v
return
end
function ki(j,n,i)
integer i(24)
ki=n+1
i(n+1)=j
return
end
function fp(n,f)
real f(24)
fp=f(n)
n=n-1
return
end
function ip(n,i)
integer i(24)
ip=i(n)
n=n-1
return
end
function nop(s)
character*99 s
l=1
do while(s(l:l).eq." ".and.l.lt.99)
l=l+1
enddo
nop=ichar(s(l:l))
s(l:l)=" "
return
end
function isp(s)
character*99 s
isp=0
l=1
do while(s(l:l).eq." ".and.l.lt.99)
l=l+1
enddo
isp=41-ichar(s(l:l))
if (isp.eq.1) s(l:l)=" "
return
end
function fr(s)
character*99 s
m=1
n=1
i=1
do while(i.le.99)
j=ichar(s(i:i))
if (j.eq.32) goto 90
if (j.ge.48.and.j.lt.58) goto 89
if (j.eq.43.or.j.eq.45) goto (89,80) m
if (j.eq.46) goto (83,80) n
80 exit
83 n=2
89 m=2
90 i=i+1
enddo
read(s(1:i-1),*) fr
do 91 j=1,i-1
s(j:j)=" "
91 continue
return
end
Прозрачная версия: (3340 символов со скаффолдом)
program infixeval
character*99 c
do while (.true.)
do 10 i=1,99
c(i:i)=" "
10 continue
read(*,"(A99)") c
f=e(c)
write(*,*)f
enddo
end
function e(c)
character*99 c
character b
real f(24) ! value stack
integer i(24) ! operator stack
nf=0 ! number of items on the value stack
ni=0 ! number of items on the operator stack
20 nf=pushf(0.0,nf,f)
ni=pushi(43,ni,i) ! ichar(+) = 43
D write (*,*) "'",c,"'"
30 if (isp(c).eq.1) goto 20
h=fr(c)
D write (*,*) "'",c,"'"
31 g=fpop(nf,f)
j=ipop(ni,i)
D write(*,*) "Opperate ",g," ",char(j)," ",h
select case(j)
case (40)
goto 20
case (42) ! "*"
d=g*h
case (43) ! "+"
d=g+h
case (45) ! "-"
d=g-h
case (47) ! "*"
d=g/h
end select
50 nf=pushf(d,nf,f)
60 j=nop(c)
D write(*,*) "Got op: ", char(j)
goto (20, 70, 75, 75, 60, 75, 60, 75) (j-39)
65 e=fpop(nf,f)
return
70 h=fpop(nf,f) ! Encountered a "("
goto 31
75 ni=pushi(j,ni,i)
goto 30
end
c push onto a real stack
c OB as kf
function pushf(v,n,f)
real f(24)
pushf=n+1
f(n+1)=v
D write(*,*) "Push ", v
return
end
c push onto a integer stack
c OB as ki
function pushi(j,n,i)
integer i(24)
pushi=n+1
i(n+1)=j
D write(*,*) "Push ", char(j)
return
end
c pop from real stack
c OB as fp
function fpop(n,f)
real f(24)
fpop=f(n)
n=n-1
D write (*,*) "Pop ", fpop
return
end
c pop from integer stack
c OB as ip
function ipop(n,i)
integer i(24)
ipop=i(n)
n=n-1
D write (*,*) "Pop ", char(ipop)
return
end
c Next OPerator: returns the next nonws character, and removes it
c from the string
function nop(s)
character*99 s
l=1
do while(s(l:l).eq." ".and.l.lt.99)
l=l+1
enddo
nop=ichar(s(l:l))
s(l:l)=" "
return
end
c IS an open Paren: return 1 if the next non-ws character is "("
c (also overwrite it with a space. Otherwise return not 1
function isp(s)
character*99 s
isp=0
l=1
do while(s(l:l).eq." ".and.l.lt.99)
l=l+1
enddo
isp=41-ichar(s(l:l))
if (isp.eq.1) s(l:l)=" "
return
end
c Float Read: return the next real number in the string and removes the
c character
function fr(s)
character*99 s
m=1 ! No sign (Minus or plus) so far
n=1 ! No decimal so far
i=1
do while(i.le.99)
j=ichar(s(i:i))
if (j.eq.32) goto 90 ! skip spaces
if (j.ge.48.and.j.lt.58) goto 89
if (j.eq.43.or.j.eq.45) goto (89,80) m
if (j.eq.46) goto (83,80) n
c not part of a number
80 exit
83 n=2
89 m=2
90 i=i+1
enddo
read(s(1:i-1),*) fr
do 91 j=1,i-1
s(j:j)=" "
91 continue
return
end
Примечания Эта отредактированная версия гораздо более злая, чем моя первая попытка.Тот же алгоритм, но теперь встроенный в ужасный клубок gotos.Я отказался от совместных подпрограмм, но теперь использую пару разновидностей вычисляемых ветвей.Вся проверка ошибок и отчеты были удалены, но эта версия автоматически восстановит некоторые классы неожиданных символов во входных данных.Эта версия также компилируется с g77.
Основными ограничениями по-прежнему являются жесткое форматирование fortran, длинные и вездесущие ключевые слова и простые примитивы.
С99
Количество символов:239 (Но смотрите ниже для 209)
сжатая функция:
#define S while(*e==32)++e
#define F float
F strtof();char*e;F v();F g(){S;return*e++-40?strtof(e-1,&e):v();}F v(){F b,a=g();for(;;){S;F o=*e++;if(!o|o==41)return a;b=g();a=o==43?a+b:o==45?a-b:o==42?a*b:a/b;}}F f(char*x){e=x;return v();}
распакованная функция:
float strtof();
char* e;
float v();
float g() {
while (*e == ' ') ++e;
return *e++ != '(' ? strtof(e-1, &e) : v();
}
float v() {
float b, a = g();
for (;;) {
while (*e == ' ') ++e;
float op = *e++;
if (op == 0 || op == ')') return a;
b = g();
a = op == '+' ? a + b : op == '-' ? a - b : op == '*' ? a * b : a / b;
}
}
float eval(char* x) {
e = x;
return v();
}
Функция не является повторным входом.
ПРАВКА от Криса Латца:Я ненавижу попирать чужой кодекс, но вот 209-версия персонажа:
#define S for(;*e==32;e++)
#define X (*e++-40?strtof(e-1,&e):v())
float strtof();char*e;float v(){float o,a=X;for(;;){S;o=*e++;if(!o|o==41)return a;S;a=o-43?o-45?o-42?a/X:a*X:a-X:a+X;}}
#define f(x) (e=x,v())
Читаемый (ну, на самом деле не очень читаемый, но распакованный):
float strtof();
char *e;
float v() {
float o, a = *e++ != '(' ? strtof(e - 1, &e) : v();
for(;;) {
for(; *e == ' '; e++);
o = *e++;
if(o == 0 || o==')') return a;
for(; *e == ' '; e++);
// I have no idea how to properly indent nested conditionals
// and this is far too long to fit on one line.
a = o != '+' ?
o != '-' ?
o != '*' ?
a / (*e++ != '(' ? strtof(e - 1, &e) : v()) :
a * (*e++ != '(' ? strtof(e - 1, &e) : v()) :
a - (*e++ != '(' ? strtof(e - 1, &e) : v()) :
a + (*e++ != '(' ? strtof(e - 1, &e) : v());
}
}
#define f(x) (e = x, v())
Да, f() это макрос, а не функция, но он работает.В читаемой версии часть логики переписана, но не переупорядочена (например o != '+' вместо того, чтобы o - '+'), но в остальном это просто версия другого с отступами (и предварительно обработанная).Я продолжаю пытаться упростить if(!o|o==41)return a; часть в for() цикл, но это никогда не делает его короче.Я все еще верю, что это возможно, но я завязал играть в гольф.Если я еще поработаю над этим вопросом, это будет в язык, который не должен быть назван.
Обычный шепелявый
(SBCL)
Количество символов:251
(defun g(e)(if(numberp e)e(let((m (g (pop e)))(o(loop for x in e by #'cddr collect x))(n(loop for x in (cdr e)by #'cddr collect (g x))))(mapcar(lambda(x y)(setf m(apply x(list m y))))o n)m)))(defun w(e)(g(read-from-string(concatenate'string"("e")"))))
Правильная версия (387 символов):
(defun wrapper (exp) (golf-eval (read-from-string (concatenate 'string "(" exp ")"))))
(defun golf-eval (exp)
(if (numberp exp)
exp
(let ((mem (golf-eval (pop exp)))
(op-list (loop for x in exp by #'cddr collect x))
(num-list (loop for x in (cdr exp) by #'cddr collect (golf-eval x))))
(mapcar (lambda (x y) (setf mem (apply x (list mem y)))) op-list num-list)
mem)))
Входные данные - это форма w(), который принимает один строковый аргумент.Он использует трюк , заключающийся в том , что числа / операнды и операторы находятся в шаблоне N O N O N ...и рекурсивно вычисляет все операнды, и, следовательно, получает вложенность очень дешево.;)
JavaScript (не совместим с IE)
Количество символов:268/260
Полностью запутанная функция:
function e(x){x=x.replace(/ /g,'')+')'
function P(n){return x[0]=='('?(x=x.substr(1),E()):(n=/^[-+]?[\d.]+/(x)[0],x=x.substr(n.length),+n)}function E(a,o,b){a=P()
for(;;){o=x[0]
x=x.substr(1)
if(o==')')return a
b=P()
a=o=='+'?a+b:o=='-'?a-b:o=='*'?a*b:a/b}}return E()}
или, в JavaScript 1.8 (Firefox 3+), вы можете сохранить несколько символов, используя замыкания выражений:
e=function(x,P,E)(x=x.replace(/ /g,'')+')',P=function(n)(x[0]=='('?(x=x.substr(1),E()):(n=/^[-+]?[\d.]+/(x)[0],x=x.substr(n.length),+n)),E=function(a,o,b){a=P()
for(;;){o=x[0]
x=x.substr(1)
if(o==')')return a
b=P()
a=o=='+'?a+b:o=='-'?a-b:o=='*'?a*b:a/b}},E())
Четкая /полу затемненная функция:
function evaluate(x) {
x = x.replace(/ /g, "") + ")";
function primary() {
if (x[0] == '(') {
x = x.substr(1);
return expression();
}
var n = /^[-+]?\d*\.?\d*/.exec(x)[0];
x = x.substr(n.length);
return +n;
}
function expression() {
var a = primary();
for (;;) {
var operator = x[0];
x = x.substr(1);
if (operator == ')') {
return a;
}
var b = primary();
a = (operator == '+') ? a + b :
(operator == '-') ? a - b :
(operator == '*') ? a * b :
a / b;
}
}
return expression();
}
Ни одна из версий не будет работать в IE, потому что они используют подписку в стиле массива на строку.Если вы замените оба вхождения x[0] с x.charAt(0), первый должен работать везде.
Начиная с первой версии, я вырезал еще несколько символов, превратив переменные в параметры функции и заменив другой оператор if условным оператором.
C# с Регулярное Выражение Любви
Количество символов: 384
Полностью запутанный:
float E(string i){i=i.Replace(" ","");Regex b=new Regex(@"\((?>[^()]+|\((?<D>)|\)(?<-D>))*(?(D)(?!))\)");i=b.Replace(i,m=>Eval(m.Value.Substring(1,m.Length-2)).ToString());float r=0;foreach(Match m in Regex.Matches(i,@"(?<=^|\D)-?[\d.]+")){float f=float.Parse(m.Value);if(m.Index==0)r=f;else{char o=i[m.Index-1];if(o=='+')r+=f;if(o=='-')r-=f;if(o=='*')r*=f;if(o=='/')r/=f;}}return r;}
Не-запутанный:
private static float Eval(string input)
{
input = input.Replace(" ", "");
Regex balancedMatcher = new Regex(@"\(
(?>
[^()]+
|
\( (?<Depth>)
|
\) (?<-Depth>)
)*
(?(Depth)(?!))
\)", RegexOptions.IgnorePatternWhitespace);
input = balancedMatcher.Replace(input, m => Eval(m.Value.Substring(1, m.Length - 2)).ToString());
float result = 0;
foreach (Match m in Regex.Matches(input, @"(?<=^|\D)-?[\d.]+"))
{
float floatVal = float.Parse(m.Value);
if (m.Index == 0)
{
result = floatVal;
}
else
{
char op = input[m.Index - 1];
if (op == '+') result += floatVal;
if (op == '-') result -= floatVal;
if (op == '*') result *= floatVal;
if (op == '/') result /= floatVal;
}
}
return result;
}
Использует преимущества регулярного выражения .NET функция балансировки группы.
PHP
Количество символов:284
запутанный:
function f($m){return c($m[1]);}function g($n,$m){$o=$m[0];$m[0]=' ';return$o=='+'?$n+$m:($o=='-'?$n-$m:($o=='*'?$n*$m:$n/$m));}function c($s){while($s!=($t=preg_replace_callback('/\(([^()]*)\)/',f,$s)))$s=$t;preg_match_all('![-+/*].*?[\d.]+!',"+$s",$m);return array_reduce($m[0],g);}
читаемый:
function callback1($m) {return c($m[1]);}
function callback2($n,$m) {
$o=$m[0];
$m[0]=' ';
return $o=='+' ? $n+$m : ($o=='-' ? $n-$m : ($o=='*' ? $n*$m : $n/$m));
}
function c($s){
while ($s != ($t = preg_replace_callback('/\(([^()]*)\)/','callback1',$s))) $s=$t;
preg_match_all('![-+/*].*?[\d.]+!', "+$s", $m);
return array_reduce($m[0], 'callback2');
}
$str = ' 2.45/8.5 * -9.27 + ( 5 * 0.0023 ) ';
var_dump(c($str));
# float(-2.66044117647)
Должен работать с любым допустимым вводом (включая отрицательные числа и произвольные пробелы)
SQL (SQL Server 2008)
Количество символов:4202
Полностью запутанная функция:
WITH Input(id,str)AS(SELECT 1,'1 + 3 / -8'UNION ALL SELECT 2,'2*3*4*5+99'UNION ALL SELECT 3,'4 * (9 - 4)/ (2 * 6 - 2)+ 8'UNION ALL SELECT 4,'1 + ((123 * 3 - 69)/ 100)'UNION ALL SELECT 5,'2.45/8.5*9.27+(5*0.0023)'),Separators(i,ch,str_src,priority)AS(SELECT 1,'-',1,1UNION ALL SELECT 2,'+',1,1UNION ALL SELECT 3,'*',1,1UNION ALL SELECT 4,'/',1,1UNION ALL SELECT 5,'(',0,0UNION ALL SELECT 6,')',0,0),SeparatorsStrSrc(str,i)AS(SELECT CAST('['AS varchar(max)),0UNION ALL SELECT str+ch,SSS.i+1FROM SeparatorsStrSrc SSS INNER JOIN Separators S ON SSS.i=S.i-1WHERE str_src<>0),SeparatorsStr(str)AS(SELECT str+']'FROM SeparatorsStrSrc WHERE i=(SELECT COUNT(*)FROM Separators WHERE str_src<>0)),ExprElementsSrc(id,i,tmp,ele,pre_ch,input_str)AS(SELECT id,1,CAST(LEFT(str,1)AS varchar(max)),CAST(''AS varchar(max)),CAST(' 'AS char(1)),SUBSTRING(str,2,LEN(str))FROM Input UNION ALL SELECT id,CASE ele WHEN''THEN i ELSE i+1 END,CAST(CASE WHEN LEFT(input_str,1)=' 'THEN''WHEN tmp='-'THEN CASE WHEN pre_ch LIKE(SELECT str FROM SeparatorsStr)THEN tmp+LEFT(input_str,1)ELSE LEFT(input_str,1)END WHEN LEFT(input_str,1)IN(SELECT ch FROM Separators)OR tmp IN(SELECT ch FROM Separators)THEN LEFT(input_str,1)ELSE tmp+LEFT(input_str,1)END AS varchar(max)),CAST(CASE WHEN LEFT(input_str,1)=' 'THEN tmp WHEN LEFT(input_str,1)='-'THEN CASE WHEN tmp IN(SELECT ch FROM Separators)THEN tmp ELSE''END WHEN LEFT(input_str,1)IN(SELECT ch FROM Separators)OR tmp IN(SELECT ch FROM Separators)THEN CASE WHEN tmp='-'AND pre_ch LIKE(SELECT str FROM SeparatorsStr)THEN''ELSE tmp END ELSE''END AS varchar(max)),CAST(LEFT(ele,1)AS char(1)),SUBSTRING(input_str,2,LEN(input_str))FROM ExprElementsSrc WHERE input_str<>''OR tmp<>''),ExprElements(id,i,ele)AS(SELECT id,i,ele FROM ExprElementsSrc WHERE ele<>''),Scanner(id,i,val)AS(SELECT id,i,CAST(ele AS varchar(max))FROM ExprElements WHERE ele<>''UNION ALL SELECT id,MAX(i)+1,NULL FROM ExprElements GROUP BY id),Operator(op,priority)AS(SELECT ch,priority FROM Separators WHERE priority<>0),Calc(id,c,i,pop_count,s0,s1,s2,stack,status)AS(SELECT Scanner.id,1,1,0,CAST(scanner.val AS varchar(max)),CAST(NULL AS varchar(max)),CAST(NULL AS varchar(max)),CAST(''AS varchar(max)),CAST('init'AS varchar(max))FROM Scanner WHERE Scanner.i=1UNION ALL SELECT Calc.id,Calc.c+1,Calc.i,3,NULL,NULL,NULL,CASE Calc.s1 WHEN'+'THEN CAST(CAST(Calc.s2 AS real)+CAST(Calc.s0 AS real)AS varchar(max))WHEN'-'THEN CAST(CAST(Calc.s2 AS real)-CAST(Calc.s0 AS real)AS varchar(max))WHEN'*'THEN CAST(CAST(Calc.s2 AS real)*CAST(Calc.s0 AS real)AS varchar(max))WHEN'/'THEN CAST(CAST(Calc.s2 AS real)/CAST(Calc.s0 AS real)AS varchar(max))ELSE NULL END+' '+stack,CAST('calc '+Calc.s1 AS varchar(max))FROM Calc INNER JOIN Scanner NextVal ON Calc.id=NextVal.id AND Calc.i+1=NextVal.i WHERE Calc.pop_count=0AND ISNUMERIC(Calc.s2)=1AND Calc.s1 IN(SELECT op FROM Operator)AND ISNUMERIC(Calc.s0)=1AND(SELECT priority FROM Operator WHERE op=Calc.s1)>=COALESCE((SELECT priority FROM Operator WHERE op=NextVal.val),0)UNION ALL SELECT Calc.id,Calc.c+1,Calc.i,3,NULL,NULL,NULL,s1+' '+stack,CAST('paren'AS varchar(max))FROM Calc WHERE pop_count=0AND s2='('AND ISNUMERIC(s1)=1AND s0=')'UNION ALL SELECT Calc.id,Calc.c+1,Calc.i,Calc.pop_count-1,s1,s2,CASE WHEN LEN(stack)>0THEN SUBSTRING(stack,1,CHARINDEX(' ',stack)-1)ELSE NULL END,CASE WHEN LEN(stack)>0THEN SUBSTRING(stack,CHARINDEX(' ',stack)+1,LEN(stack))ELSE''END,CAST('pop'AS varchar(max))FROM Calc WHERE Calc.pop_count>0UNION ALL SELECT Calc.id,Calc.c+1,Calc.i+1,Calc.pop_count,CAST(NextVal.val AS varchar(max)),s0,s1,coalesce(s2,'')+' '+stack,cast('read'as varchar(max))FROM Calc INNER JOIN Scanner NextVal ON Calc.id=NextVal.id AND Calc.i+1=NextVal.i WHERE NextVal.val IS NOT NULL AND Calc.pop_count=0AND((Calc.s0 IS NULL OR calc.s1 IS NULL OR calc.s2 IS NULL)OR NOT(ISNUMERIC(Calc.s2)=1AND Calc.s1 IN(SELECT op FROM Operator)AND ISNUMERIC(calc.s0)=1AND (SELECT priority FROM Operator WHERE op=Calc.s1)>=COALESCE((SELECT priority FROM Operator WHERE op=NextVal.val),0))AND NOT(s2='('AND ISNUMERIC(s1)=1AND s0=')')))SELECT Calc.id,Input.str,Calc.s0 AS result FROM Calc INNER JOIN Input ON Calc.id=Input.id WHERE Calc.c=(SELECT MAX(c)FROM Calc calc2 WHERE Calc.id=Calc2.id)ORDER BY id
Четкая /полу затемненная функция:
WITH
Input(id, str) AS (
SELECT 1, '1 + 3 / -8'
UNION ALL SELECT 2, '2*3*4*5+99'
UNION ALL SELECT 3, '4 * (9 - 4) / (2 * 6 - 2) + 8'
UNION ALL SELECT 4, '1 + ((123 * 3 - 69) / 100)'
UNION ALL SELECT 5, '2.45/8.5*9.27+(5*0.0023)'
)
, Separators(i, ch, str_src, priority) AS (
SELECT 1, '-', 1, 1
UNION ALL SELECT 2, '+', 1, 1
UNION ALL SELECT 3, '*', 1, 1
UNION ALL SELECT 4, '/', 1, 1
UNION ALL SELECT 5, '(', 0, 0
UNION ALL SELECT 6, ')', 0, 0
)
, SeparatorsStrSrc(str, i) AS (
SELECT CAST('[' AS varchar(max)), 0
UNION ALL
SELECT
str + ch
, SSS.i + 1
FROM
SeparatorsStrSrc SSS
INNER JOIN Separators S ON SSS.i = S.i - 1
WHERE
str_src <> 0
)
, SeparatorsStr(str) AS (
SELECT str + ']' FROM SeparatorsStrSrc
WHERE i = (SELECT COUNT(*) FROM Separators WHERE str_src <> 0)
)
, ExprElementsSrc(id, i, tmp, ele, pre_ch, input_str) AS (
SELECT
id
, 1
, CAST(LEFT(str, 1) AS varchar(max))
, CAST('' AS varchar(max))
, CAST(' ' AS char(1))
, SUBSTRING(str, 2, LEN(str))
FROM
Input
UNION ALL
SELECT
id
, CASE ele
WHEN '' THEN i
ELSE i + 1
END
, CAST(
CASE
WHEN LEFT(input_str, 1) = ' '
THEN ''
WHEN tmp = '-'
THEN CASE
WHEN pre_ch LIKE (SELECT str FROM SeparatorsStr)
THEN tmp + LEFT(input_str, 1)
ELSE LEFT(input_str, 1)
END
WHEN LEFT(input_str, 1) IN (SELECT ch FROM Separators)
OR
tmp IN (SELECT ch FROM Separators)
THEN LEFT(input_str, 1)
ELSE tmp + LEFT(input_str, 1)
END
AS varchar(max))
, CAST(
CASE
WHEN LEFT(input_str, 1) = ' '
THEN tmp
WHEN LEFT(input_str, 1) = '-'
THEN CASE
WHEN tmp IN (SELECT ch FROM Separators)
THEN tmp
ELSE ''
END
WHEN LEFT(input_str, 1) IN (SELECT ch FROM Separators)
OR
tmp IN (SELECT ch FROM Separators)
THEN CASE
WHEN tmp = '-' AND pre_ch LIKE (SELECT str FROM SeparatorsStr)
THEN ''
ELSE tmp
END
ELSE ''
END
AS varchar(max))
, CAST(LEFT(ele, 1) AS char(1))
, SUBSTRING(input_str, 2, LEN(input_str))
FROM
ExprElementsSrc
WHERE
input_str <> ''
OR
tmp <> ''
)
, ExprElements(id, i, ele) AS (
SELECT
id
, i
, ele
FROM
ExprElementsSrc
WHERE
ele <> ''
)
, Scanner(id, i, val) AS (
SELECT
id
, i
, CAST(ele AS varchar(max))
FROM
ExprElements
WHERE
ele <> ''
UNION ALL
SELECT
id
, MAX(i) + 1
, NULL
FROM
ExprElements
GROUP BY
id
)
, Operator(op, priority) AS (
SELECT
ch
, priority
FROM
Separators
WHERE
priority <> 0
)
, Calc(id, c, i, pop_count, s0, s1, s2, stack, status) AS (
SELECT
Scanner.id
, 1
, 1
, 0
, CAST(scanner.val AS varchar(max))
, CAST(NULL AS varchar(max))
, CAST(NULL AS varchar(max))
, CAST('' AS varchar(max))
, CAST('init' AS varchar(max))
FROM
Scanner
WHERE
Scanner.i = 1
UNION ALL
SELECT
Calc.id
, Calc.c + 1
, Calc.i
, 3
, NULL
, NULL
, NULL
, CASE Calc.s1
WHEN '+' THEN CAST(CAST(Calc.s2 AS real) + CAST(Calc.s0 AS real) AS varchar(max))
WHEN '-' THEN CAST(CAST(Calc.s2 AS real) - CAST(Calc.s0 AS real) AS varchar(max))
WHEN '*' THEN CAST(CAST(Calc.s2 AS real) * CAST(Calc.s0 AS real) AS varchar(max))
WHEN '/' THEN CAST(CAST(Calc.s2 AS real) / CAST(Calc.s0 AS real) AS varchar(max))
ELSE NULL
END
+ ' '
+ stack
, CAST('calc ' + Calc.s1 AS varchar(max))
FROM
Calc
INNER JOIN Scanner NextVal ON Calc.id = NextVal.id
AND Calc.i + 1 = NextVal.i
WHERE
Calc.pop_count = 0
AND ISNUMERIC(Calc.s2) = 1
AND Calc.s1 IN (SELECT op FROM Operator)
AND ISNUMERIC(Calc.s0) = 1
AND (SELECT priority FROM Operator WHERE op = Calc.s1)
>= COALESCE((SELECT priority FROM Operator WHERE op = NextVal.val), 0)
UNION ALL
SELECT
Calc.id
, Calc.c + 1
, Calc.i
, 3
, NULL
, NULL
, NULL
, s1 + ' ' + stack
, CAST('paren' AS varchar(max))
FROM
Calc
WHERE
pop_count = 0
AND s2 = '('
AND ISNUMERIC(s1) = 1
AND s0 = ')'
UNION ALL
SELECT
Calc.id
, Calc.c + 1
, Calc.i
, Calc.pop_count - 1
, s1
, s2
, CASE
WHEN LEN(stack) > 0
THEN SUBSTRING(stack, 1, CHARINDEX(' ', stack) - 1)
ELSE NULL
END
, CASE
WHEN LEN(stack) > 0
THEN SUBSTRING(stack, CHARINDEX(' ', stack) + 1, LEN(stack))
ELSE ''
END
, CAST('pop' AS varchar(max))
FROM
Calc
WHERE
Calc.pop_count > 0
UNION ALL
SELECT
Calc.id
, Calc.c + 1
, Calc.i + 1
, Calc.pop_count
, CAST(NextVal.val AS varchar(max))
, s0
, s1
, coalesce(s2, '') + ' ' + stack
, cast('read' as varchar(max))
FROM
Calc
INNER JOIN Scanner NextVal ON Calc.id = NextVal.id
AND Calc.i + 1 = NextVal.i
WHERE
NextVal.val IS NOT NULL
AND Calc.pop_count = 0
AND (
(Calc.s0 IS NULL or calc.s1 is null or calc.s2 is null)
OR
NOT(
ISNUMERIC(Calc.s2) = 1
AND Calc.s1 IN (SELECT op FROM Operator)
AND ISNUMERIC(calc.s0) = 1
AND (SELECT priority FROM Operator WHERE op = Calc.s1)
>= COALESCE((SELECT priority FROM Operator WHERE op = NextVal.val), 0)
)
AND NOT(s2 = '(' AND ISNUMERIC(s1) = 1 AND s0 = ')')
)
)
SELECT
Calc.id
, Input.str
, Calc.s0 AS result
FROM
Calc
INNER JOIN Input ON Calc.id = Input.id
WHERE
Calc.c = (SELECT MAX(c) FROM Calc calc2
WHERE Calc.id = Calc2.id)
ORDER BY
id
Это не самый короткий путь.Но я думаю, что это очень гибко для SQL.Добавлять новые операторы легко.Легко изменить приоритет операторов.
F#
Количество символов:327
ОП искал версию F #, вот она.Можно сделать намного приятнее, так как я злоупотребляю ссылка здесь для сохранения символов.Он обрабатывает большинство вещей, таких как -(1.0), 3 - -3 и даже 0 - .5 и т.д.
let g s=
let c=ref[for x in System.Text.RegularExpressions.Regex.Matches(s,"[0-9.]+|[^\s]")->x.Value]
let rec e v=if (!c).IsEmpty then v else
let h=(!c).Head
c:=(!c).Tail
match h with|"("->e(e 0.0)|")"->v|"+"->e(v+(e 0.0))|"-"->e(v-(e 0.0))|"/"->e(v/(e 0.0))|"*"->e(v*(e 0.0))|x->float x
e(e 0.0)
J
Количество символов:208
После Джефф Мозерпосле этого комментария я понял, что совершенно забыл об этом языке...Я не эксперт, но моя первая попытка прошла довольно успешно.
e=:>@{:@f@;:
f=:''&(4 :0)
'y x'=.x g y
while.($y)*-.')'={.>{.y do.'y x'=.(x,>(-.'/'={.>{.y){('%';y))g}.y end.y;x
)
g=:4 :0
z=.>{.y
if.z='('do.'y z'=.f}.y else.if.z='-'do.z=.'_',>{.}.y end.end.(}.y);":".x,z
)
Это немного раздражает, когда приходится составлять карту x/y и -z в J's x%y и _z.Без этого, возможно, 50% этого кода могло бы исчезнуть.
Python (без импорта чего-либо)
Количество символов:222
Я позаимствовал много трюков из ответа Дейва, но мне удалось срезать еще несколько символов.
def e(s,l=0,n=0,f='+'):
if s:l=[c for c in s+')'if' '!=c]
while f!=')':
p=l.pop;m=p(0)
if m=='(':m=e(0,l)
while l[0]not in'+-*/)':m+=p(0)
m=float(m);n={'+':n+m,'-':n-m,'*':n*m,'/':n/(m or 1)}[f];f=p(0)
return n
Прокомментированная версия:
def evaluate(stringexpr, listexpr=0, n=0, f_operation='+'):
# start out as taking 0 + the expression... (or could use 1 * ;)
# We'll prefer to keep the expression as a list of characters,
# so we can use .pop(0) to eat up the expression as we go.
if stringexpr:
listexpr = [c for c in stringexpr+')' if c!=' ']
# use ')' as sentinel to return the answer
while f_operation != ')':
m_next = listexpr.pop(0)
if m_next == '(':
# lists are passed by reference, so this call will eat the (parexp)
m_next = evaluate(None, listexpr)
else:
# rebuild any upcoming numeric chars into a string
while listexpr[0] not in '+-*/)':
m_next += listexpr.pop(0)
# Update n as the current answer. But never divide by 0.
m = float(m_next)
n = {'+':n+m, '-':n-m, '*':n*m, '/':n/(m or 1)}[f_operation]
# prepare the next operation (known to be one of '+-*/)')
f_operation = listexpr.pop(0)
return n
C#
Количество символов:403
Итак, вот мое решение...Я все еще жду, когда кто-нибудь опубликует что-нибудь на C #, что сможет превзойти это.(Марк Гравелл был близок к этому и, возможно, еще немного повозившись, добьется большего успеха, чем я.)
Полностью запутанная функция:
float e(string x){float v=0;if(float.TryParse(x,out v))return v;x+=';';int t=0;
char o,s='?',p='+';float n=0;int l=0;for(int i=0;i<x.Length;i++){o=s;if(
x[i]!=' '){s=x[i];if(char.IsDigit(x[i])|s=='.'|(s=='-'&o!='1'))s='1';if(s==')')
l--;if(s!=o&l==0){if(o=='1'|o==')'){n=e(x.Substring(t,i-t));if(p=='+')v+=n;
if(p=='-')v-=n;if(p=='*')v*=n;if(p=='/')v/=n;p=x[i];}t=i;if(s=='(')t++;}
if(s=='(')l++;}}return v;}
Полу-запутанная функция:
public static float Eval(string expr)
{
float val = 0;
if (float.TryParse(expr, out val))
return val;
expr += ';';
int tokenStart = 0;
char oldState, state = '?', op = '+';
float num = 0;
int level = 0;
for (int i = 0; i < expr.Length; i++)
{
oldState = state;
if (expr[i] != ' ')
{
state = expr[i];
if (char.IsDigit(expr[i]) || state == '.' ||
(state == '-' && oldState != '1'))
state = '1';
if (state == ')')
level--;
if (state != oldState && level == 0)
{
if (oldState == '1' || oldState == ')')
{
num = Eval(expr.Substring(tokenStart, i - tokenStart));
if (op == '+') val += num;
if (op == '-') val -= num;
if (op == '*') val *= num;
if (op == '/') val /= num;
op = expr[i];
}
tokenStart = i;
if (state == '(')
tokenStart++;
}
if (state == '(')
level++;
}
}
return val;
}
Казалось бы, ничего особо умного здесь не происходит.Однако у функции есть преимущество в том, что она является повторной (т. е.потокобезопасный).
Я также разумно доволен количеством символов, учитывая, что оно написано на C # (я полагаю, допустимые 1.0, 2.0 и 3.0).
А вот и еще один:
Сценарий оболочки (с использованием sed + awk)
Количество символов:295
запутанный:
e(){ a="$1";while echo "$a"|grep -q \(;do eval "`echo "$a"|sed 's/\(.*\)(\([^()]*\))\(.*\)/a="\1\`e \"\2\"\`\3"/'`";done; echo "$a"|sed 's/\([-+*/]\) *\(-\?\) */ \1 \2/g'|awk '{t=$1;for(i=2;i<NF;i+=2){j=$(i+1);if($i=="+") t+=j; else if($i=="-") t-=j; else if($i=="*") t*=j; else t/=j}print t}';}
читаемый
e () {
a="$1"
# Recursively process bracket-expressions
while echo "$a"|grep -q \(; do
eval "`echo "$a"|
sed 's/\(.*\)(\([^()]*\))\(.*\)/a="\1\`e \"\2\"\`\3"/'`"
done
# Compute expression without brackets
echo "$a"|
sed 's/\([-+*/]\) *\(-\?\) */ \1 \2/g'|
awk '{
t=$1;
for(i=2;i<NF;i+=2){
j=$(i+1);
if($i=="+") t+=j;
else if($i=="-") t-=j;
else if($i=="*") t*=j;
else t/=j
}
print t
}'
}
Тест:
str=' 2.45 / 8.5 * 9.27 + ( 5 * 0.0023 ) '
echo "$str"|bc -l
e "$str"
Результат:
2.68344117647058823526
2.68344
MATLAB (версия 7.8.0)
Количество символов:239
Запутанная функция:
function [v,s]=m(s),r=1;while s,s=regexp(s,'( ?)(?(1)-?)[\.\d]+|\S','match');c=s{end};s=[s{1:end-1}];if any(c>47),v=str2num(c);elseif c>41,[l,s]=m(s);v=[l/v l*v l+v l-v];v=v(c=='/*+-');if r,break;end;r=1;elseif c<41,break;end;r=r&c~=41;end
Функция очистки (er):
function [value,str] = math(str)
returnNow = 1;
while str,
str = regexp(str,'( ?)(?(1)-?)[\.\d]+|\S','match');
current = str{end};
str = [str{1:end-1}];
if any(current > 47),
value = str2num(current);
elseif current > 41,
[leftValue,str] = math(str);
value = [leftValue/value leftValue*value ...
leftValue+value leftValue-value];
value = value(current == '/*+-');
if returnNow,
break;
end;
returnNow = 1;
elseif current < 41,
break;
end;
returnNow = returnNow & (c ~= 41);
end
Тест:
>> [math('1 + 3 / -8'); ...
math('2*3*4*5+99'); ...
math('4 * (9 - 4) / (2 * 6 - 2) + 8'); ...
math('1 + ((123 * 3 - 69) / 100)'); ...
math('2.45/8.5*9.27+(5*0.0023)')]
ans =
-0.5000
219.0000
10.0000
4.0000
2.6834
Краткий обзор:Смесь регулярных выражений и рекурсии.Практически лучшее, что я смог сделать на данный момент, без обмана и использования EVAL.
Рубин
Количество символов:170
Запутанный:
def s(x)
while x.sub!(/\(([^\(\)]*?)\)/){s($1)}
x.gsub!('--','')
end
while x.sub!(/(-?[\d.]+)[ ]*([+\-*\/])[ ]*(-?[\d.]+)/){$1.to_f.send($2,$3.to_f)}
end
x.strip.to_f
end
Читаемый:
def s(x)
while x.sub!(/\(([^\(\)]*?)\)/){s($1)}
x.gsub!('--','')
end
while x.sub!(/(-?[\d.]+)[ ]*([+\-*\/])[ ]*(-?[\d.]+)/){$1.to_f.send($2,$3.to_f)}
end
x.strip.to_f
end
[
['1 + 3 / -8', -0.5],
['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.68344117647059],
['(3+7) - (5+2)', 3]
].each do |pair|
a,b = s(String.new(pair[0])),pair[1]
print pair[0].ljust(25), ' = ', b, ' (', a==b, ')'
puts
end
В этом нет никакой реальной путаницы, которую я решил опубликовать заново, поскольку она сильно отличается от моей первой.Я должен был предвидеть это с самого начала.Этот процесс представляет собой очень простой процесс устранения:найдите и преобразуйте самую старшую пару круглых скобок (наиболее вложенную) в число до тех пор, пока больше не будет найдено, затем преобразуйте все существующие числа и операции в результат.И, разрешая операторы в скобках, я удаляю все двойные тире (Float.to_f не знает, что с ними делать).
Таким образом, он поддерживает положительные и отрицательные числа (+3, 3 и -3) и даже отрицаемые подвыражения в круглых скобках только в порядке обработки.Единственной более короткой реализацией является Perl (без eval).
Редактировать: Я все еще гоняюсь за Perl, но на данный момент это второй по величине ответ.Я сократил его, внеся изменения во второе регулярное выражение и изменив обработку строки на деструктивную (заменяет старую строку).Это избавило от необходимости дублировать строку, которая, как я выяснил, была просто новым указателем на строку.И переименование функции в s От решить сохранил несколько символов.
Python с регулярными выражениями
Количество символов:283
Полностью запутанная функция:
import re
from operator import*
def c(e):
O=dict(zip("+-/*()",(add,sub,truediv,mul)))
a=[add,0];s=a
for v,o in re.findall("(-?[.\d]+)|([+-/*()])",e):
if v:s=[float(v)]+s
elif o=="(":s=a+s
elif o!=")":s=[O[o]]+s
if v or o==")":s[:3]=[s[1](s[2],s[0])]
return s[0]
Не запутанный:
import re
from operator import *
def compute(s):
operators = dict(zip("+-/*()", (add, sub, truediv, mul)))
stack = [add, 0]
for val, op in re.findall("(-?[.\d]+)|([+-/*()])", s):
if val:
stack = [float(val)] + stack
elif op == "(":
stack = [add, 0] + stack
elif op != ")":
stack = [operators[op]] + stack
if val or op == ")":
stack[:3] = [stack[1](stack[2], stack[0])]
return stack[0]
Я хотел посмотреть, смогу ли я превзойти другие решения Python, используя регулярные выражения.
Не смог.
Регулярное выражение, которое я использую, создает список пар (val, op), где допустим только один элемент в каждой паре.Остальная часть кода представляет собой довольно стандартный синтаксический анализатор на основе стека с изящным трюком замены 3 верхних ячеек в стеке результатом вычисления с использованием синтаксиса назначения списка Python.Для выполнения этой работы с отрицательными числами требовалось всего два дополнительных символа (-?в регулярном выражении).
Питон
Количество символов:382
Еще одно решение на Python, в значительной степени использующее замену регулярных выражений.При каждом выполнении цикла вычисляются простейшие выражения, и результаты помещаются обратно в строку.
Это неискаженный код, если только вы не считаете, что регулярные выражения должны быть запутанными.
import re
from operator import *
operators = dict(zip("+-/*", (add, sub, truediv, mul)))
def compute(s):
def repl(m):
v1, op, v2 = m.groups()
return str(operators[op](float(v1), float(v2)))
while not re.match("^\d+\.\d+$", s):
s = re.sub("([.\d]+)\s*([+-/*])\s*([.\d]+)", repl, s)
s = re.sub("\(([.\d]+)\)", r"\1", s)
return s
Эта идея пришла мне в голову как раз тогда, когда я ложился спать, и я не мог от нее отказаться, пока не записал ее и не воплотил в жизнь.
C#
Количество символов:396 (обновлено)
(но не проходит тест, который вы добавили с помощью "/ -8", и я не склонен это исправлять...
static float Eval(string s){int i,j;s=s.Trim();while((i=s.IndexOf(')'))>=0){j=s.LastIndexOf('(',i,i);s=s.Substring(0,j++)+Eval(s.Substring(j,i-j))+s.Substring(i+1);}if((i=s.LastIndexOfAny("+-*/".ToCharArray()))<0) return float.Parse(s);var r=float.Parse(s.Substring(i+1));var l=i>0?Eval(s.Substring(0,i)):(float?)null;return s[i]=='+'?(l??0)+r:(s[i]=='-'?(l??0)-r:(s[i]=='/'?(l??1)/r:(l??1)*r));}
От:
static float Eval(string s)
{
int i, j;
s = s.Trim();
while ((i = s.IndexOf(')')) >= 0)
{
j = s.LastIndexOf('(', i, i);
s = s.Substring(0, j++) + Eval(s.Substring(j, i - j)) + s.Substring(i + 1);
}
if ((i = s.LastIndexOfAny("+-*/".ToCharArray())) < 0) return float.Parse(s);
var r = float.Parse(s.Substring(i + 1));
var l = i > 0 ? Eval(s.Substring(0, i)) : (float?)null;
return s[i] == '+'
? (l ?? 0) + r
: (s[i] == '-'
? (l ?? 0) - r
: (s[i] == '/'
? (l ?? 1) / r
: (l ?? 1) * r));
}
Питон
Количество символов:235
Полностью запутанная функция:
def g(a):
i=len(a)
while i:
try:m=g(a[i+1:]);n=g(a[:i]);a=str({'+':n+m,'-':n-m,'*':n*m,'/':n/(m or 1)}[a[i]])
except:i-=1;j=a.rfind('(')+1
if j:k=a.find(')',j);a=a[:j-1]+str(g(a[j:k]))+a[k+1:]
return float(a.replace('--',''))
Полу-запутанный:
def g(a):
i=len(a);
# do the math
while i:
try:
# recursively evaluate left and right
m=g(a[i+1:])
n=g(a[:i])
# try to do the math assuming that a[i] is an operator
a=str({'+':n+m,'-':n-m,'*':n*m,'/':n/(m or 1)}[a[i]])
except:
# failure -> next try
i-=1
j=a.rfind('(')+1
# replace brackets in parallel (this part is executed first)
if j:
k=a.find(')',j)
a=a[:j-1]+str(g(a[j:k]))+a[k+1:]
return float(a.replace('--',''))
FWIW, n + 1-е решение на Python.В явном злоупотреблении try-except я использую метод проб и ошибок.Он должен правильно обрабатывать все случаи, включая такие вещи, как -(8), --8 и g('-(1 - 3)').Это повторный вход.Без поддержки со стороны -- случай, который многие реализации не поддерживают, равен 217 символам (см. предыдущую редакцию).
Спасибо за интересный час в воскресенье и еще 30 минут в понедельник.Благодаря крубо за его приятный диктант.
Рубин
Количество символов: 217 179
Это самое короткое решение ruby на данный момент (одно, сильно основанное на регулярном выражении, дает неправильные ответы, когда строка содержит несколько групп круглых скобок) -- это уже не так.Решения, основанные на регулярных выражениях и подстановке, короче.Этот основан на стеке накопителей и анализирует все выражение слева направо.Он является повторным вводом и не изменяет входную строку.Его можно было бы обвинить в нарушении правил неиспользования eval, как это называется Floatметоды с одинаковыми названиями в качестве их математической мнемоники (+,-,/,*).
Запутанный код (старая версия, измененная ниже):
def f(p);a,o=[0],['+']
p.sub(/-/,'+-').scan(/(?:(-?\d+(?:\.\d+)?)|(.))\s*/).each{|n|
q,w=n;case w;when'(';a<<0;o<<'+';when')';q=a.pop;else;o<<w
end if q.nil?;a[-1]=a[-1].method(o.pop).call(q.to_f) if !q.nil?};a[0];end
Еще больше запутанного кода:
def f(p);a,o=[0],[:+]
p.scan(/(?:(-?\d+(?:\.\d+)?)|(.))\s*/).each{|n|q,w=n;case w
when'(';a<<0;o<<:+;when')';q=a.pop;else;o<<w;end if !q
a<<a.pop.send(o.pop,q.to_f)if q};a[0];end
Чистый код:
def f(p)
accumulators, operands = [0], ['+']
p.gsub(/-/,'+-').scan(/(?:(-?\d+(?:\.\d+)?)|(.))\s*/).each do |n|
number, operand = n
case operand
when '('
accumulators << 0
operands << '+'
when ')'
number = accumulators.pop
operands.pop
else
operands[-1] = operand
end if number.nil?
accumulators[-1] = accumulators.last.method(operands[-1]).call(number.to_f) unless number.nil?
end
accumulators.first
end
Ruby 1.8.7
Количество символов:620
Постарайтесь полегче относиться к моей реализации, я впервые в своей жизни пишу анализатор выражений!Я гарантирую, что это не самое лучшее.
Запутанный:
def solve_expression(e)
t,r,s,c,n=e.chars.to_a,[],'','',''
while(c=t.shift)
n=t[0]
if (s+c).match(/^(-?)[.\d]+$/) || (!n.nil? && n.match(/\d/) && c=='-')
s+=c
elsif (c=='-' && n=='(') || c=='('
m,o,x=c=='-',1,''
while(c=t.shift)
o+=1 if c=='('
o-=1 if c==')'
x+=c unless c==')' && o==0
break if o==0
end
r.push(m ? -solve_expression(x) : solve_expression(x))
s=''
elsif c.match(/[+\-\/*]/)
r.push(c) and s=''
else
r.push(s) if !s.empty?
s=''
end
end
r.push(s) unless s.empty?
i=1
a=r[0].to_f
while i<r.count
b,c=r[i..i+1]
c=c.to_f
case b
when '+': a=a+c
when '-': a=a-c
when '*': a=a*c
when '/': a=a/c
end
i+=2
end
a
end
Читаемый:
def solve_expression(expr)
chars = expr.chars.to_a # characters of the expression
parts = [] # resulting parts
s,c,n = '','','' # current string, character, next character
while(c = chars.shift)
n = chars[0]
if (s + c).match(/^(-?)[.\d]+$/) || (!n.nil? && n.match(/\d/) && c == '-') # only concatenate when it is part of a valid number
s += c
elsif (c == '-' && n == '(') || c == '(' # begin a sub-expression
negate = c == '-'
open = 1
subExpr = ''
while(c = chars.shift)
open += 1 if c == '('
open -= 1 if c == ')'
# if the number of open parenthesis equals 0, we've run to the end of the
# expression. Make a new expression with the new string, and add it to the
# stack.
subExpr += c unless c == ')' && open == 0
break if open == 0
end
parts.push(negate ? -solve_expression(subExpr) : solve_expression(subExpr))
s = ''
elsif c.match(/[+\-\/*]/)
parts.push(c) and s = ''
else
parts.push(s) if !s.empty?
s = ''
end
end
parts.push(s) unless s.empty? # expression exits 1 character too soon.
# now for some solutions!
i = 1
a = parts[0].to_f # left-most value is will become the result
while i < parts.count
b,c = parts[i..i+1]
c = c.to_f
case b
when '+': a = a + c
when '-': a = a - c
when '*': a = a * c
when '/': a = a / c
end
i += 2
end
a
end
Ruby 1.9
(из-за регулярного выражения)
Количество символов:296
def d(s)
while m = s.match(/((?<pg>\((?:\\[()]|[^()]|\g<pg>)*\)))/)
s.sub!(m[:pg], d(m[:pg][1,m[:pg].size-2]))
end
while m = s.match(/(-?\d+(\.\d+)?)\s*([*+\-\/])\s*(-?\d+(\.\d+)?)/)
r=m[1].to_f.send(m[3],m[4].to_f) if %w{+ - * /}.include?m[3]
s.sub!(m[0], r.to_s)
end
s
end
Редактировать:Включает оптимизацию Мартина.
СНОБОЛ4
Количество символов:232
a = pos(0) | '('
n = span('0123456789.')
j = '!+;!-;!*;!/; output = e'
d j '!' len(1) . y = " e a . q n . l '" y "' n . r = q (l " y " r) :s(p)" :s(d)
k = code(j)
e = input
s e ' ' = :s(s)
p e ('(' n . i ')') = i :s(p)f<k>
end
Это полу-обман.Он использует code() (вариант eval) для декомпрессии самого себя, но не для вычисления входного выражения.
Де-запутанная версия, без code:
prefix = pos(0) | '('
num = span('0123456789.')
expr = input
spaces expr ' ' = '' :s(spaces)
paren expr ('(' num . x ')') = x :s(paren)
add expr (prefix . pfx) (num . l) '+' (num . r) = pfx (l + r) :s(paren)
sub expr (prefix . pfx) (num . l) '-' (num . r) = pfx (l - r) :s(paren)
mul expr (prefix . pfx) (num . l) '*' (num . r) = pfx (l * r) :s(paren)
div expr (prefix . pfx) (num . l) '/' (num . r) = pfx (l / r) :s(paren)
output = expr
end
СТРАТЕГИИ:
- Во-первых, удалите все пробелы (
spaces) - По возможности убирайте круглые скобки, окружающие число (
paren) - В противном случае найдите простое выражение, включающее два числа с префиксом
'('или в начале строки - Если ни одно из вышеперечисленных правил не применяется, выражение вычисляется полностью.Теперь, если входные данные были правильно сформированы, у нас должно остаться число.
Пример:
1 + (2 * 3) + 41+(2*3)+4[spaces]1+(6)+4[mul]1+6+4[paren]7+4[add]11[add]
C#
Количество символов:355
Я взял Ответ Нолдорина и модифицировал его, так что отдайте должное Нолдорину на 99%.Лучшее, что я мог сделать с используемым алгоритмом, - это 408 символов.Видишь Ответ Нолдорина для получения более понятной версии кода.
Внесенные изменения:
Измените сравнения символов, чтобы сравнивать с числами.
Удалены некоторые объявления по умолчанию и объединены объявления того же типа.
Переработал некоторые положения if.
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, удалив один из статутов возврата.
