Arithmetic evaluation: Difference between revisions

=={{header|11l}}==

[[wp:Pratt parser|Pratt parser]]

String id

Int lbp

L(expr_str) [‘-2 / 2 + 4 + 3 * 2’,

‘2 * (3 + (4 * 5 + (6 * 7) * 8) - 9) * 10’]

{{out}}

<pre>

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

{{out}}

<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

{{out}}

<pre>

 

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

(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;

 

immutable exp = (args.length > 1) ? args[1 .. $].join(' ') : exp0;

new AST().parse(exp).CalcVis; // Should be 60.

{{out}}

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

=={{header|Dyalect}}==

 

with Lookup

 

print( eval("(1+33.23)*7") )

 

{{out}}

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|Elena}}==

ELENA 5.0 :

import extensions;

import extensions'text;

text.clear()

}

 

=={{header|Emacs Lisp}}==

;; -*- mode: emacs-lisp; lexical-binding: t -*-

;;> ./arithmetic-evaluation '(1 + 2) * 3'

(terpri)))

(setq command-line-args-left nil)

 

{{out}}

 

=={{header|ERRE}}==

PROGRAM EVAL

 

IF NERR>0 THEN PRINT("Internal Error #";NERR) ELSE PRINT("Value is ";DB#) END IF

END PROGRAM

This solution is based on a stack: as a plus there is a power (^) operator. Unary operator "-" is accepted. Program shows the stack after every operation and you must press a key to go on (this feature can be avoided by removing the final REPEAT..UNTIL loop at the end of "DISEGNA_STACK" procedure).

 

 

<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|Factor}}==

IN: rosetta.arith

 

 

: evaluate ( string -- result )

 

=={{header|FreeBASIC}}==

'Arithmetic evaluation

'

if sym <> done_sym then error_msg("unexpected input")

loop

 

{{out}}

=={{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 }

 

{{out}}

 

=={{header|Haskell}}==

 

import Text.Parsec

 

main :: IO ()

{{Out}}

<pre>28</pre>

* 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() | ""

 

{{out|Sample Output}}

The implementation here uses a shift/reduce parser to build a tree structure for evaluation (a tree structure which J happens to support for evaluation):

 

eval=:monad define

'gerund structure'=:y

coerase tmp

r

example use:

 

You can also display the syntax tree, for example:

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

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

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

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

 

At the top level, the first box is a list of terminals, and the second box represents their parsed structure within the source sentence, with numbers indexing the respective terminals. Within the list of terminals - each terminal is contained with a box. Operators are strings inside of boxes (the leading $ "operator" in this example is not really an operator - it's just a placeholder that was used to help in the parsing). Punctuation is simply the punctuation string (left or right parenthesis - these are also not really operators and are just placeholders which were used during parsing). Numeric values are a box inside of a box where the inner box carries two further boxes. The first indicates syntactic data type ('0' for arrays - here that means numbers) and the second carries the value.

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

 

 

public class ArithmeticEvaluation {

}

}

 

{{out}}

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

 

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

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

}

}

 

 

 

=== PEG operations ===

def plus(E): E | (plus(E) // . );

def optional(E): E // .;

def amp(E): . as $in | E | $in;

 

 

=== Helper functions ===

select(.remainder | startswith($s))

| .result += [$s]

def parseNumber($re):

consume($re)

 

=== PEG Grammar ===

 

def ws: consume(" *");

Product | ws | star( (literal("+") // literal("-")) | Product);

 

 

=== Evaluation ===

def eval:

if type == "array" then

{remainder: String}

| Expr.result

 

=== Example ===

From Javascript entry.

 

function evalArithmeticExp(s) {

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

evalArithmeticExp('2*-3--4+-0.25') ==> -2.25

=!EXPECTEND!=

 

{{out}}

=={{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|Kotlin}}==

{{trans|JavaScript}}

 

/* if string is empty, returns zero */

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

).forEach { println("$it = ${evalArithmeticExp(it)}") }

 

{{out}}

 

=={{header|Liberty BASIC}}==

'[RC] Arithmetic evaluation.bas

'Buld the tree (with linked nodes, in array 'cause LB has no pointers)

addOpNode = newNode

end function

 

{{out}}

=={{header|Lua}}==

 

 

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

end

 

 

=={{header|M2000 Interpreter}}==

All visible variables can be used, and all known functions, internal and user (if they are visible at that point). Global variables and functions are always visible.

 

y=100

Module CheckEval {

}

Call CheckEval

 

From BBC BASIC. In M2000 we can't call a user function which isn't a child function, so here we make all functions as members of same group, so now they call each other. A function as a member in a group can use other members, using a dot or This and a dot, so .Ast$() is same as This.Ast$().

 

Module CheckAst {

Group Eval {

}

CheckAst

 

=={{header|Mathematica}} / {{header|Wolfram Language}}==

parse[string_] :=

Module[{e},

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

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

 

Example use:

 

{{out}}

 

=={{header|MiniScript}}==

Expr.eval = 0

 

print ast.eval

end while

{{out}}

<pre>Enter expression: 200*42

This implementation uses a Pratt parser.

 

import os

 

 

# In the end, we print out the result.

 

=={{header|OCaml}}==

 

| Const of float

| Sum of expression * expression (* e1 + e2 *)

let parse_expression = parser [< e = parse_expr; _ = Stream.empty >] -> e

 

 

Using the function <code>read_expression</code> in an interactive loop:

 

while true do

print_string "Expression: ";

let res = eval expr in

Printf.printf " = %g\n%!" res;

 

Compile with:

 

=={{header|ooRexx}}==

expressions = .array~of("2+3", "2+3/4", "2*3-4", "2*(3+4)+5/6", "2 * (3 + (4 * 5 + (6 * 7) * 8) - 9) * 10", "2*-3--4+-.25")

loop input over expressions

raise syntax 98.900 array("Invalid expression")

return expression

{{out}}

<pre>

The <code>Do</code> procedure automatically threads the input state through a sequence of procedure calls.

 

 

fun {Expr X0 ?X}

{Inspector.configure widgetShowStrings true}

{Inspect AST}

 

To improve performance, the number of choice points should be limited, for example by reading numbers deterministically instead.

 

=={{header|Perl}}==

# Evaluates an arithmetic expression like "(1+3)*7" and returns

# its value.

my ($op, @operands) = @$ast;

$_ = ev_ast($_) foreach @operands;

 

=={{header|Phix}}==

plus this as asked for has an AST, whereas Phix uses cross-linked flat IL.

See also [[Arithmetic_evaluation/Phix]] for a translation of the D entry.

<span style="color: #000080;font-style:italic;">-- demo\rosetta\Arithmetic_evaluation.exw</span>

<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>

<span style="color: #0000FF;">?</span><span style="color: #000000;">evaluate</span><span style="color: #0000FF;">(</span><span style="color: #000000;">opstack</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">])</span>

<span style="color: #0000FF;">{}</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">wait_key</span><span style="color: #0000FF;">()</span>

I added a flag (for this task) to store the ast nodes as op_p_p, p_op_p, or p_p_op, whichever you prefer.

{{out}}

 

=={{header|Picat}}==

print("Enter an expression: "),

Str = read_line(),

Res is Exp,

printf("Result = %w\n", Res).

 

=={{header|PicoLisp}}==

(numbers and transient symbols). From that, a recursive descendent parser can

build an expression tree, resulting in directly executable Lisp code.

(let *L (str Str "")

(aggregate) ) )

((= "+" X) (term))

((= "-" X) (list '- (term)))

{{out}}

-> (+ (+ 1 2) (/ (* 3 (- 4)) (+ 1 2)))

 

: (ast "(1+2+3)*-4/(1+2)")

 

=={{header|Pop11}}==

 

/* Uncomment the following to parse data from standard input

 

 

;;; Test it

 

=={{header|Prolog}}==

{{works with|SWI Prolog 8.1.19}}

numeric(X) :- 48 =< X, X =< 57.

not_numeric(X) :- 48 > X ; X > 57.

% Example use

 

=={{header|Python}}==

<br>A subsequent example uses Pythons' ast module to generate the abstract syntax tree.

 

 

class AstNode(object):

expr = raw_input("Expression:")

astTree = Lex( expr, Yaccer())

 

===ast standard library module===

Python comes with its own [http://docs.python.org/3.1/library/ast.html#module-ast ast] module as part of its standard libraries. The module compiles Python source into an AST tree that can in turn be compiled to bytecode then executed.

>>>

>>> expr="2 * (3 -1) + 2 * 5"

>>> code_object = compile(node, filename='<string>', mode='eval')

>>> eval(code_object)

 

=={{header|Racket}}==

 

 

(require parser-tools/yacc

(displayln (parse (λ () (lex i)))))

 

 

=={{header|Raku}}==

{{Works with|rakudo|2018.03}}

 

 

grammar expr {

say ev '1 + 2 - 3 * 4 / 5'; # 0.6

say ev '1 + 5*3.4 - .5 -4 / -2 * (3+4) -6'; # 25.5

 

=={{header|REXX}}==

:::* &nbsp; 12.3D+44 &nbsp; &nbsp; &nbsp; ("double" precision)

:::* &nbsp; 12.3Q+44 &nbsp; &nbsp; &nbsp; ("extended" or "quad" precision)

nchars = '0123456789.eEdDqQ' /*possible parts of a number, sans ± */

e='***error***'; $=" "; doubleOps= '&|*/'; z= /*handy─dandy variables.*/

return substr(x, Nj, 1) /* [↑] ignore any blanks in expression*/

end /*Nj*/

To view a version of the above REXX program, see this version which has much more whitespace: &nbsp; ──► &nbsp; [[Arithmetic_evaluation/REXX]]. <br>

<br>

=={{header|Ruby}}==

Function to convert infix arithmetic expression to binary tree. The resulting tree knows how to print and evaluate itself. Assumes expression is well-formed (matched parens, all operators have 2 operands). Algorithm: http://www.seas.gwu.edu/~csci131/fall96/exp_to_tree.html

 

class TreeNode

node_stack.last

Testing:

puts("Original: " + exp)

 

puts("Infix: " + tree.to_s(:infix))

puts("Postfix: " + tree.to_s(:postfix))

{{out}}

<pre>Original: 1 + 2 - 3 * (4 / 6)

 

=={{header|Rust}}==

 

 

}

 

 

=={{header|Scala}}==

is practically non-existent, to avoid obscuring the code.

 

package org.rosetta.arithmetic_evaluator.scala

 

}

}

 

Example:

The parse function uses a recursive-descent parser to follow the precedence rules.

 

(import (scheme base)

(scheme char)

(newline))

'("1 + 2" "20+4*5" "1/2+5*(6-3)" "(1+3)/4-1" "(1 - 5) * 2 / (20 + 1)"))

 

{{out}}

=={{header|Sidef}}==

{{trans|JavaScript}}

 

func evalExp(s) {

 

return Number(evalExp(s))

 

Testing the function:

['2+3' => 5],

['-4-3' => -7],

assert_eq(num, res)

"%-45s == %10g\n".printf(expr, num)

 

=={{header|Standard ML}}==

This implementation uses a [https://en.wikipedia.org/wiki/Recursive_descent_parser recursive descent parser]. It first lexes the input. The parser builds a Abstract Syntax Tree (AST) and the evaluator evaluates it. The parser uses sub categories.

The parsing is a little bit tricky because the grammar is left recursive.

datatype expression =

Con of int (* constant *)

case parseE (lex (explode str)) of

(exp, nil) => eval exp

 

=={{header|Tailspin}}==

def ops: ['+','-','*','/'];

 

'$ast -> evaluateArithmetic;

' -> !OUT::write

{{out}}

<pre>

 

If we don't need to get the AST, we could just evaluate right away:

composer calculator

(<WS>?) <addition|multiplication|term> (<WS>?)

'

' -> !OUT::write

{{out}}

<pre>16</pre>

in a form that it can be immediately eval-led,

using Tcl's prefix operators.

 

proc ast str {

} \n] {

puts "$test ..... [eval $test] ..... [eval [eval $test]]"

{{out}}

<pre>

Use TXR text pattern matching to parse expression to a Lisp AST, then evaluate with <code>eval</code>:

 

@(define space)@/ */@(end)

@(define mulop (nod))@\

erroneous suffix "@bad"

@ (end)

 

Run:

=={{header|Ursala}}==

with no error checking other than removal of spaces

#import nat

#import flo

traverse = *^ ~&v?\%ep ^H\~&vhthPX '+-*/'-$<plus,minus,times,div>@dh

 

 

test program:

 

test = evaluate*t

5-3*2

(1+1)*(2+3)

{{out}}

<pre>

{{trans|Kotlin}}

{{libheader|Wren-pattern}}

 

/* if string is empty, returns zero */

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

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

 

{{out}}

=={{header|zkl}}==

In zkl, the compiler stack is part of the language and is written in zkl so ...

The ASTs look like

{{out}}

</pre>

Evaluating them is just moving up the stack:

{{out}}

<pre>

 

=={{header|ZX Spectrum Basic}}==

20 LET s$="": REM last symbol

30 LET pc=0: REM parenthesis counter

300 PRINT FLASH 1;"Invalid symbol ";c$;" detected in pos ";n: BEEP 1,-25

310 STOP