Arithmetic evaluation: Difference between revisions

{{task}}[[Category:Recursion]]

{{task}}Create a program which parses and evaluates arithmetic expressions.

<langsyntaxhighlight lang="algol68">INT base=10;

)</langsyntaxhighlight>

#include calclex.ahk</langsyntaxhighlight>

calclex.ahk<langsyntaxhighlight AutoHotkeylang="autohotkey">tokenize(string, lexer)

}</langsyntaxhighlight>

<langsyntaxhighlight lang="bbcbasic"> Expr$ = "1 + 2 * (3 + (4 * 5 + 6 * 7 * 8) - 9) / 10"

= num$</langsyntaxhighlight>

<langsyntaxhighlight lang="cpp"> #include <boost/spirit.hpp>

};</langsyntaxhighlight>

<langsyntaxhighlight Clojurelang="clojure">(def precedence '{* 0, / 0

60</langsyntaxhighlight>

<langsyntaxhighlight lang="lisp">(defun tokenize-stream (stream)

collect token)))))))</langsyntaxhighlight>

<langsyntaxhighlight lang="d">import std.stdio, std.string, std.ascii, std.conv, std.array,

immutable int pos; // Optional, to dispalydisplay AST struct.

}</langsyntaxhighlight>

<langsyntaxhighlight lang="e">def eParser := <elang:syntax.makeEParser>

}</langsyntaxhighlight>

<langsyntaxhighlight lang="e">? arithEvaluate("1 + 2")

# value: 20.0</langsyntaxhighlight>

#define<syntaxhighlight lang="elena">import system'routines.;

#defineimport extensions.;

#class Token

constructor #methodnew(int level = theLevel.)

#method append : aChar(ch)

[{

]}

#method numberNumber = theValue value _value.toReal.();

#class Node

#constructor new(int &level:aLevel)

[{

theLevelLevel := aLevel.level

]}

#class SummaryNode :: Node

#constructor new(int &level:aLevel)

<= %super new &(level:(aLevel + 1).;

#class DifferenceNode :: Node

#constructor new(int &level:aLevel)

<= %super new &(level:(aLevel + 1).;

#class ProductNode :: Node

#constructor new(int &level:aLevel)

<= %super new &(level:(aLevel + 2).;

#class FractionNode :: Node

#constructor new(int &level:aLevel)

<= %super new &(level:(aLevel + 2).;

#class Expression

int #fieldLevel theLevel. :rprop;

object #fieldTop theTop.:prop;

#constructor new(int &level:aLevel)

[{

theLevelLevel := aLevel.level

]}

#method set &right:aNode [ theTop Top := aNode. ]node

}

get #method numberNumber() => theTop.Top;

eval(ch =>)

] $41 { // )

]. $42 { // *

eval(ch =>)

] $40 { // (

#42 ? [ ^ weak // *self.newBracket().gotoStarting()

] $45 { // -

] ! {

#45 ? [ ^ weak // -self.newToken().append(ch).gotoToken()

]}

#class Scope

int #field theLevel. _level;

#constructor new &(parser:aParser)

[{

theState_state := startState.;

theLevel_level := 0.;

theExpression_expression := Expression .new &level:(0.);

theParser_parser := aParser.parser

]}

[{

]}

[{

theToken_token := nil.;

]}

[{

theToken_token := nil.;

]}

[{

theToken_token := nil.;

]}

[{

theToken_token := nil.;

]}

[{

theToken_token := nil.;

theLevel_level := theLevel_level + 10.;

]}

[{

if (theLevel_level < 10)

? [ #throw{ InvalidArgumentException .new &message:("Invalid expression").raise() ].};

theLevel_level := theLevel_level - 10.

]}

#method append:(ch)

[{

(if(ch >= $48) and:(&& ch < $58))

] }

#method append(string &literal:aLiterals)

[{

aLiteral run &eachs.forEach: :(ch [){ self .append:(ch.) ].}

]}

[{

theState_state := startState.

]}

[{

theState_state := tokenState.

]}

[{

theState_state := operatorState.

]}

get #method numberNumber() => theExpression._expression;

#methoddispatch() => theState._state;

#class Parser

[{

#var aTokentoken := Token .new &(level:aLevel.);

expression.Top := anExpression set &top:($self .append &last:(anExpressionexpression.Top, toptoken) &new:aToken).;

^ aToken.token

]}

[{

[}

[{

expression.Top := anExpression set &top:($self .append &last:(anExpressionexpression.Top, top) &DifferenceNode.new:(ProductNode new &level:aLevel)).

]}

[{

expression.Top := anExpression set &top:($self .append &last:(anExpressionexpression.Top, top) &ProductNode.new:(FractionNode new &level:aLevel)).

]}

[{

expression.Top := anExpression set &top:($self .append &last:(anExpressionexpression.Top, top) &FractionNode.new:(Expression new &level:aLevel)).

]}

[{

if (aNewNode levelnewNode.Level <= aLastNode levellastNode.Level)

{ newNode.Left := ? [ aNewNode set &left:aLastNode.lastNode; ^ aNewNode.newNode ].};

#var aParentparent := aLastNode.lastNode;

#var aCurrentcurrent := aLastNode rightlastNode.Right;

while #loop (($nil != aCurrent)current and:[&& aNewNode levelnewNode.Level > aCurrent level ]current.Level) ?

{ [ aParentparent := aCurrent.current; aCurrentcurrent := aCurrent rightcurrent.Right ].};

if ($nil == aCurrentcurrent)

^ aLastNode.lastNode

]}

#method run : aText(text)

[{

#var aScopescope := Scope .new &parser:$(self.);

aText run &eachtext.forEach: :(ch){ [ aScope scope.eval:(ch.) ].};

^ aScope numberscope.Number

]}

#symbolpublic program =()

#var aTexttext := Stringnew new.StringWriter();

#var aParserparser := new Parser new.();

[while (aText << console .readLine() length.writeTo(text).Length > 0] doWhile:)

[{

| if &Error:e [{

console writeLine:.printLine("Invalid Expression=",parser.run(text))

].}

<langsyntaxhighlight lang="fsharp">module AbstractSyntaxTree

| Divide of Expression * Expression</langsyntaxhighlight>

<langsyntaxhighlight lang="fsharp">{

| _ { failwithf "unrecognized input: '%s'" <| lexeme lexbuf }</langsyntaxhighlight>

<langsyntaxhighlight lang="fsharp">%{

| LPAREN Expr RPAREN { $2 } </langsyntaxhighlight>

<langsyntaxhighlight lang="fsharp">open AbstractSyntaxTree

|> printfn "%d"</langsyntaxhighlight>

<langsyntaxhighlight lang="groovy">enum Op {

}</langsyntaxhighlight>

<langsyntaxhighlight lang="groovy">def testParse = {

try { testParse('/ 1 /') } catch (e) { println e }</langsyntaxhighlight>

data Exp = Num Int

| Sub ExpAdd Exp

| Mul Exp Exp

| Div ExpSub Exp

[ [op s"*" fMul assocAssocLeft, = Infix (f <$op string"/" s)Div assocAssocLeft]

op ons f g = \x y ->Infix (f (g<$ x) (gstring ys)

=> Num x String -> fromIntegral xa

solution = either (const Add(error a"Did bnot ->parse")) eval a. parse expr + eval b""

<langsyntaxhighlight Iconlang="icon">procedure main() #: simple arithmetical parser / evaluator

end</langsyntaxhighlight>

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

<langsyntaxhighlight lang="j">parse=:parse_parser_

)</langsyntaxhighlight>

<langsyntaxhighlight lang="j"> eval parse '1+2*3/(4-5+6)'

2.2</langsyntaxhighlight>

<langsyntaxhighlight lang="j"> parse '2*3/(4-5)'

└─────────────────────────────────────────────────────┴───────────────────┘</langsyntaxhighlight>

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. Punctuation is simply the punctuation string (left or right parenthesis). 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.

<langsyntaxhighlight lang="java">import java.util.Stack;

public class ArithmeticEvaluation {

public staticinterface enum ParenthesesExpression { LEFT, RIGHT }

this.operatorsymbol = operatorsymbol;

this.rightOperandprecedence = rightOperandprecedence;

public BigRationalstatic eval()class Number implements Expression {

public BigRational eval() {

if (c =BigRational leftValue = operatorleftOperand.symboleval();

continue inputStringLoop;@Override

public String }toString() {

Object operator Expression leftOperand = operatorsoperands.pop();

throw new IllegalArgumentException()int curIndex = 0;

<pre>Input: "2+3", AST: "(2 + 3)", evalvalue=5

Input: "2+3/4", AST: "(2 + (3 / 4))", evalvalue=11/4

Input: "2*3-4", AST: "((2 * 3) - 4)", evalvalue=2

Input: "2*(3+4)+5/6", AST: "((2 * (3 + 4)) + (5 / 6))", evalvalue=89/6

Input: "2 * (3 + (4 * 5 + (6 * 7) * 8) - 9) * 10", AST: "((2 * ((3 + ((4 * 5) + ((6 * 7) * 8))) - 9)) * 10)", evalvalue=7000

Input: "2*-3--4+-.25", AST: "(((2 * -3) - -4) + -1/4)", evalvalue=-9/4</pre>

<langsyntaxhighlight lang="javascript">function evalArithmeticExp(s) {

}</langsyntaxhighlight>

<langsyntaxhighlight lang="julia">julia> expr="2 * (3 -1) + 2 * 5"

3.5</langsyntaxhighlight>

=={{header|LuaKotlin}}==

<langsyntaxhighlight Mathematicalang="mathematica">(*parsing:*)

evaluate[string_String] := evaluate[parse[string]]</langsyntaxhighlight>

<langsyntaxhighlight Mathematicalang="mathematica">parse["-1+2(3+4*-5/6)"]

evaluate["-1+2(3+4*-5/6)"]</langsyntaxhighlight>

<langsyntaxhighlight lang="ocaml">type expression =

let read_expression s = parse_expression(lexer(Stream.of_string s))</langsyntaxhighlight>

<langsyntaxhighlight lang="ocaml">let () =

done</langsyntaxhighlight>

<langsyntaxhighlight lang="oz">declare

{Inspect {Eval AST}}</langsyntaxhighlight>

<langsyntaxhighlight lang="perl">sub ev

return $ops{$op}->(@operands);}}</langsyntaxhighlight>

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

-- p_op_p -- 0: expressions stored as p1,op,p2 -- sequence elements are subexpressions

-- p_p_op -- -1:on expressionscompletion storedlength(opstack) asshould p1,p2,opbe 1</span>

-- p is the precedence level 1:we ""should andparse +to,- eg/ie

-- 04: fullFactor expressiononly (effectivelymay theas samewell asjust call 1Factor)

<langsyntaxhighlight PicoLisplang="picolisp">(de ast (Str)

((= "(" X) (prog1 (aggregate) (pop '*L)))) ) )</langsyntaxhighlight>

<langsyntaxhighlight PicoLisplang="picolisp">: (ast "1+2+3*-4/(1+2)")

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

<langsyntaxhighlight lang="pop11">/* Scanner routines */

arith_eval(do_expr()) =></langsyntaxhighlight>

{{works with|SWI Prolog 8.1.19}}

<langsyntaxhighlight lang="prolog">% Lexer

lex1string_codes(String, Tokens1Codes),

% calculator("(3+50)*7-9", X).</langsyntaxhighlight>

<langsyntaxhighlight lang="python">import operator

print expr, '=',astTree.eval()</langsyntaxhighlight>

<langsyntaxhighlight lang="python">>>> import ast

16</langsyntaxhighlight>

<langsyntaxhighlight lang="racket">#lang racket

(require parser-tools/yacc parser-tools/lex

[(~: (~+ numeric) (~? (~: #\. (~* numeric))))

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

(calc "(1 + 2 * 3) - (1+2)*-3")</syntaxhighlight>

<langsyntaxhighlight lang="rexx">/*REXX pgmprogram evaluates an infix-type infix─type arithmetic expression & showsand displays the result.*/