Arithmetic evaluation: Difference between revisions

 

;Requirements:

* The four symbols + - * / must be supported as binary operators with conventional precedence rules.

* Precedence-control parentheses must also be supported.

 

;Note:

* Multiplication/Division (left to right)

* Addition/Subtraction (left to right)

 

;C.f:

* [[Parsing/RPN calculator algorithm]].

* [[Parsing/RPN to infix conversion]].

 

=={{header|Ada}}==

{{works with|ALGOL 68G|Any - tested with release [http://sourceforge.net/projects/algol68/files/algol68g/algol68g-1.18.0/algol68g-1.18.0-9h.tiny.el5.centos.fc11.i386.rpm/download 1.18.0-9h.tiny]}}

{{wont work with|ELLA ALGOL 68|Any (with appropriate job cards) - tested with release [http://sourceforge.net/projects/algol68/files/algol68toc/algol68toc-1.8.8d/algol68toc-1.8-8d.fc9.i386.rpm/download 1.8-8d] - A68RS has not implemented forward declarations}}

MODE FIXED = LONG REAL; # numbers in the format 9,999.999 #

 

index error:

printf(("Stack over flow"))

<pre>

euler's number is about: 2.71828182845899446428546958

</pre>

 

=={{header|AutoHotkey}}==

{{works with|AutoHotkey_L}}

hand coded recursive descent parser

expr : term ( ( PLUS | MINUS ) term )* ;

}

 

{

stringo := string ; store original string

string := "pos= " token.pos "`nvalue= " token.value "`ntype= " token.type

return string

 

=={{header|BBC BASIC}}==

{{works with|BBC BASIC for Windows}}

PRINT "Input = " Expr$

AST$ = FNast(Expr$)

ENDIF

UNTIL FALSE

<pre>

Input = 1 + 2 * (3 + (4 * 5 + 6 * 7 * 8) - 9) / 10

 

=={{header|C++}}==

{{Works with|g++|4.1.2 20061115 (prerelease) (SUSE Linux)}}

 

{{libheader|Boost.Spirit|1.8.4}}

#include <boost/spirit/tree/ast.hpp>

#include <string>

}

}

 

=={{header|Clojure}}==

+ 1, - 1})

 

 

user> (evaluate "1 + 2*(3 - 2*(3 - 2)*((2 - 4)*5 - 22/(7 + 2*(3 - 1)) - 1)) + 1")

 

=={{header|Common Lisp}}==

This implementation can read integers, and produce integral and rational values.

 

(labels ((whitespace-p (char)

(find char #(#\space #\newline #\return #\tab)))

finally (return (parse-integer (coerce digits 'string))))))

(consume-whitespace)

(otherwise

(unless (digit-char-p c)

(unless (or (null token) (integerp token))

(read-char stream))

 

(defun group-parentheses (tokens &optional (delimited nil))

(let ((token (pop tokens)))

(case token

(multiple-value-bind (group remaining-tokens)

(group-parentheses tokens t)

(setf new-tokens (cons group new-tokens)

tokens remaining-tokens)))

(if (not delimited)

(cerror "Ignore it." "Unexpected right parenthesis.")

(loop for token = (tokenize-stream in)

until (null token)

Examples

=={{header|D}}==

After the AST tree is constructed, a visitor pattern is used to display the AST structure and calculate the expression value.

std.exception, std.traits;

 

T[] data;

alias data this;

 

if (data.empty)

static if (discard)

return top;

}

immutable opPrec = [ 0, -9, -9, 1, 1, 2, 2];

 

 

final class XP {

immutable Type type;

immutable string str;

XP LHS, RHS;

 

str = s;

pos = p;

foreach_reverse (immutable t; [EnumMembers!Type[1 .. $]])

if (opChar[t] == s)

}

 

auto rhs = cast(XP)other;

enforce(rhs !is null);

}

 

}

 

int xpHead, xpTail;

 

num.push(x);

}

 

while (xpHead < xpr.length && xpr[xpHead] == ' ')

xpHead++; // Skip spc.

return token;

default: // Should be number.

while (xpTail < xpr.length && xpr[xpTail].isDigit())

xpTail++;

} // End nextToken.

 

bool expectingOP;

xpr = s;

root = null;

opr.push(new XP); // CBkt, prevent evaluate null OP precedence.

XP tokenXP = new XP(token, xpHead);

if (expectingOP) { // Process OP-alike XP.

switch (token) {

case ")":

expectingOP = true;

break;

case "+", "-", "*", "/":

joinXP(opr.pop());

opr.push(tokenXP);

 

while (opr.length > 1) // Join pending Op.

} catch(Exception e) {

writefln("%s\n%s\n%s^", e.msg, xpr, " ".replicate(xpHead));

 

if (num.length != 1) { // Should be one XP left.

root = null;

} else {

}

return this;

// To display AST fancy struct.

void ins(ref char[][] s, in string v, in int p, in int l)

if (l + 1 > s.length)

s.length++;

while (s[l].length < p + v.length + 1)

s[l] ~= " ";

}

 

char[][] Tree;

 

if (a && a.root) {

auto c = new CalcVis;

}

foreach (const t; c.Tree)

writefln("\n%s ==>\n%s = %s", a.xpr, c.resultStr, c.result);

} else

}

 

// Calc. the value, display AST struct and eval order.

ins(Tree, xp.str, xp.pos, level);

level++;

if (xp.type == Type.Num) {

resultStr ~= xp.str;

} else {

resultStr ~= "(";

}

 

immutable exp0 = "1 + 2*(3 - 2*(3 - 2)*((2 - 4)*5" ~

" - 22/(7 + 2*(3 - 1)) - 1)) + 1";

{{out}}

<pre> ........................................................+.

1 + 2*(3 - 2*(3 - 2)*((2 - 4)*5 - 22/(7 + 2*(3 - 1)) - 1)) + 1 ==>

((1+(2*(3-((2*(3-2))*((((2-4)*5)-(22/(7+(2*(3-1)))))-1)))))+1) = 60</pre>

 

=={{header|E}}==

While the task requirements specify not evaluating using the language's built-in eval, they don't say that you have to write your own ''parser''...

 

def LiteralExpr := <elang:evm.makeLiteralExpr>.asType()

def arithEvaluate(expr :String) {

return evalAST(ast)

 

Parentheses are handled by the parser.

 

# value: 3

 

 

? arithEvaluate("(1 + 2 / 2) * (5 + 5)")

 

 

 

{

}

 

{

 

}

 

{

}

{

}

{

}

{

}

{

}

{

}

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

=={{header|F_Sharp|F#}}==

 

<code>AbstractSyntaxTree.fs</code>:

type Expression =

| Minus of Expression * Expression

| Times of Expression * Expression

 

<code>Lexer.fsl</code>:

module Lexer

 

| newline { lexbuf.EndPos <- lexbuf.EndPos.NextLine; token lexbuf }

| eof { EOF }

 

<code>Parser.fsy</code>:

open AbstractSyntaxTree

%}

| Expr TIMES Expr { Times ($1, $3) }

| Expr DIVIDE Expr { Divide ($1, $3) }

 

<code>Program.fs</code>:

open Lexer

open Parser

|> parse

|> eval

 

=={{header|Go}}==

 

See [[Arithmetic Evaluator/Go]]

 

=={{header|Groovy}}==

Solution:

ADD('+', 2),

SUBTRACT('-', 2),

}

return elements[0] instanceof List ? parse(elements[0]) : elements[0]

 

Test:

def ex = parse(it)

print """

try { testParse('1++') } catch (e) { println e }

try { testParse('*1') } catch (e) { println e }

 

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

 

=={{header|Haskell}}==

 

 

 

 

 

 

 

=={{header|Icon}} and {{header|Unicon}}==

* Notice that the code looks remarkably like a typical grammar, rather than being an opaque cryptic solution

* Does not rely on any library to silently solve 1/2 the problem; in fact, this code would probably suit being put into a library almost verbatim

write("Usage: Input expression = Abstract Syntax Tree = Value, ^Z to end.")

repeat {

procedure exponent()

suspend tab(any('eE')) || =("+" | "-" | "") || digits() | ""

 

<pre>#matheval.exe

 

Nevertheless, this task deals only with simple arithmetic, so this kind of precedence is an arguably appropriate choice for this task.

 

 

eval=:monad define

'gerund structure'=:y

coerase tmp

r

example use:

 

You can also display the syntax tree, for example:

┌─────────────────────────────────────────────────────┬───────────────────┐

│┌───┬───────┬───┬───────┬───┬─┬───────┬───┬───────┬─┐│┌───────┬─┬───────┐│

││ │└─────┘│ │└─────┘│ │ │└─────┘│ │└─────┘│ ││ │

│└───┴───────┴───┴───────┴───┴─┴───────┴───┴───────┴─┘│ │

 

 

=={{header|Java}}==

Uses the [[Arithmetic/Rational/Java|BigRational class]] to handle arbitrary-precision numbers (rational numbers since basic arithmetic will result in rational values).

 

 

}

}

}

}

}

}

}

}

 

 

=={{header|JavaScript}}==

Spaces are removed, expressions like <code>5--1</code> are treated as <code>5 - -1</code>

 

s = s.replace(/\s/g,'').replace(/^\+/,'');

var rePara = /\([^\(\)]*\)/;

}

}

 

 

<pre>evalArithmeticExp('2+3') // 5

evalArithmeticExp('2+3/4') // 2.75

evalArithmeticExp('2 * (3 + (4 * 5 + (6 * 7) * 8) - 9) * 10') // 7000

evalArithmeticExp('2*-3--4+-0.25' // -2.25</pre>

 

=={{header|Julia}}==

Julia's homoiconic nature and strong metaprogramming facilities make AST/Expression parsing and creation as accessible and programmatic as other language features

"2 * (3 -1) + 2 * 5"

 

 

julia> eval(parse("2 * (3 + ((5) / (7 - 11)))"))

 

=={{header|Lua}}==

 

 

P, R, C, S, V = lpeg.P, lpeg.R, lpeg.C, lpeg.S, lpeg.V

end

 

 

parse[string_] :=

Module[{e},

evaluate[{"*", a_, b_}] := evaluate[a]*evaluate[b];

evaluate[{"/", a_, b_}] := evaluate[a]/evaluate[b];

 

Example use:

 

<pre>{"+", {"-", 1}, {"*", 2, {"-", 3, {"/", {"*", 4, {"-", 5}}, 6}}}}

35/3</pre>