Arithmetic evaluation: Difference between revisions
Content added Content deleted
m (re-alphabetized solutions) |
(→{{header|Groovy}}: new solution) |
||
Line 1,376: | Line 1,376: | ||
See [[Arithmetic Evaluator/Go]] |
See [[Arithmetic Evaluator/Go]] |
||
=={{header|Groovy}}== |
|||
Solution: |
|||
<lang groovy>enum Op { |
|||
ADD('+', 2), |
|||
SUBTRACT('-', 2), |
|||
MULTIPLY('*', 1), |
|||
DIVIDE('/', 1); |
|||
static { |
|||
ADD.operation = { a, b -> a + b } |
|||
SUBTRACT.operation = { a, b -> a - b } |
|||
MULTIPLY.operation = { a, b -> a * b } |
|||
DIVIDE.operation = { a, b -> a / b } |
|||
} |
|||
final String symbol |
|||
final int precedence |
|||
Closure operation |
|||
private Op(String symbol, int precedence) { |
|||
this.symbol = symbol |
|||
this.precedence = precedence |
|||
} |
|||
String toString() { symbol } |
|||
static Op fromSymbol(String symbol) { |
|||
Op.values().find { it.symbol == symbol } |
|||
} |
|||
} |
|||
interface Expression { |
|||
Number evaluate(); |
|||
} |
|||
class Constant implements Expression { |
|||
Number value |
|||
Constant (Number value) { this.value = value } |
|||
Constant (String str) { |
|||
try { this.value = str as BigInteger } |
|||
catch (e) { this.value = str as BigDecimal } |
|||
} |
|||
Number evaluate() { value } |
|||
String toString() { "${value}" } |
|||
} |
|||
class Term implements Expression { |
|||
Op op |
|||
Expression left, right |
|||
Number evaluate() { op.operation(left.evaluate(), right.evaluate()) } |
|||
String toString() { "(${op} ${left} ${right})" } |
|||
} |
|||
void fail(String msg, Closure cond = {true}) { |
|||
if (cond()) throw new IllegalArgumentException("Cannot parse expression: ${msg}") |
|||
} |
|||
Expression parse(String expr) { |
|||
def tokens = tokenize(expr) |
|||
def elements = preParse(tokens, 0) |
|||
parse(elements) |
|||
} |
|||
List tokenize(String expr) { |
|||
def tokens = [] |
|||
def constStr = "" |
|||
def captureConstant = { i -> |
|||
if (constStr) { |
|||
try { tokens << new Constant(constStr) } |
|||
catch (NumberFormatException e) { fail "Invalid constant '${constStr}' near position ${i}" } |
|||
constStr = '' |
|||
} |
|||
} |
|||
for(def i = 0; i<expr.size(); i++) { |
|||
def c = expr[i] |
|||
def constSign = c in ['+','-'] && constStr.empty && (tokens.empty || tokens[-1] != ')') |
|||
def isConstChar = { it in ['.'] + ('0'..'9') || constSign } |
|||
if (c in ([')'] + Op.values()*.symbol) && !constSign) { captureConstant(i) } |
|||
switch (c) { |
|||
case ~/\s/: break |
|||
case isConstChar: constStr += c; break |
|||
case Op.values()*.symbol: tokens << Op.fromSymbol(c); break |
|||
case ['(',')']: tokens << c; break |
|||
default: fail "Invalid character '${c}' at position ${i+1}" |
|||
} |
|||
} |
|||
captureConstant() |
|||
tokens |
|||
} |
|||
List preParse(List tokens, int depth) { |
|||
def deepness = depth |
|||
def tokenGroups = [] |
|||
for (def i = 0; i < tokens.size(); i++) { |
|||
def token = tokens[i] |
|||
switch (token) { |
|||
case '(': |
|||
fail("'(' too close to end of expression") { i+2 > tokens.size() } |
|||
def subGroup = preParse(tokens[i+1..-1], depth+1) |
|||
tokenGroups << subGroup[0..-2] |
|||
i += subGroup[-1] + 1 |
|||
break |
|||
case ')': |
|||
fail("Unbalanced parens, found extra ')'") { deepness == 0 } |
|||
tokenGroups << i |
|||
return tokenGroups |
|||
default: |
|||
tokenGroups << token |
|||
} |
|||
} |
|||
fail("Unbalanced parens, unclosed groupings at end of expression") { deepness != 0 } |
|||
def n = tokenGroups.size() |
|||
fail("The operand/operator sequence is wrong") { n%2 == 0 } |
|||
(0..<n).each { |
|||
def i = it |
|||
fail("The operand/operator sequence is wrong") { (i%2 == 0) == (tokenGroups[i] instanceof Op) } |
|||
} |
|||
tokenGroups |
|||
} |
|||
Expression parse(List elements) { |
|||
while (elements.size() > 1) { |
|||
def n = elements.size() |
|||
fail ("The operand/operator sequence is wrong") { n%2 == 0 } |
|||
def groupLoc = (0..<n).find { i -> elements[i] instanceof List } |
|||
if (groupLoc != null) { |
|||
elements[groupLoc] = parse(elements[groupLoc]) |
|||
continue |
|||
} |
|||
def opLoc = (0..<n).find { i -> elements[i] instanceof Op && elements[i].precedence == 1 } \ |
|||
?: (0..<n).find { i -> elements[i] instanceof Op && elements[i].precedence == 2 } |
|||
if (opLoc != null) { |
|||
fail ("Operator out of sequence") { opLoc%2 == 0 } |
|||
def term = new Term(left:elements[opLoc-1], op:elements[opLoc], right:elements[opLoc+1]) |
|||
elements[(opLoc-1)..(opLoc+1)] = [term] |
|||
continue |
|||
} |
|||
} |
|||
return elements[0] instanceof List ? parse(elements[0]) : elements[0] |
|||
}</lang> |
|||
Test: |
|||
<lang groovy>def testParse = { |
|||
def ex = parse(it) |
|||
print """ |
|||
Input: ${it} |
|||
AST: ${ex} |
|||
value: ${ex.evaluate()} |
|||
""" |
|||
} |
|||
testParse('1+1+(1+(1+(1+(1+(1+(1+(1+(1+(1+(1+(1+(1+(1+1/15)/14)/13)/12)/11)/10)/9)/8)/7)/6)/5)/4)/3)/2') |
|||
assert (parse('1+1+(1+(1+(1+(1+(1+(1+(1+(1+(1+(1+(1+(1+(1+1/15)/14)/13)/12)/11)/10)/9)/8)/7)/6)/5)/4)/3)/2') |
|||
.evaluate() - Math.E).abs() < 0.0000000000001 |
|||
testParse('1 + 2*(3 - 2*(3 - 2)*((2 - 4)*5 - 22/(7 + 2*(3 - 1)) - 1)) + 1') |
|||
testParse('1 - 5 * 2 / 20 + 1') |
|||
testParse('(1 - 5) * 2 / (20 + 1)') |
|||
testParse('2 * (3 + ((5) / (7 - 11)))') |
|||
testParse('(2 + 3) / (10 - 5)') |
|||
testParse('(1 + 2) * 10 / 100') |
|||
testParse('(1 + 2 / 2) * (5 + 5)') |
|||
testParse('2*-3--4+-.25') |
|||
testParse('2*(-3)-(-4)+(-.25)') |
|||
testParse('((11+15)*15)*2-(3)*4*1') |
|||
testParse('((11+15)*15)* 2 + (3) * -4 *1') |
|||
testParse('(((((1)))))') |
|||
testParse('-35') |
|||
println() |
|||
try { testParse('((11+15)*1') } catch (e) { println e } |
|||
try { testParse('((11+15)*1)))') } catch (e) { println e } |
|||
try { testParse('((11+15)*x)') } catch (e) { println e } |
|||
try { testParse('+++++') } catch (e) { println e } |
|||
try { testParse('1 /') } catch (e) { println e } |
|||
try { testParse('*1') } catch (e) { println e } |
|||
try { testParse('/ 1 /') } catch (e) { println e }</lang> |
|||
Output: |
|||
<pre style="height:30ex;overflow:scroll;">Input: 1+1+(1+(1+(1+(1+(1+(1+(1+(1+(1+(1+(1+(1+(1+1/15)/14)/13)/12)/11)/10)/9)/8)/7)/6)/5)/4)/3)/2 |
|||
AST: (+ (+ 1 1) (/ (+ 1 (/ (+ 1 (/ (+ 1 (/ (+ 1 (/ (+ 1 (/ (+ 1 (/ (+ 1 (/ (+ 1 (/ (+ 1 (/ (+ 1 (/ (+ 1 (/ (+ 1 (/ (+ 1 (/ 1 15)) 14)) 13)) 12)) 11)) 10)) 9)) 8)) 7)) 6)) 5)) 4)) 3)) 2)) |
|||
value: 2.7182818284589946 |
|||
Input: 1 + 2*(3 - 2*(3 - 2)*((2 - 4)*5 - 22/(7 + 2*(3 - 1)) - 1)) + 1 |
|||
AST: (+ (+ 1 (* 2 (- 3 (* (* 2 (- 3 2)) (- (- (* (- 2 4) 5) (/ 22 (+ 7 (* 2 (- 3 1))))) 1))))) 1) |
|||
value: 60 |
|||
Input: 1 - 5 * 2 / 20 + 1 |
|||
AST: (+ (- 1 (/ (* 5 2) 20)) 1) |
|||
value: 1.5 |
|||
Input: (1 - 5) * 2 / (20 + 1) |
|||
AST: (/ (* (- 1 5) 2) (+ 20 1)) |
|||
value: -0.3809523810 |
|||
Input: 2 * (3 + ((5) / (7 - 11))) |
|||
AST: (* 2 (+ 3 (/ 5 (- 7 11)))) |
|||
value: 3.50 |
|||
Input: (2 + 3) / (10 - 5) |
|||
AST: (/ (+ 2 3) (- 10 5)) |
|||
value: 1 |
|||
Input: (1 + 2) * 10 / 100 |
|||
AST: (/ (* (+ 1 2) 10) 100) |
|||
value: 0.3 |
|||
Input: (1 + 2 / 2) * (5 + 5) |
|||
AST: (* (+ 1 (/ 2 2)) (+ 5 5)) |
|||
value: 20 |
|||
Input: 2*-3--4+-.25 |
|||
AST: (+ (- (* 2 -3) -4) -0.25) |
|||
value: -2.25 |
|||
Input: 2*(-3)-(-4)+(-.25) |
|||
AST: (+ (- (* 2 -3) -4) -0.25) |
|||
value: -2.25 |
|||
Input: ((11+15)*15)*2-(3)*4*1 |
|||
AST: (- (* (* (+ 11 15) 15) 2) (* (* 3 4) 1)) |
|||
value: 768 |
|||
Input: ((11+15)*15)* 2 + (3) * -4 *1 |
|||
AST: (+ (* (* (+ 11 15) 15) 2) (* (* 3 -4) 1)) |
|||
value: 768 |
|||
Input: (((((1))))) |
|||
AST: 1 |
|||
value: 1 |
|||
Input: -35 |
|||
AST: -35 |
|||
value: -35 |
|||
java.lang.IllegalArgumentException: Cannot parse expression: Unbalanced parens, unclosed groupings at end of expression |
|||
java.lang.IllegalArgumentException: Cannot parse expression: Unbalanced parens, found extra ')' |
|||
java.lang.IllegalArgumentException: Cannot parse expression: Invalid character 'x' at position 10 |
|||
java.lang.IllegalArgumentException: Cannot parse expression: Invalid constant '+' near position 1 |
|||
java.lang.IllegalArgumentException: Cannot parse expression: The operand/operator sequence is wrong |
|||
java.lang.IllegalArgumentException: Cannot parse expression: The operand/operator sequence is wrong |
|||
java.lang.IllegalArgumentException: Cannot parse expression: The operand/operator sequence is wrong</pre> |
|||
=={{header|Haskell}}== |
=={{header|Haskell}}== |