Arithmetic evaluation

Create a program which parses and evaluates arithmetic expressions.

Requirements

An abstract-syntax tree (AST) for the expression must be created from parsing the input.
The AST must be used in evaluation, also, so the input may not be directly evaluated (e.g. by calling eval or a similar language feature.)
The expression will be a string or list of symbols like "(1+3)*7".
The four symbols + - * / must be supported as binary operators with conventional precedence rules.
Precedence-control parentheses must also be supported.

Note

For those who don't remember, mathematical precedence is as follows:

Parentheses
Multiplication/Division (left to right)
Addition/Subtraction (left to right)

C.f

OP + = (NUM a,b)NUM: ( HEAP AST := NODE(a, (FIXED a,b)FIXED:a+b, b) ); OP - = (NUM a,b)NUM: ( HEAP AST := NODE(a, (FIXED a,b)FIXED:a-b, b) ); OP * = (NUM a,b)NUM: ( HEAP AST := NODE(a, (FIXED a,b)FIXED:a*b, b) ); OP / = (NUM a,b)NUM: ( HEAP AST := NODE(a, (FIXED a,b)FIXED:a/b, b) ); OP **= (NUM a,b)NUM: ( HEAP AST := NODE(a, (FIXED a,b)FIXED:a**b, b) );

ELSE simply use REAL arithmetic with no abstract syntax tree at all # CO

MODE NUM = FIXED, AST = FIXED; OP EVAL = (FIXED num)FIXED: num;

FI# END CO

MODE LEX = PROC (TOK)NUM; MODE MONADIC =PROC (NUM)NUM; MODE DIADIC = PROC (NUM,NUM)NUM;

MODE TOK = CHAR; MODE ACTION = UNION(STACKACTION, LEX, MONADIC, DIADIC); MODE OPVAL = STRUCT(INT prio, ACTION action); MODE OPITEM = STRUCT(TOK token, OPVAL opval);

[256]STACKITEM stack; MODE STACKITEM = STRUCT(NUM value, OPVAL op); MODE STACKACTION = PROC (REF STACKITEM)VOID;

PROC begin = (REF STACKITEM top)VOID: prio OF op OF top -:= +10; PROC end = (REF STACKITEM top)VOID: prio OF op OF top -:= -10;

OP ** = (COMPL a,b)COMPL: complex exp(complex ln(a)*b);

[8]OPITEM op list :=(

OP PRIO ACTION #

 ("^", (8, (NUM a,b)NUM: a**b)),
 ("*", (7, (NUM a,b)NUM: a*b)),
 ("/", (7, (NUM a,b)NUM: a/b)),
 ("+", (6, (NUM a,b)NUM: a+b)),
 ("-", (6, (NUM a,b)NUM: a-b)),
 ("(",(+10, begin)),
 (")",(-10, end)),
 ("?", (9, LEX:SKIP))

);

PROC op dict = (TOK op)REF OPVAL:(

This can be unrolled to increase performance #

 REF OPITEM candidate;
 FOR i TO UPB op list WHILE
   candidate := op list[i];

WHILE # op /= token OF candidate DO

   SKIP
 OD;
 opval OF candidate

);

PROC build ast = (STRING expr)NUM:(

 INT top:=0;

 PROC compress ast stack = (INT prio, NUM in value)NUM:(
   NUM out value := in value;
   FOR loc FROM top BY -1 TO 1 WHILE 
     REF STACKITEM stack top := stack[loc];
 # WHILE # ( top >= LWB stack | prio <= prio OF op OF stack top | FALSE ) DO
     top := loc - 1;
     out value := 
       CASE action OF op OF stack top IN
         (MONADIC op): op(value OF stack top), # not implemented #
         (DIADIC op): op(value OF stack top,out value)
       ESAC
   OD;
   out value
 );

 NUM value := NIL;
 FIXED num value;
 INT decimal places;

 FOR i TO UPB expr DO
   TOK token = expr[i];
   REF OPVAL this op := op dict(token); 
   CASE action OF this op IN
     (STACKACTION action):(
       IF prio OF thisop = -10 THEN
         value := compress ast stack(0, value)
       FI;
       IF top >= LWB stack THEN
         action(stack[top])
       FI
     ),
     (LEX):( # a crude lexer #
       SHORT INT digit = ABS token - ABS "0";
       IF 0<= digit AND digit < base THEN
         IF NUM(value) IS NIL THEN # first digit #
           decimal places := 0;
           value := HEAP AST := num value := digit
         ELSE
           NUM(value) := num value := IF decimal places = 0 
             THEN
               num value * base + digit
             ELSE
               decimal places *:= base;
               num value + digit / decimal places
             FI
         FI
       ELIF token = "." THEN
         decimal places := 1
       ELSE
         SKIP # and ignore spaces and any unrecognised characters #
       FI
     ),
     (MONADIC): SKIP, # not implemented #
     (DIADIC):(
       value := compress ast stack(prio OF this op, value);
       IF top=UPB stack THEN index error FI;
       stack[top+:=1]:=STACKITEM(value, this op);
       value:=NIL
     )
   ESAC
 OD;
 compress ast stack(-max int, value)

);

test:(

  printf(($" euler's number is about: "g(-long real width,long real width-2)l$,
    EVAL build 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")));
 SKIP EXIT
 index error:
   printf(("Stack over flow"))

)</lang> Output:

 euler's number is about: 2.71828182845899446428546958

AutoHotkey

Works with: AutoHotkey_L

<lang AutoHotkey>/* hand coded recursive descent parser expr : term ( ( PLUS | MINUS ) term )* ; term : factor ( ( MULT | DIV ) factor )* ; factor : NUMBER | '(' expr ')';

/

calcLexer := makeCalcLexer() string := "((3+4)*(7*9)+3)+4" tokens := tokenize(string, calcLexer) msgbox % printTokens(tokens) ast := expr() msgbox % printTree(ast) msgbox % expression := evalTree(ast) filedelete expression.ahk fileappend, % "msgbox % " expression, expression.ahk run, expression.ahk return

expr() {

 global tokens
 ast := object(1, "expr")
 if node := term()
   ast._Insert(node)    
 loop 
 {
   if peek("PLUS") or peek("MINUS")
   {  
     op := getsym()
     newop := object(1, op.type, 2, op.value)
     node := term()
     ast._Insert(newop)
     ast._Insert(node)
   }
   Else  
     Break
 }
 return ast

}

term() {

 global tokens
 tree := object(1, "term")
 if node := factor()
   tree._Insert(node)
 loop 
 {
   if  peek("MULT") or peek("DIV")
   {  
     op := getsym()
     newop := object(1, op.type, 2, op.value)
     node := factor()
     tree._Insert(newop)
     tree._Insert(node)
   }
   else
     Break
 }
 return tree

}

factor() {

 global tokens
 if peek("NUMBER")
 {  
   token := getsym()
   tree := object(1, token.type, 2, token.value)
   return tree
 }
 else if  peek("OPEN")
 {
   getsym()
   tree := expr()
   if  peek("CLOSE")
   {
     getsym()
     return tree
   }
   else
     error("miss closing parentheses ")
 }
 else  
   error("no factor found")

}

peek(type, n=1) { global tokens

 if (tokens[n, "type"] == type)
 return 1

}

getsym(n=1) { global tokens return token := tokens._Remove(n) }

error(msg) { global tokens msgbox % msg " at:`n" printToken(tokens[1]) }

printTree(ast) { if !ast return

n := 0

 loop
 {
 n += 1
   if !node := ast[n]
     break
   if !isobject(node)
     treeString .= node
   else
     treeString .= printTree(node)
 }
 return ("(" treeString ")" )

}

evalTree(ast) { if !ast return

n := 1

 loop
 {
 n += 1
   if !node := ast[n]
     break
   if !isobject(node)
     treeString .= node
   else
     treeString .= evalTree(node)
 }

if (n == 3) return treeString

 return ("(" treeString ")" )

}

include calclex.ahk</lang>

calclex.ahk<lang AutoHotkey>tokenize(string, lexer) {

 stringo := string  ; store original string
 locationInString := 1
 size := strlen(string)
 tokens := object()

start:

 Enum := Lexer._NewEnum()
 While Enum[type, value]  ; loop through regular expression lexing rules
 {
   if (1 == regexmatch(string, value, tokenValue))
   {
     token := object()     
     token.pos := locationInString 
     token.value := tokenValue
     token.length := strlen(tokenValue)
     token.type := type
     tokens._Insert(token)
     locationInString += token.length
     string := substr(string, token.length + 1)
     goto start
   } 
   continue
 }
 if (locationInString < size)
   msgbox % "unrecognized token at " substr(stringo, locationInstring)
 return tokens

}

makeCalcLexer() {

 calcLexer := object()
 PLUS := "\+"
 MINUS := "-"
 MULT := "\*"
 DIV := "/"
 OPEN := "\("
 CLOSE := "\)"
 NUMBER := "\d+"
 WS := "[ \t\n]+"
 END := "\."
 RULES := "PLUS,MINUS,MULT,DIV,OPEN,CLOSE,NUMBER,WS,END"
 loop, parse, rules, `,
 {
   type := A_LoopField
   value := %A_LoopField%
   calcLexer._Insert(type, value)
 }
 return calcLexer

}

printTokens(tokens) {

 loop % tokens._MaxIndex()
 {  
   tokenString .= printToken(tokens[A_Index]) "`n`n"
 }
 return tokenString

}

printToken(token) {

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

}</lang>

C

See Arithmetic Evaluator/C.

C++

Works with: g++ version 4.1.2 20061115 (prerelease) (SUSE Linux)

Library: Boost.Spirit version 1.8.4

<lang cpp> #include <boost/spirit.hpp>

#include <boost/spirit/tree/ast.hpp>
#include <string>
#include <cassert>
#include <iostream>
#include <istream>
#include <ostream>

using boost::spirit::rule;
using boost::spirit::parser_tag;
using boost::spirit::ch_p;
using boost::spirit::real_p;

using boost::spirit::tree_node;
using boost::spirit::node_val_data;

// The grammar
struct parser: public boost::spirit::grammar<parser>
{
  enum rule_ids { addsub_id, multdiv_id, value_id, real_id };

  struct set_value
  {
    set_value(parser const& p): self(p) {}
    void operator()(tree_node<node_val_data<std::string::iterator,
                                            double> >& node,
                    std::string::iterator begin,
                    std::string::iterator end) const
    {
      node.value.value(self.tmp);
    }
    parser const& self;
  };

  mutable double tmp;

  template<typename Scanner> struct definition
  {
    rule<Scanner, parser_tag<addsub_id> > addsub;
    rule<Scanner, parser_tag<multdiv_id> > multdiv;
    rule<Scanner, parser_tag<value_id> > value;
    rule<Scanner, parser_tag<real_id> > real;

    definition(parser const& self)
    {
      using namespace boost::spirit;
      addsub = multdiv
        >> *((root_node_d[ch_p('+')] | root_node_d[ch_p('-')]) >> multdiv);
      multdiv = value
        >> *((root_node_d[ch_p('*')] | root_node_d[ch_p('/')]) >> value);
      value = real | inner_node_d[('(' >> addsub >> ')')];
      real = leaf_node_d[access_node_d[real_p[assign_a(self.tmp)]][set_value(self)]];
    }

    rule<Scanner, parser_tag<addsub_id> > const& start() const
    {
      return addsub;
    }
  };
};

template<typename TreeIter>
double evaluate(TreeIter const& i)
{
  double op1, op2;
  switch (i->value.id().to_long())
  {
  case parser::real_id:
    return i->value.value();
  case parser::value_id:
  case parser::addsub_id:
  case parser::multdiv_id:
    op1 = evaluate(i->children.begin());
    op2 = evaluate(i->children.begin()+1);
    switch(*i->value.begin())
    {
    case '+':
      return op1 + op2;
    case '-':
      return op1 - op2;
    case '*':
      return op1 * op2;
    case '/':
      return op1 / op2;
    default:
      assert(!"Should not happen");
    }
  default:
    assert(!"Should not happen");
  }
  return 0;
}

// the read/eval/write loop
int main()
{
  parser eval;
  std::string line;
  while (std::cout << "Expression: "
         && std::getline(std::cin, line)
         && !line.empty())
  {
    typedef boost::spirit::node_val_data_factory<double> factory_t;
    boost::spirit::tree_parse_info<std::string::iterator, factory_t> info =
      boost::spirit::ast_parse<factory_t>(line.begin(), line.end(),
                                          eval, boost::spirit::space_p);
    if (info.full)
    {
      std::cout << "Result: " << evaluate(info.trees.begin()) << std::endl;
    }
    else
    {
      std::cout << "Error in expression." << std::endl;
    }
  }
};</lang>

Clojure

<lang Clojure>(def precedence '{* 0, / 0 + 1, - 1})

(defn order-ops

 "((A x B) y C) or (A x (B y C)) depending on precedence of x and y"
 A x B y C & more
 (let [ret (if (<=  (precedence x)

(precedence y)) (list (list A x B) y C) (list A x (list B y C)))]

   (if more
     (recur (concat ret more))
     ret)))

(defn add-parens

 "Tree walk to add parens.  All lists are length 3 afterwards."
 [s]
 (clojure.walk/postwalk
  #(if (seq? %)
     (let [c (count %)]

(cond (even? c) (throw (Exception. "Must be an odd number of forms")) (= c 1) (first %) (= c 3) % (>= c 5) (order-ops %)))

     %)
  s))

(defn make-ast

 "Parse a string into a list of numbers, ops, and lists"
 [s]
 (-> (format "'(%s)" s)
     (.replaceAll , "([*+-/])" " $1 ")
     load-string
     add-parens))

(def ops {'* * '+ + '- - '/ /})

(def eval-ast

    (partial clojure.walk/postwalk

#(if (seq? %) (let [[a o b] %] ((ops o) a b)) %)))

(defn evaluate [s]

 "Parse and evaluate an infix arithmetic expression"
 (eval-ast (make-ast s)))

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

Common Lisp

The following code processes the data in a pipeline of steps which are combined in the evaluate function.

First, the string is converted into a sequence of tokens, represented as a list. Operator tokens are represented directly by the corresponding Lisp symbols, and the integer terms are represented by Lisp integer objects. The symbols :lparen and :rparen represent the the parentheses. So for instance the input "1*(3+2)" tokenizes as (1 * :lparen 3 + 2 :rparen).

Next, that sequence of tokens is then transformed by eliminating the parentheses. Subsequences of the form :lparen ... :rparen with a sublist containing the tokens between the :lparen and :rparen. The sequence now has an intermediate tree structure, in which parenthesized fragments like 1 + 2 * 3 + 4 / 9 still remain flat.

At this point, another processing stage parses the operator precedence, and fully parenthesizes fragments, turning (1 + 2 / 3 + 5) into (1 + (2 / 3) + 5). The result is a Lisp-ified infix representation.

Finally, this infix representation can be easily converted to prefix, forming the final AST which is a Lisp expression. (Lisp expressions are abstract syntax trees!) This representation evaluates directly with eval.

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

<lang lisp>(defun tokenize-stream (stream)

 (labels ((whitespace-p (char)
            (find char #(#\space #\newline #\return #\tab)))
          (consume-whitespace ()
            (loop while (whitespace-p (peek-char nil stream nil #\a))
                  do (read-char stream)))
          (read-integer ()
            (loop while (digit-char-p (peek-char nil stream nil #\space))
                  collect (read-char stream) into digits
                  finally (return (parse-integer (coerce digits 'string))))))
   (consume-whitespace)
   (let ((c (peek-char nil stream nil nil)))
     (let ((token (case c
                    ((nil) nil)
                    ((#\() :lparen)
                    ((#\)) :rparen)
                    ((#\*) '*)
                    ((#\/) '/)
                    ((#\+) '+)
                    ((#\-) '-)
                    (otherwise
                      (unless (digit-char-p c)
                        (cerror "Skip it." "Unexpected character ~w." c)
                        (read-char stream)
                        (return-from tokenize-stream
                                     (tokenize-stream stream)))
                      (read-integer)))))
       (unless (or (null token) (integerp token))
         (read-char stream))
       token))))

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

 (do ((new-tokens '()))
     ((endp tokens)
      (when delimited
        (cerror "Insert it."  "Expected right parenthesis."))
      (values (nreverse new-tokens) '()))
   (let ((token (pop tokens)))
     (case token
       ((:lparen)
        (multiple-value-bind (group remaining-tokens)
            (group-parentheses tokens t)
          (setf new-tokens (cons group new-tokens)
                tokens remaining-tokens)))
       ((:rparen)
        (if (not delimited)
          (cerror "Ignore it." "Unexpected right parenthesis.")
          (return (values (nreverse new-tokens) tokens))))
       (otherwise
        (push token new-tokens))))))

(defun group-operations (expression)

 (flet ((gop (exp) (group-operations exp)))
   (if (integerp expression)
     expression
     (destructuring-bind (a &optional op1 b op2 c &rest others)
                         expression
       (unless (member op1 '(+ - * / nil))
         (error "syntax error: in expr ~a expecting operator, not ~a"
                expression op1))
       (unless (member op2 '(+ - * / nil))
         (error "syntax error: in expr ~a expecting operator, not ~a"
                expression op2))
       (cond
        ((not op1) (gop a))
        ((not op2) `(,(gop a) ,op1 ,(gop b)))
        (t (let ((a (gop a)) (b (gop b)) (c (gop c)))
             (if (and (member op1 '(+ -)) (member op2 '(* /)))
               (gop `(,a ,op1 (,b ,op2 ,c) ,@others))
               (gop `((,a ,op1 ,b) ,op2 ,c ,@others))))))))))

(defun infix-to-prefix (expression)

 (if (integerp expression)
   expression
   (destructuring-bind (a op b) expression
     `(,op ,(infix-to-prefix a) ,(infix-to-prefix b)))))

(defun evaluate (string)

 (with-input-from-string (in string)
   (eval
     (infix-to-prefix
       (group-operations
         (group-parentheses
           (loop for token = (tokenize-stream in)
                 until (null token)
                 collect token)))))))</lang>

Examples

> (evaluate "1 - 5 * 2 / 20 + 1")
3/2

> (evaluate "(1 - 5) * 2 / (20 + 1)")
-8/21

> (evaluate "2 * (3 + ((5) / (7 - 11)))")
7/2

> (evaluate "(2 + 3) / (10 - 5)")
1

Examples of error handling

> (evaluate "(3 * 2) a - (1 + 2) / 4")

 Error: Unexpected character a.
  1 (continue) Skip it.
  2 (abort) Return to level 0.
  3 Return to top loop level 0.

Type :b for backtrace, :c <option number> to proceed,  or :? for other options

 : 1 > :c 1
21/4

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

Error: Expected right parenthesis.
  1 (continue) Insert it.
  2 (abort) Return to level 0.
  3 Return to top loop level 0.

Type :b for backtrace, :c <option number> to proceed,  or :? for other options

: 1 > :c 1
21/4

D

Following the previous number-operator dual stacks approach, an AST is built while previous version is evaluating the expression value. After the AST tree is constructed, a visitor pattern is used to display the AST structure and calculate the value. <lang d>//module evaluate ; import std.stdio, std.string, std.ctype, std.conv ;

// simple stack template void push(T)(inout T[] stk, T top) { stk ~= top ; } T pop(T)(inout T[] stk, bool discard = true) {

 T top ;
 if (stk.length == 0) throw new Exception("Stack Empty") ;
 top = stk[$-1] ;
 if (discard) stk.length = stk.length - 1 ;
 return top ;

}

alias int Type ; enum { Num, OBkt, CBkt, Add, Sub, Mul, Div } ; // Type string[] opChar = ["#","(",")","+","-","*","/"] ; int[] opPrec = [0,-9,-9,1,1,2,2] ;

abstract class Visitor { void visit(XP e) ; }

class XP {

 Type type ;
 string str ;
 int pos ;  // optional, for dispalying AST struct.
 XP LHS, RHS = null ;
 this(string s = ")", int p = -1) {
   str = s ; pos = p ;
   type = Num ;
   for(Type t = Div ; t > Num ; t--)
     if(opChar[t] == s) type = t ;
 }
 int opCmp(XP rhs) { return opPrec[type] - opPrec[rhs.type] ; }
 void accept(Visitor v) { v.visit(this) ; } ;

}

class AST {

 XP root ;
 XP[] num, opr ;
 string xpr, token ;
 int xpHead, xpTail ;

 void joinXP(XP x) { x.RHS = num.pop() ; x.LHS = num.pop() ; num.push(x) ; }

 string nextToken() {
   while (xpHead < xpr.length && xpr[xpHead] == ' ') 
     xpHead++ ; // skip spc
   xpTail = xpHead ;
   if(xpHead < xpr.length) {
     token = xpr[xpTail..xpTail+1] ;
     switch(token) {
       case "(",")","+","-","*","/": // valid non-number
         xpTail++ ; 
         return token ;
       default: // should be number
         if(isdigit(token[0])) {
           while(xpTail < xpr.length && isdigit(xpr[xpTail]))
             xpTail++ ;
           return xpr[xpHead..xpTail] ;          
         } // else may be error 
     } // end switch 
   }
   if(xpTail < xpr.length)
     throw new Exception("Invalid Char <" ~ xpr[xpTail] ~ ">") ; 
   return null ;
 } // end nextToken

 AST parse(string s) {
   bool expectingOP ;
   xpr = s ;
   try {
     xpHead = xpTail = 0 ; 
     num = opr = null ;
     root = null ;
     opr.push(new XP) ; // CBkt, prevent evaluate null OP precidence
     while((token = nextToken) !is null) {
       XP tokenXP = new XP(token, xpHead) ;
       if(expectingOP) {   // process OP-alike XP
         switch(token) {
           case ")":
             while(opr.pop(false).type != OBkt)
               joinXP(opr.pop()) ;
             opr.pop() ;
             expectingOP = true ; break ;
           case "+","-","*","/":
             while (tokenXP <= opr.pop(false))
               joinXP(opr.pop()) ;
             opr.push(tokenXP) ;
             expectingOP = false ; break ;
           default:
             throw new Exception("Expecting Operator or ), not <" ~ token ~ ">") ;
         }
       } else {            // process Num-alike XP
         switch(token) {
           case "+","-","*","/",")":
             throw new Exception("Expecting Number or (, not <" ~ token ~ ">") ;
           case "(":
             opr.push(tokenXP) ;
             expectingOP = false ; break ;
           default: // number
             num.push(tokenXP) ;
             expectingOP = true ; 
         }
       } 
       xpHead = xpTail ;       
     } // end while              
     
     while (opr.length > 1) // join pending Op
       joinXP(opr.pop()) ;
       
   }catch(Exception e) {
     writefln("%s\n%s\n%s^", e.msg, xpr, repeat(" ", xpHead)) ;
     root = null ;
     return this ;
   }
 
   if(num.length != 1) { // should be one XP left
     writefln("Parse Error...") ;
     root = null ;
   } else
     root = num.pop() ;
   return this ;
 } // end Parse

} // end class AST

// for display AST fancy struct void ins(inout char[][] s, string v, int p, int l) {

 while(s.length < l + 1) s.length = s.length + 1 ;
 while(s[l].length < p + v.length + 1) s[l] ~= " " ;
 s[l][p..p +v.length] = v ;

}

class calcVis : Visitor {

 int result, level = 0 ;
 string Result = null ;
 char[][] Tree = null ;
 static void opCall(AST a) {
   if (a && a.root) {
     calcVis c = new calcVis ;
     a.root.accept(c) ;
     for(int i = 1; i < c.Tree.length ; i++) { // more fancy
       bool flipflop = false ; char mk = '.' ;
       for(int j = 0 ; j < c.Tree[i].length ; j++) {
         while(j >= c.Tree[i-1].length) c.Tree[i-1] ~= " " ;         
         char c1 = c.Tree[i][j] ; char c2 = c.Tree[i-1][j] ;
         if(flipflop && (c1 == ' ') && c2 == ' ')
           c.Tree[i-1][j] = mk ;
         if(c1 != mk && c1 != ' ' && (j == 0 || !isdigit(c.Tree[i][j-1])))
           flipflop = !flipflop ;
       }
     }
     foreach(t; c.Tree) writefln(t) ;
     writefln("%s ==>\n%s = %s", a.xpr,c.Result,c.result) ;
   } else
     writefln("Evalute invalid or null Expression") ;
 }
 void visit(XP xp) {// calc. the value, display AST struct and eval order.
   ins(Tree, xp.str, xp.pos, level) ;
   level++ ;
   if (xp.type == Num) {
     Result ~= xp.str ;
     result = toInt(xp.str) ;
   } else {
     Result ~= "(" ;
     xp.LHS.accept(this) ;
     int lhs = result ; 
     Result ~= opChar[xp.type] ;
     xp.RHS.accept(this) ;
     Result ~= ")" ;
     switch(xp.type) {
       case Add: result = lhs + result ; break ;
       case Sub: result = lhs - result ; break ;
       case Mul: result = lhs * result ; break ;
       case Div: result = lhs / result ; break ;
       default: throw new Exception("Invalid type") ;
     }
   } // 
   level-- ;
 }

}

void main(string[] args) {

 string expression = args.length > 1 ? join(args[1..$]," ") : 
   "1 + 2*(3 - 2*(3 - 2)*((2 - 4)*5 - 22/(7 + 2*(3 - 1)) - 1)) + 1" ; // should be 60    
 calcVis((new AST).parse(expression)) ;

}</lang>

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

<lang e>def eParser := <elang:syntax.makeEParser> def LiteralExpr := <elang:evm.makeLiteralExpr>.asType() def arithEvaluate(expr :String) {

 def ast := eParser(expr)
 
 def evalAST(ast) {
   return switch (ast) {
     match e`@a + @b` { evalAST(a) + evalAST(b) }
     match e`@a - @b` { evalAST(a) - evalAST(b) }
     match e`@a * @b` { evalAST(a) * evalAST(b) }
     match e`@a / @b` { evalAST(a) / evalAST(b) }
     match e`-@a` { -(evalAST(a)) }
     match l :LiteralExpr { l.getValue() }
   }
 }
 
 return evalAST(ast)

}</lang>

Parentheses are handled by the parser.

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

value: 3

? arithEvaluate("(1 + 2) * 10 / 100")

value: 0.3

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

value: 20.0</lang>

Elena

<lang elena>#define std'dictionary'*.

define std'basic'*.
define std'patterns'*.
define ext'io'*.
define ext'convertors'*.

subject parse_order.

class Token

{

   #field theValue.
   
   #method parse_order'get = 0.
   
   #method += aChar
   [
       theValue += aChar.
   ]
   
   #method + aNode
   [
       ^ aNode += self.
   ]
   
   #method new
   [
       theValue := String.
   ]
   
   #method numeric = theValue~EReal64Convertor numeric.

}

class Node

{

   #field theLeft.
   #field theRight.
   
   #role Empty
   {
       #method += aNode
       [
           theLeft := aNode.            
           $self $setLeftAssigned.
       ]
   }
   
   #role LeftAssigned
   {
       #method += aNode
       [
           theRight := aNode.
           #shift.
       ]
   }
   
   #method $setLeftAssigned
   [
       #shift LeftAssigned.
   ]

   #method + aNode
   [
       #if (self parse_order > aNode parse_order)?
       [
           self += aNode.
       ]
       | [
           aNode += self.            
           ^ aNode.
       ].
   ]
       
   #method += aNode
   [
       #if (theRight parse_order > aNode parse_order)?
       [
           theRight += aNode.
       ]
       | [
           theRight := aNode += theRight.
       ].        
   ]
   
   #method new
   [
       #shift Empty.
   ]

}

class SummaryNode (Node)

{

   #method parse_order'get = 2.
   
   #method numeric = theLeft numeric + theRight numeric.

}

class DifferenceNode (Node)

{

   #method parse_order'get = 2.
   
   #method numeric = theLeft numeric - theRight numeric.

}

class ProductNode (Node)

{

   #method parse_order'get = 1.
   
   #method numeric = theLeft numeric * theRight numeric.

}

class FractionNode (Node)

{

   #method parse_order'get = 1.
   
   #method numeric = theLeft numeric / theRight numeric.

}

class SubExpression

{

   #field theParser.
   #field theCounter.
   
   #role EOF
   {
       #method eof'is []
       
       #method += aChar [ $self fail. ]
   }
   
   #method parse_order'get = 0.
   
   #method + aNode
   [
       ^ aNode += self.
   ]
   
   #method append : aChar
   [
       #var aCode := Int32Value::aChar.
       #if control if:(aCode == 41)
       [
           theCounter -= 1.
       ]
       | if:(aCode == 40)
       [
           theCounter += 1.
       ].
       #if(theCounter == 0)?
           [ #shift EOF. ^ $self. ].
       theParser evaluate:aChar.
   ]
   
   #method numeric = theParser numeric.
   
   #method new
   [
       theParser := arithmeval'Parser.
       theCounter := Integer << 1.
   ]

}

class Parser

{

   #field theToken.
   #field theTopNode.
   
   #role Start
   {
       #method evaluate : aChar
       [
           #if (40 == aChar)?
           [
               theToken := SubExpression.
               theTopNode := theToken.
               $self $setBrackets.
           ]
           | [
               theToken := Token.
               theTopNode := theToken.
               theToken += aChar.
               #shift.
           ].
       ]
   }
   
   #role Brackets
   {
       #method evaluate : aChar
       [
           theToken += aChar.
           
           #if theToken eof'is
           [
               #shift.
           ].
       ]
   }
   
   #role Operator
   {
       #method evaluate : aChar
       [
           #if Control if:(48 < aChar) if:(58 > aChar)
           [
               theToken := (Token += aChar).
               
               theTopNode += theToken.
               
               #shift.
           ]
           | if:(40 == aChar)
           [
               theToken := SubExpression.
               theTopNode += theToken.
               
               #shift Brackets.
           ]
           | [ $self fail. ].
       ]
   }
   
   #method numeric = theTopNode numeric.
   
   #method evaluate : aChar
   [
       #if Control if:(48 < aChar) if:(58 > aChar)
       [
           theToken += aChar.
       ]
       | if:(42 == aChar)  // *
       [
           theTopNode := theTopNode + ProductNode.
           
           #shift Operator.
       ]
       | if:(47 == aChar)  // /
       [
           theTopNode := theTopNode + FractionNode.
           
           #shift Operator.
       ]
       | if:(43 == aChar)  // +
       [
           theTopNode := theTopNode + SummaryNode.
           
           #shift Operator.
       ]
       | if:(45 == aChar)  // -
       [
           theTopNode := theTopNode + DifferenceNode.
           
           #shift Operator.
       ]
       | if:(40 == aChar)
       [
           theToken := SubExpression.
           theTopNode := theToken.
           
           #shift Brackets.
       ]
       | [ $self fail. ].
   ]
   
   #method new
   [
       #shift Start.
   ]
   
   #method $setBrackets
   [
       #shift Brackets.
   ]

}

symbol Program =>

[

   #var aText := String.
   
   #loop ((Console >> aText) length > 0)?
   [
       #var aParser := Parser.

       Console << "=" << aText then: aText =>
       [
           Scan::aText run:aParser.
           
           ^ aParser numeric.
       ]
       | << "Invalid Expression".
       
       Console << "%n".
   ].

]. </lang>

Factor

<lang factor>USING: accessors kernel locals math math.parser peg.ebnf ; IN: rosetta.arith

TUPLE: operator left right ; TUPLE: add < operator ; C: <add> add TUPLE: sub < operator ; C: _{sub
TUPLE: mul < operator ; C: <mul> mul}

TUPLE: div < operator ; C:

div

EBNF: expr-ast spaces = [\n\t ]* digit = [0-9] number = (digit)+ => [[ string>number ]]

value = spaces number:n => n

          | spaces "(" exp:e spaces ")"    => e

fac = fac:a spaces "*" value:b => [[ a b <mul> ]]

| fac:a spaces "/" value:b => [[ a b

]]

          | value

exp = exp:a spaces "+" fac:b => [[ a b <add> ]]

          | exp:a spaces "-" fac:b         => [[ a b _{]]
          | fac}

main = exp:e spaces !(.) => e

EBNF

GENERIC: eval-ast ( ast -- result )

M: number eval-ast ;

recursive-eval ( ast -- left-result right-result )

   [ left>> eval-ast ] [ right>> eval-ast ] bi ;

M: add eval-ast recursive-eval + ; M: sub eval-ast recursive-eval - ; M: mul eval-ast recursive-eval * ; M: div eval-ast recursive-eval / ;

evaluate ( string -- result )

   expr-ast eval-ast ;</lang>

F#

Using FsLex and FsYacc from the F# PowerPack, we implement this with multiple source files:

AbstractSyntaxTree.fs: <lang fsharp>module AbstractSyntaxTree

type Expression =

 | Int    of int 
 | Plus   of Expression * Expression 
 | Minus  of Expression * Expression 
 | Times  of Expression * Expression 
 | Divide of Expression * Expression</lang>

Lexer.fsl: <lang fsharp>{ module Lexer

open Parser // we need the terminal tokens from the Parser

let lexeme = Lexing.LexBuffer<_>.LexemeString }

let intNum = '-'? ['0'-'9']+ let whitespace = ' ' | '\t' let newline = '\n' | '\r' '\n'

rule token = parse

   | intNum     { INT (lexeme lexbuf |> int) }
   | '+'        { PLUS }
   | '-'        { MINUS }
   | '*'        { TIMES }
   | '/'        { DIVIDE }
   | '('        { LPAREN }
   | ')'        { RPAREN }
   | whitespace { token lexbuf }
   | newline    { lexbuf.EndPos <- lexbuf.EndPos.NextLine; token lexbuf }
   | eof        { EOF }
   | _          { failwithf "unrecognized input: '%s'" <| lexeme lexbuf }</lang>

Parser.fsy: <lang fsharp>%{ open AbstractSyntaxTree %}

%start Expr

// terminal tokens %token <int> INT %token PLUS MINUS TIMES DIVIDE LPAREN RPAREN %token EOF

// associativity and precedences %left PLUS MINUS %left TIMES DIVIDE

// return type of Expr %type <Expression> Expr

%%

Expr: INT { Int $1 }

   | Expr PLUS Expr          { Plus ($1, $3) } 
   | Expr MINUS Expr         { Minus ($1, $3) } 
   | Expr TIMES Expr         { Times ($1, $3) } 
   | Expr DIVIDE Expr        { Divide ($1, $3) } 
   | LPAREN Expr RPAREN      { $2 } </lang>

Program.fs: <lang fsharp>open AbstractSyntaxTree open Lexer open Parser

let parse txt =

 txt
 |> Lexing.LexBuffer<_>.FromString
 |> Parser.Expr Lexer.token

let rec eval = function

 | Int i        -> i
 | Plus (a,b)   -> eval a + eval b
 | Minus (a,b)  -> eval a - eval b
 | Times (a,b)  -> eval a * eval b
 | Divide (a,b) -> eval a / eval b

do

 "((11+15)*15)*2-(3)*4*1"
 |> parse 
 |> eval
 |> printfn "%d"</lang>

Go

See Arithmetic Evaluator/Go

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 = groupByParens(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(expr.size())
   tokens

}

List groupByParens(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 = groupByParens(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 } try { testParse('/ 1 /') } catch (e) { println e }</lang>

Output:

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: Invalid constant '+' near position 3
java.lang.IllegalArgumentException: Cannot parse expression: The operand/operator sequence is wrong
java.lang.IllegalArgumentException: Cannot parse expression: The operand/operator sequence is wrong

Haskell

<lang haskell>import Text.ParserCombinators.Parsec import Text.ParserCombinators.Parsec.Expr

data Exp = Num Int

        | Add Exp Exp
        | Sub Exp Exp
        | Mul Exp Exp
        | Div Exp Exp

expr = buildExpressionParser table factor

table = [[op "*" (Mul) AssocLeft, op "/" (Div) AssocLeft]

       ,[op "+" (Add) AssocLeft, op "-" (Sub) AssocLeft]]
       where op s f assoc = Infix (do string s; return f) assoc

factor = do char '(' ; x <- expr ; char ')'

            return x 
     <|> do ds <- many1 digit
            return $ Num (read ds)

evaluate (Num x) = fromIntegral x evaluate (Add a b) = (evaluate a) + (evaluate b) evaluate (Sub a b) = (evaluate a) - (evaluate b) evaluate (Mul a b) = (evaluate a) * (evaluate b) evaluate (Div a b) = (evaluate a) `div` (evaluate b)

solution exp = case parse expr [] exp of

                Right expr -> evaluate expr
                Left _ -> error "Did not parse"</lang>

Icon and Unicon

A compact recursive descent parser using Hanson's device. This program

handles left and right associativity and different precedences
is ready to handle any number of infix operators without adding more functions to handle the precedences
accepts integers, reals, and radix constants (e.g. 3r10 is 3 in base 3)
currently accepts the Icon operators + - * / % (remainder) and ^ (exponentiation) and unary operators + and -
string invocation is used to evaluate binary operators hence other Icon binary operators (including handle multiple character ones) can be easily added
uses Icon style type coercion on operands
represents the AST as a nested list eliminating unneeded parenthesis

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

<lang Icon>procedure main() #: simple arithmetical parser / evaluator

  write("Usage: Input expression = Abstract Syntax Tree = Value, ^Z to end.")
  repeat {
     writes("Input expression : ")
     if not writes(line := read()) then break
     if map(line) ? { (x := E()) & pos(0) } then
        write(" = ", showAST(x), " = ", evalAST(x))
     else
        write(" rejected")
  }

end

procedure evalAST(X) #: return the evaluated AST

  local x

  if type(X) == "list" then {
     x := evalAST(get(X))
     while x := get(X)(x, evalAST(get(X) | stop("Malformed AST.")))
  }
  return \x | X

end

procedure showAST(X) #: return a string representing the AST

  local x,s

  s := ""
  every x := !X do
     s ||:= if type(x) == "list" then "(" || showAST(x) || ")" else x
  return s

end

When you're writing a big parser, a few utility recognisers are very useful

procedure ws() # skip optional whitespace

  suspend tab(many(' \t')) | ""

end

procedure digits()

  suspend tab(many(&digits))

end

procedure radixNum(r) # r sets the radix

  static chars
  initial chars := &digits || &lcase
  suspend tab(many(chars[1 +: r]))

end

global token record HansonsDevice(precedence,associativity)

procedure opinfo()

  static O
  initial {
     O := HansonsDevice([], table(&null))                         # parsing table
     put(O.precedence, ["+", "-"], ["*", "/", "%"], ["^"])        # Lowest to Highest precedence
     every O.associativity[!!O.precedence] := 1                   # default to 1 for LEFT associativity
     O.associativity["^"] := 0                                    # RIGHT associativity
  }
  return O

end

procedure E(k) #: Expression

  local lex, pL
  static opT
  initial opT := opinfo()

  /k := 1
  lex := []
  if not (pL := opT.precedence[k]) then                        # this op at this level?
     put(lex, F())
  else {
     put(lex, E(k + 1))
     while ws() & put(lex, token := =!pL) do
        put(lex, E(k + opT.associativity[token]))
  }
  suspend if *lex = 1 then lex[1] else lex                     # strip useless []

end

procedure F() #: Factor

  suspend ws() & (    # skip optional whitespace, and ...
     (="+" & F())              |          # unary + and a Factor, or ...
     (="-" || V())             |          # unary - and a Value, or ...
     (="-" & [-1, "*", F()])   |          # unary - and a Factor, or ...
    2(="(", E(), ws(), =")")   |          # parenthesized subexpression, or ...
      V()                                 # just a value
  )

end

procedure V() #: Value

  local r
  suspend ws() & numeric(    # skip optional whitespace, and ...
      =(r := 1 to 36) || ="r" || radixNum(r)             |     # N-based number, or ...
      digits() || (="." || digits() | "") || exponent()        # plain number with optional fraction
  )

end

procedure exponent()

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

end</lang>

Sample Output:

#matheval.exe 

Usage: Input expression = Abstract Syntax Tree = Value, ^Z to end.
Input expression : 1
1 = 1 = 1
Input expression : -1
-1 = -1 = -1
Input expression : (-15/2.0)
(-15/2.0) = -15/2.0 = -7.5
Input expression : -(15/2.0)
-(15/2.0) = -1*(15/2.0) = -7.5
Input expression : 2+(3-4)*6/5^2^3%3
2+(3-4)*6/5^2^3%3 = 2+((3-4)*6/(5^(2^3))%3) = 2
Input expression : 1+2+3+4
1+2+3+4 = 1+2+3+4 = 10
Input expression : ((((2))))+3*5
((((2))))+3*5 = 2+(3*5) = 17
Input expression : 3r10*3
3r10*3 = 3r10*3 = 9
Input expression : ^Z

J

Note that once you get beyond a few basic arithmetic operations, what we commonly call "mathematical precedence" stops making sense, and primary value for this kind of precedence has been that it allows polynomials to be expressed simply (but expressing polynomials as a sequence of coefficients, one for each exponent, is even simpler).

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

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

<lang j>parse=:parse_parser_ eval=:monad define

 'gerund structure'=:y
 gerund@.structure

)

coclass 'parser' classify=: '$()*/+-'&(((>:@#@[ # 2:) #: 2 ^ i.)&;:)

rules=: patterns=: ,"0 assert 1

addrule=: dyad define

  rules=: rules,;:x
  patterns=: patterns,+./@classify"1 y

)

'Term' addrule '$()', '0', '+-',: '0' 'Factor' addrule '$()+-', '0', '*/',: '0' 'Parens' addrule '(', '*/+-0', ')',: ')*/+-0$' rules=: rules,;:'Move'

buildTree=: monad define

 words=: ;:'$',y
 queue=: classify '$',y
 stack=: classify '$$$$'
 tokens=: ]&.>i.#words
 tree=: 
 while.(#queue)+.6<#stack do.
   rule=: rules {~ i.&1 patterns (*./"1)@:(+./"1) .(*."1)4{.stack
   rule`:6
 end.
 'syntax' assert 1 0 1 1 1 1 -: {:"1 stack
 gerund=: literal&.> (<,'%') (I. words=<,'/')} words
 gerund;1{tree

)

literal=:monad define ::]

 ".'t=.',y
 5!:1<'t'

)

Term=: Factor=: monad define

 stack=: ({.stack),(classify '0'),4}.stack
 tree=: ({.tree),(<1 2 3{tree),4}.tree

)

Parens=: monad define

 stack=: (1{stack),3}.stack
 tree=: (1{tree),3}.tree

)

Move=: monad define

 'syntax' assert 0<#queue
 stack=: ({:queue),stack
 queue=: }:queue
 tree=: ({:tokens),tree
 tokens=: }:tokens

)

parse=:monad define

 tmp=: conew 'parser'
 r=: buildTree__tmp y
 coerase tmp
 r

)</lang> example use: <lang j> eval parse '1+2*3/(4-5+6)' 2.2</lang>

You can also display the syntax tree, for example: <lang j> parse '2*3/(4-5)' ┌─────────────────────────────────────────────────────┬───────────────────┐ │┌───┬───────┬───┬───────┬───┬─┬───────┬───┬───────┬─┐│┌───────┬─┬───────┐│ ││┌─┐│┌─────┐│┌─┐│┌─────┐│┌─┐│(│┌─────┐│┌─┐│┌─────┐│)│││┌─┬─┬─┐│4│┌─┬─┬─┐││ │││$│││┌─┬─┐│││*│││┌─┬─┐│││%││ ││┌─┬─┐│││-│││┌─┬─┐││ ││││1│2│3││ ││6│7│8│││ ││└─┘│││0│2│││└─┘│││0│3│││└─┘│ │││0│4│││└─┘│││0│5│││ │││└─┴─┴─┘│ │└─┴─┴─┘││ ││ ││└─┴─┘││ ││└─┴─┘││ │ ││└─┴─┘││ ││└─┴─┘││ ││└───────┴─┴───────┘│ ││ │└─────┘│ │└─────┘│ │ │└─────┘│ │└─────┘│ ││ │ │└───┴───────┴───┴───────┴───┴─┴───────┴───┴───────┴─┘│ │ └─────────────────────────────────────────────────────┴───────────────────┘</lang>

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.

Java

Uses the BigRational class to handle arbitrary-precision numbers (rational numbers since basic arithmetic will result in rational values).

<lang java>import java.util.Stack;

public class ArithmeticEvaluation {

 public static enum Parentheses { LEFT, RIGHT }
 
 public static enum BinaryOperator
 {
   ADD('+', 1) {
     public BigRational eval(BigRational leftValue, BigRational rightValue) {  return leftValue.add(rightValue);  }
   },
   SUB('-', 1) {
     public BigRational eval(BigRational leftValue, BigRational rightValue) {  return leftValue.subtract(rightValue);  }
   },
   MUL('*', 2) {
     public BigRational eval(BigRational leftValue, BigRational rightValue) {  return leftValue.multiply(rightValue);  }
   },
   DIV('/', 2) {
     public BigRational eval(BigRational leftValue, BigRational rightValue) {  return leftValue.divide(rightValue);  }
   };
   
   public final char symbol;
   public final int precedence;
   
   BinaryOperator(char symbol, int precedence)
   {
     this.symbol = symbol;
     this.precedence = precedence;
   }
   
   public abstract BigRational eval(BigRational leftValue, BigRational rightValue);
 }
 
 public static class BinaryExpression
 {
   public Object leftOperand = null;
   public BinaryOperator operator = null;
   public Object rightOperand = null;
   
   public BinaryExpression(Object leftOperand, BinaryOperator operator, Object rightOperand)
   {
     this.leftOperand = leftOperand;
     this.operator = operator;
     this.rightOperand = rightOperand;
   }
   
   public BigRational eval()
   {
     BigRational leftValue = (leftOperand instanceof BinaryExpression) ? ((BinaryExpression)leftOperand).eval() : (BigRational)leftOperand;
     BigRational rightValue = (rightOperand instanceof BinaryExpression) ? ((BinaryExpression)rightOperand).eval() : (BigRational)rightOperand;
     return operator.eval(leftValue, rightValue);
   }
   
   public String toString()
   {  return "(" + leftOperand + " " + operator.symbol + " " + rightOperand + ")";  }
 }
 
 public static void createNewOperand(BinaryOperator operator, Stack<Object> operands)
 {
   Object rightOperand = operands.pop();
   operands.push(new BinaryExpression(operands.pop(), operator, rightOperand));
   return;
 }
 
 public static Object createExpression(String inputString)
 {
   int curIndex = 0;
   boolean afterOperand = false;
   Stack<Object> operands = new Stack<Object>();
   Stack<Object> operators = new Stack<Object>();

inputStringLoop:

   while (curIndex < inputString.length())
   {
     int startIndex = curIndex;
     char c = inputString.charAt(curIndex++);
     if (Character.isWhitespace(c))
       continue;
     if (afterOperand)
     {
       if (c == ')')
       {
         Object operator = null;
         while (!operators.isEmpty() && ((operator = operators.pop()) != Parentheses.LEFT))
           createNewOperand((BinaryOperator)operator, operands);
         continue;
       }
       afterOperand = false;
       for (BinaryOperator operator : BinaryOperator.values())
       {
         if (c == operator.symbol)
         {
           while (!operators.isEmpty() && (operators.peek() != Parentheses.LEFT) && (((BinaryOperator)operators.peek()).precedence >= operator.precedence))
             createNewOperand((BinaryOperator)operators.pop(), operands);
           operators.push(operator);
           continue inputStringLoop;
         }
       }
       throw new IllegalArgumentException();
     }
     if (c == '(')
     {
       operators.push(Parentheses.LEFT);
       continue;
     }
     afterOperand = true;
     while (curIndex < inputString.length())
     {
       c = inputString.charAt(curIndex);
       if (((c < '0') || (c > '9')) && (c != '.'))
         break;
       curIndex++;
     }
     operands.push(BigRational.valueOf(inputString.substring(startIndex, curIndex)));
   }
   
   while (!operators.isEmpty())
   {
     Object operator = operators.pop();
     if (operator == Parentheses.LEFT)
       throw new IllegalArgumentException();
     createNewOperand((BinaryOperator)operator, operands);
   }
   Object expression = operands.pop();
   if (!operands.isEmpty())
     throw new IllegalArgumentException();
   return expression;
 }
 
 public static void main(String[] args)
 {
   String[] testExpressions = { "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" };
   for (String testExpression : testExpressions)
   {
     Object expression = createExpression(testExpression);
     System.out.println("Input: \"" + testExpression + "\", AST: \"" + expression + "\", eval=" + (expression instanceof BinaryExpression ? ((BinaryExpression)expression).eval() : expression));
   }
 }

}</lang>

Output:

Input: "2+3", AST: "(2 + 3)", eval=5
Input: "2+3/4", AST: "(2 + (3 / 4))", eval=11/4
Input: "2*3-4", AST: "((2 * 3) - 4)", eval=2
Input: "2*(3+4)+5/6", AST: "((2 * (3 + 4)) + (5 / 6))", eval=89/6
Input: "2 * (3 + (4 * 5 + (6 * 7) * 8) - 9) * 10", AST: "((2 * ((3 + ((4 * 5) + ((6 * 7) * 8))) - 9)) * 10)", eval=7000
Input: "2*-3--4+-.25", AST: "(((2 * -3) - -4) + -1/4)", eval=-9/4

JavaScript

Numbers must have a digit before the decimal point, so 0.1 not .1.

Spaces are removed, expressions like 5--1 are treated as 5 - -1

<lang javascript>function evalArithmeticExp(s) {

 s = s.replace(/\s/g,).replace(/^\+/,);
 var rePara = /\([^\(\)]*\)/;
 var exp = s.match(rePara);

 while (exp = s.match(rePara)) {
   s = s.replace(exp[0], evalExp(exp[0]));
 }
 return evalExp(s);
 
 function evalExp(s) {
   s = s.replace(/[\(\)]/g,);
   var reMD = /\d+\.?\d*\s*[\*\/]\s*[+-]?\d+\.?\d*/;
   var reM = /\*/;
   var reAS = /-?\d+\.?\d*\s*[\+-]\s*[+-]?\d+\.?\d*/;
   var reA  = /\d\+/;
   var exp;

   while (exp = s.match(reMD)) {
     s = exp[0].match(reM)? s.replace(exp[0], multiply(exp[0])) : s.replace(exp[0], divide(exp[0]));
   }
   
   while (exp = s.match(reAS)) {
     s = exp[0].match(reA)? s.replace(exp[0], add(exp[0])) : s.replace(exp[0], subtract(exp[0]));
   }
   
   return  + s;

   function multiply(s, b) {
     b = s.split('*');
     return b[0] * b[1];
   }
   
   function divide(s, b) {
     b = s.split('/');
     return b[0] / b[1];
   }
   
   function add(s, b) {
     s = s.replace(/^\+/,).replace(/\++/,'+');
     b = s.split('+');
     return Number(b[0]) + Number(b[1]);
   }
   
   function subtract(s, b) {
     s = s.replace(/\+-|-\+/g,'-');

     if (s.match(/--/)) {
       return add(s.replace(/--/,'+'));
     }
     b = s.split('-');
     return b.length == 3? -1 * b[1] - b[2] : b[0] - b[1];
   }
 }

}</lang>

Sample output:

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

Lua

<lang lua>require"lpeg"

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

--matches arithmetic expressions and returns a syntax tree expression = P{"expr"; ws = P" "^0, number = C(R"09"^1) * V"ws", lp = "(" * V"ws", rp = ")" * V"ws", sym = C(S"+-*/") * V"ws", more = (V"sym" * V"expr")^0, expr = V"number" * V"more" + V"lp" * lpeg.Ct(V"expr" * V"more") * V"rp" * V"more"}

--evaluates a tree function eval(expr)

 --empty
 if type(expr) == "string" or type(expr) == "number" then return expr + 0 end
 
 --arithmetic functions
 tb = {["+"] = function(a,b) return eval(a) + eval(b) end,

["-"] = function(a,b) return eval(a) - eval(b) end, ["*"] = function(a,b) return eval(a) * eval(b) end, ["/"] = function(a,b) return eval(a) / eval(b) end}

 --you could add ^ or other operators to this pretty easily
 for i, v in ipairs{"*/", "+-"} do
   for s, u in ipairs(expr) do

local k = type(u) == "string" and C(S(v)):match(u) if k then expr[s-1] = tb[k](expr[s-1],expr[s+1]) table.remove(expr, s) table.remove(expr, s) end end

 end
 return expr[1]

end

print(eval{expression:match(io.read())})</lang>

OCaml

<lang ocaml>type expression =

 | Const of float
 | Sum  of expression * expression   (* e1 + e2 *)
 | Diff of expression * expression   (* e1 - e2 *)
 | Prod of expression * expression   (* e1 * e2 *)
 | Quot of expression * expression   (* e1 / e2 *)

let rec eval = function

 | Const c -> c
 | Sum (f, g) -> eval f +. eval g
 | Diff(f, g) -> eval f -. eval g
 | Prod(f, g) -> eval f *. eval g
 | Quot(f, g) -> eval f /. eval g

open Genlex

let lexer = make_lexer ["("; ")"; "+"; "-"; "*"; "/"]

let rec parse_expr = parser

    [< e1 = parse_mult; e = parse_more_adds e1 >] -> e
and parse_more_adds e1 = parser
    [< 'Kwd "+"; e2 = parse_mult; e = parse_more_adds (Sum(e1, e2)) >] -> e
  | [< 'Kwd "-"; e2 = parse_mult; e = parse_more_adds (Diff(e1, e2)) >] -> e
  | [< >] -> e1
and parse_mult = parser
    [< e1 = parse_simple; e = parse_more_mults e1 >] -> e
and parse_more_mults e1 = parser
    [< 'Kwd "*"; e2 = parse_simple; e = parse_more_mults (Prod(e1, e2)) >] -> e
  | [< 'Kwd "/"; e2 = parse_simple; e = parse_more_mults (Quot(e1, e2)) >] -> e
  | [< >] -> e1
and parse_simple = parser
  | [< 'Int i >] -> Const(float i)
  | [< 'Float f >] -> Const f
  | [< 'Kwd "("; e = parse_expr; 'Kwd ")" >] -> e

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

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

Using the function read_expression in an interactive loop:

<lang ocaml>let () =

 while true do
   print_string "Expression: ";
   let str = read_line() in
   if str = "q" then exit 0;
   let expr = read_expression str in
   let res = eval expr in
   Printf.printf " = %g\n%!" res;
 done</lang>

Compile with:

ocamlopt -pp camlp4o arith_eval.ml -o arith_eval.opt

Oz

We can create a simple, but slow parser using logic programming. Every procedure reads the input characters from X0 and returns the remaining characters in X. The AST is returned as the regular return value.

The Do procedure automatically threads the input state through a sequence of procedure calls.

<lang oz>declare

 fun {Expr X0 ?X}
    choice
       [L _ R] = {Do [Term &+ Expr] X0 ?X} in add(L R)
    [] [L _ R] = {Do [Term &- Expr] X0 ?X} in sub(L R)
    [] {Term X0 X}
    end
 end

 fun {Term X0 ?X}
    choice
       [L _ R] = {Do [Factor &* Term] X0 ?X} in mul(L R)
    [] [L _ R] = {Do [Factor &/ Term] X0 ?X} in 'div'(L R)
    [] {Factor X0 X}
    end
 end

 fun {Factor X0 ?X}
    choice {Parens Expr X0 X}
    [] {Number X0 X}
    end
 end

 fun {Number X0 X}
    Ds = {Many1 Digit X0 X}
 in
    num(Ds)
 end

 fun {Digit X0 ?X}
    D|!X = X0
 in
    D = choice &0 [] &1 [] &2 [] &3 [] &4 [] &5 [] &6 [] &7 [] &8 [] &9 end 
 end

 fun {Many1 Rule X0 ?X}
    choice [{Rule X0 X}]
    [] X1 in {Rule X0 X1}|{Many1 Rule X1 X}
    end
 end

 fun {Parens Rule X0 ?X}
    [_ R _] = {Do [&( Rule &)] X0 X}
 in
    R
 end

 fun {Do Rules X0 ?X}
    Res#Xn = {FoldL Rules
              fun {$ Res#Xi Rule}
                 if {Char.is Rule} then
                    !Rule|X2 = Xi
                 in
                    (Rule|Res) # X2
                 elseif {Procedure.is Rule} then
                    X2 in
                    ({Rule Xi X2}|Res) # X2
                 end
              end
              nil#X0}
 in
    X = Xn
    {Reverse Res}
 end

 %% Returns a singleton list if an AST was found or nil otherwise.
 fun {Parse S}
    {SearchOne fun {$} {Expr S nil} end}
 end

 fun {Eval X}
    case X of
       num(Ds)    then {String.toInt Ds}
    [] add(L R)   then {Eval L} + {Eval R}
    [] sub(L R)   then {Eval L} - {Eval R}
    [] mul(L R)   then {Eval L} * {Eval R}
    [] 'div'(L R) then {Eval L} div {Eval R}
    end
 end

 [AST] = {Parse "((11+15)*15)*2-(3)*4*1"}

in

 {Inspector.configure widgetShowStrings true}
 {Inspect AST}
 {Inspect {Eval AST}}</lang>

To improve performance, the number of choice points should be limited, for example by reading numbers deterministically instead. For real parsing with possible large input, it is however recommended to use Gump, Mozart's parser generator.

Pascal

See Arithmetic Evaluator/Pascal.

Perl

<lang perl>sub ev

Evaluates an arithmetic expression like "(1+3)*7" and returns
its value.

{my $exp = shift;
 # Delete all meaningless characters. (Scientific notation,
 # infinity, and not-a-number aren't supported.)
 $exp =~ tr {0-9.+-/*()} {}cd;
 return ev_ast(astize($exp));}

{my $balanced_paren_regex;
 $balanced_paren_regex = qr
    {\( ( [^()]+ | (??{$balanced_paren_regex}) )+ \)}x;
 # ??{ ... } interpolates lazily (only when necessary),
 # permitting recursion to arbitrary depths.
 
 sub astize
 # Constructs an abstract syntax tree by recursively
 # transforming textual arithmetic expressions into array
 # references of the form [operator, left oprand, right oprand].
  {my $exp = shift;
   # If $exp is just a number, return it as-is.
   $exp =~ /[^0-9.]/ or return $exp;
   # If parentheses surround the entire expression, get rid of
   # them.
   $exp = substr($exp, 1, -1)
       while $exp =~ /\A($balanced_paren_regex)\z/;
   # Replace stuff in parentheses with placeholders.
   my @paren_contents;
   $exp =~ s {($balanced_paren_regex)}
             {push(@paren_contents, $1);
              "[p$#paren_contents]"}eg;
   # Scan for operators in order of increasing precedence,
   # preferring the rightmost.
   $exp =~ m{(.+) ([+-]) (.+)}x or
       $exp =~ m{(.+) ([*/]) (.+)}x or
       # The expression must've been malformed somehow.
       # (Note that unary minus isn't supported.)
       die "Eh?: [$exp]\n";
   my ($op, $lo, $ro) = ($2, $1, $3);
   # Restore the parenthetical expressions.
   s {\[p(\d+)\]} {($paren_contents[$1])}eg
       foreach $lo, $ro;
   # And recurse.
   return [$op, astize($lo), astize($ro)];}}

{my %ops =
    ('+' => sub {$_[0] + $_[1]},
     '-' => sub {$_[0] - $_[1]},
     '*' => sub {$_[0] * $_[1]},
     '/' => sub {$_[0] / $_[1]});
 
 sub ev_ast
 # Evaluates an abstract syntax tree of the form returned by
 # &astize.
  {my $ast = shift;
   # If $ast is just a number, return it as-is.
   ref $ast or return $ast;
   # Otherwise, recurse.
   my ($op, @operands) = @$ast;
   $_ = ev_ast($_) foreach @operands;
   return $ops{$op}->(@operands);}}</lang>

Perl 6

Works with: Rakudo version #22 "Thousand Oaks"

<lang perl6>sub ev (Str $s --> Num) {

   grammar expr {
       token TOP { ^ <sum> $ }
       token sum { <product> (('+' || '-') <product>)* }
       token product { <factor> (('*' || '/') <factor>)* }
       token factor { <unary_minus>? [ <parens> || <literal> ] }
       token unary_minus { '-' }
       token parens { '(' <sum> ')' }
       token literal { \d+ ['.' \d+]? || '.' \d+ }
   }
   
   my sub minus ($b) { $b ?? -1 !! +1 }

   my sub sum ($x) {
       [+] product($x<product>), map
           { minus($^y[0] eq '-') * product $^y<product> },
           |($x[0] or [])
   }
   
   my sub product ($x) {
       [*] factor($x<factor>), map
           { factor($^y<factor>) ** minus($^y[0] eq '/') },
           |($x[0] or [])
   }
   
   my sub factor ($x) {
       minus($x<unary_minus>) * ($x<parens>
         ?? sum $x<parens><sum>
         !! $x<literal>)
   }

   expr.parse([~] split /\s+/, $s);
   $/ or fail 'No parse.';
   sum $/<sum>;

}</lang>

Testing:

PicoLisp

The built-in function 'str' splits a string into a list of lexical tokens (numbers and transient symbols). From that, a recursive descendent parser can build an expression tree, resulting in directly executable Lisp code. <lang PicoLisp>(de ast (Str)

  (let *L (str Str "")
     (aggregate) ) )

(de aggregate ()

  (let X (product)
     (while (member (car *L) '("+" "-"))
        (setq X (list (intern (pop '*L)) X (product))) )
     X ) )

(de product ()

  (let X (term)
     (while (member (car *L) '("*" "/"))
        (setq X (list (intern (pop '*L)) X (term))) )
     X ) )

(de term ()

  (let X (pop '*L)
     (cond
        ((num? X) X)
        ((= "+" X) (term))
        ((= "-" X) (list '- (term)))
        ((= "(" X) (prog1 (aggregate) (pop '*L)))) ) ) )</lang>

Output: <lang PicoLisp>: (ast "1+2+3*-4/(1+2)") -> (+ (+ 1 2) (/ (* 3 (- 4)) (+ 1 2)))

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

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

Pop11

<lang pop11>/* Scanner routines */ /* Uncomment the following to parse data from standard input

vars itemrep; incharitem(charin) -> itemrep;

/

Current symbol

vars sym;

define get_sym();

   itemrep() -> sym;

enddefine;

define expect(x);

   lvars x;
   if x /= sym then
       printf(x, 'Error, expected %p\n');
       mishap(sym, 1, 'Example parser error');
   endif;
   get_sym();

enddefine;

lconstant res_list = [( ) + * ];

lconstant reserved = newproperty(

 maplist(res_list, procedure(x); [^x ^(true)]; endprocedure),
   20, false, "perm");

/*

 Parser for arithmetic expressions

/

/* expr: term

  | expr "+" term
  | expr "-" term
  ;

/

define do_expr() -> result;

   lvars result = do_term(), op;
   while sym = "+" or sym = "-" do
       sym -> op;
       get_sym();
       [^op ^result ^(do_term())] -> result;
   endwhile;

enddefine;

/* term: factor

  | term "*" factor
  | term "/" factor
  ;

/

define do_term() -> result;

   lvars result = do_factor(), op;
   while sym = "*" or sym = "/" do
       sym -> op;
       get_sym();
       [^op ^result ^(do_factor())] -> result;
   endwhile;

enddefine;

/* factor: word

  | constant
  | "(" expr ")"
  ;

/

define do_factor() -> result;

   if sym = "(" then
       get_sym();
       do_expr() -> result;
       expect(")");
   elseif isinteger(sym) or isbiginteger(sym) then
       sym -> result;
       get_sym();
   else
       if reserved(sym) then
           printf(sym, 'unexpected symbol %p\n');
           mishap(sym, 1, 'Example parser syntax error');
       endif;
       sym -> result;
       get_sym();
   endif;

enddefine;

/* Expression evaluator, returns false on error (currently only

  division by 0 */

define arith_eval(expr);

   lvars op, arg1, arg2;
   if not(expr) then
       return(expr);
   endif;
   if isinteger(expr) or isbiginteger(expr) then
       return(expr);
   endif;
   expr(1) -> op;
   arith_eval(expr(2)) -> arg1;
   arith_eval(expr(3)) -> arg2;
   if not(arg1) or not(arg2) then
       return(false);
   endif;
   if op = "+" then
       return(arg1 + arg2);
   elseif op = "-" then
       return(arg1 - arg2);
   elseif op = "*" then
       return(arg1 * arg2);
   elseif op = "/" then
       if arg2 = 0 then
           return(false);
       else
           return(arg1 div arg2);
       endif;
   else
       printf('Internal error\n');
       return(false);
   endif;

enddefine;

/* Given list, create item repeater. Input list is stored in a

  closure are traversed when new item is requested. */

define listitemrep(lst);

   procedure();
       lvars item;
       if lst = [] then
           termin;
       else
           front(lst) -> item;
           back(lst) -> lst;
           item;
        endif;
    endprocedure;

enddefine;

/* Initialise scanner */

listitemrep([(3 + 50) * 7 - 100 / 10]) -> itemrep;

get_sym();

Test it

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

Prolog

Works with: SWI Prolog

<lang prolog>% Lexer

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

lex1([], []).
lex1([40|Xs], ['('|Ys]) :- lex1(Xs, Ys).
lex1([41|Xs], [')'|Ys]) :- lex1(Xs, Ys).
lex1([43|Xs], ['+'|Ys]) :- lex1(Xs, Ys).
lex1([45|Xs], ['-'|Ys]) :- lex1(Xs, Ys).
lex1([42|Xs], ['*'|Ys]) :- lex1(Xs, Ys).
lex1([47|Xs], ['/'|Ys]) :- lex1(Xs, Ys).
lex1([X|Xs], [N|Ys]) :- numeric(X), N is X - 48, lex1(Xs, Ys).

lex2([], []).
lex2([X], [X]).
lex2([Xa,Xb|Xs], [Xa|Ys]) :- atom(Xa), lex2([Xb|Xs], Ys).
lex2([Xa,Xb|Xs], [Xa|Ys]) :- number(Xa), atom(Xb), lex2([Xb|Xs], Ys).
lex2([Xa,Xb|Xs], [Y|Ys]) :- number(Xa), number(Xb), N is Xa * 10 + Xb, lex2([N|Xs], [Y|Ys]).

% Parser
oper(1, *, X, Y, X * Y). oper(1, /, X, Y, X / Y).
oper(2, +, X, Y, X + Y). oper(2, -, X, Y, X - Y).

num(D) --> [D], {number(D)}.

expr(0, Z) --> num(Z).
expr(0, Z) --> {Z = (X)}, ['('], expr(2, X), [')'].

expr(N, Z) --> {succ(N0, N)}, {oper(N, Op, X, Y, Z)}, expr(N0, X), [Op], expr(N, Y).
expr(N, Z) --> {succ(N0, N)}, expr(N0, Z).

parse(Tokens, Expr) :- expr(2, Expr, Tokens, []).


% Evaluator
evaluate(E, E) :- number(E).
evaluate(A + B, E) :- evaluate(A, Ae), evaluate(B, Be), E is Ae + Be.
evaluate(A - B, E) :- evaluate(A, Ae), evaluate(B, Be), E is Ae - Be.
evaluate(A * B, E) :- evaluate(A, Ae), evaluate(B, Be), E is Ae * Be.
evaluate(A / B, E) :- evaluate(A, Ae), evaluate(B, Be), E is Ae / Be.

% Solution
calculator(String, Value) :-
   lex1(String, Tokens1),
   lex2(Tokens1, Tokens2),
   parse(Tokens2, Expression),
   evaluate(Expression, Value).

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

Python

There are python modules, such as Ply, which facilitate the implementation of parsers. This example, however, uses only standard Python with the parser having two stacks, one for operators, one for operands.
A subsequent example uses Pythons' ast module to generate the abstract syntax tree.

<lang python>import operator

class AstNode(object):

  def __init__( self, opr, left, right ):
     self.opr = opr
     self.l = left
     self.r = right

  def eval(self):
     return self.opr(self.l.eval(), self.r.eval())

class LeafNode(object):

  def __init__( self, valStrg ):
     self.v = int(valStrg)

  def eval(self):
     return self.v

class Yaccer(object):

  def __init__(self):
     self.operstak = []
     self.nodestak =[]
     self.__dict__.update(self.state1)

  def v1( self, valStrg ):
     # Value String
     self.nodestak.append( LeafNode(valStrg))
     self.__dict__.update(self.state2)
     #print 'push', valStrg

  def o2( self, operchar ):
     # Operator character or open paren in state1
     def openParen(a,b):
        return 0		# function should not be called

     opDict= { '+': ( operator.add, 2, 2 ),
        '-': (operator.sub, 2, 2 ),
        '*': (operator.mul, 3, 3 ),
        '/': (operator.div, 3, 3 ),
        '^': ( pow,         4, 5 ),  # right associative exponentiation for grins
        '(': ( openParen,   0, 8 )
        }
     operPrecidence = opDict[operchar][2]
     self.redeuce(operPrecidence)

     self.operstak.append(opDict[operchar])
     self.__dict__.update(self.state1)
     # print 'pushop', operchar

  def syntaxErr(self, char ):
     # Open Parenthesis 
     print 'parse error - near operator "%s"' %char

  def pc2( self,operchar ):
     # Close Parenthesis
     # reduce node until matching open paren found 
     self.redeuce( 1 )
     if len(self.operstak)>0:
        self.operstak.pop()		# pop off open parenthesis
     else:
        print 'Error - no open parenthesis matches close parens.'
     self.__dict__.update(self.state2)

  def end(self):
     self.redeuce(0)
     return self.nodestak.pop()

  def redeuce(self, precidence):
     while len(self.operstak)>0:
        tailOper = self.operstak[-1]
        if tailOper[1] < precidence: break

        tailOper = self.operstak.pop()
        vrgt = self.nodestak.pop()
        vlft= self.nodestak.pop()
        self.nodestak.append( AstNode(tailOper[0], vlft, vrgt))
        # print 'reduce'

  state1 = { 'v': v1, 'o':syntaxErr, 'po':o2, 'pc':syntaxErr }
  state2 = { 'v': syntaxErr, 'o':o2, 'po':syntaxErr, 'pc':pc2 }

def Lex( exprssn, p ):

  bgn = None
  cp = -1
  for c in exprssn:
     cp += 1
     if c in '+-/*^()':         # throw in exponentiation (^)for grins
        if bgn is not None:
           p.v(p, exprssn[bgn:cp])
           bgn = None
        if c=='(': p.po(p, c)
        elif c==')':p.pc(p, c)
        else: p.o(p, c)
     elif c in ' \t':
        if bgn is not None:
           p.v(p, exprssn[bgn:cp])
           bgn = None
     elif c in '0123456789':
        if bgn is None:
           bgn = cp
     else:
        print 'Invalid character in expression'
        if bgn is not None:
           p.v(p, exprssn[bgn:cp])
           bgn = None
        
  if bgn is not None:
     p.v(p, exprssn[bgn:cp+1])
     bgn = None
  return p.end()

expr = raw_input("Expression:") astTree = Lex( expr, Yaccer()) print expr, '=',astTree.eval()</lang>

ast standard library module

Python comes with its own 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. <lang python>>>> import ast >>> >>> expr="2 * (3 -1) + 2 * 5" >>> node = ast.parse(expr, mode='eval') >>> print(ast.dump(node).replace(',', ',\n')) Expression(body=BinOp(left=BinOp(left=Num(n=2),

op=Mult(),
right=BinOp(left=Num(n=3),
op=Sub(),
right=Num(n=1))),
op=Add(),
right=BinOp(left=Num(n=2),
op=Mult(),
right=Num(n=5))))

>>> code_object = compile(node, filename='<string>', mode='eval') >>> eval(code_object) 14 >>> # lets modify the AST by changing the 5 to a 6 >>> node.body.right.right.n 5 >>> node.body.right.right.n = 6 >>> code_object = compile(node, filename='<string>', mode='eval') >>> eval(code_object) 16</lang>

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 <lang ruby>$op_priority = {"+" => 0, "-" => 0, "*" => 1, "/" => 1} $op_function = {

 "+" => lambda {|x, y| x + y},
 "-" => lambda {|x, y| x - y},
 "*" => lambda {|x, y| x * y},
 "/" => lambda {|x, y| x / y}}

class TreeNode

 attr_accessor :info, :left, :right

 def initialize(info)
   @info = info
 end

 def leaf?
   @left.nil? and @right.nil?
 end

 def to_s(order)
   if leaf?
     @info
   else
     left_s, right_s = @left.to_s(order), @right.to_s(order)

     strs = case order
            when :prefix then [@info, left_s, right_s]
            when :infix then [left_s, @info, right_s]
            when :postfix then [left_s, right_s, @info]
            else []
            end
     
     "(" + strs.join(" ") + ")"
   end
 end

 def eval
   if !leaf? and operator?(@info)
     $op_function[@info].call(@left.eval, @right.eval)
   else
     @info.to_f
   end
 end

end

def tokenize(exp)

 exp
   .gsub('(', ' ( ')
   .gsub(')', ' ) ')
   .split(' ')

end

def operator?(token)

 $op_priority.has_key?(token)

end

def pop_connect_push(op_stack, node_stack)

 temp = op_stack.pop
 temp.right = node_stack.pop
 temp.left = node_stack.pop
 node_stack.push(temp)

end

def infix_exp_to_tree(exp)

 tokens = tokenize(exp)
 op_stack, node_stack = [], []

 tokens.each do |token|
   if operator?(token)
     # clear stack of higher priority operators
     until (op_stack.empty? or
            op_stack.last.info == "(" or
            $op_priority[op_stack.last.info] < $op_priority[token])
       pop_connect_push(op_stack, node_stack)
     end

     op_stack.push(TreeNode.new(token))
   elsif token == "("
     op_stack.push(TreeNode.new(token))
   elsif token == ")"
     while op_stack.last.info != "("
       pop_connect_push(op_stack, node_stack)
     end

     # throw away the '('
     op_stack.pop
   else
     node_stack.push(TreeNode.new(token))
   end
 end

 until op_stack.empty?
   pop_connect_push(op_stack, node_stack)
 end

 node_stack.last

end</lang> Testing: <lang ruby>exp = "1 + 2 - 3 * (4 / 6)" puts("Original: " + exp)

tree = infix_exp_to_tree(exp) puts("Prefix: " + tree.to_s(:prefix)) puts("Infix: " + tree.to_s(:infix)) puts("Postfix: " + tree.to_s(:postfix)) puts("Result: " + tree.eval.to_s)</lang> Output:

Original: 1 + 2 - 3 * (4 / 6)
Prefix: (- (+ 1 2) (* 3 (/ 4 6)))
Infix: ((1 + 2) - (3 * (4 / 6)))
Postfix: ((1 2 +) (3 (4 6 /) *) -)
Result: 1.0

Scala

This code shows a bit of Scala's parser classes. The error handling of parser errors is practically non-existent, to avoid obscuring the code.

<lang scala> package org.rosetta.arithmetic_evaluator.scala

object ArithmeticParser extends scala.util.parsing.combinator.RegexParsers {

 def readExpression(input: String) : Option[()=>Int] = {
   parseAll(expr, input) match {
     case Success(result, _) =>
       Some(result)
     case other =>
       println(other)
       None
   }
 }

 private def expr : Parser[()=>Int] = {
   (term<~"+")~expr ^^ { case l~r => () => l() + r() } |
   (term<~"-")~expr ^^ { case l~r => () => l() - r() } |
   term
 }

 private def term : Parser[()=>Int] = {
   (factor<~"*")~term ^^ { case l~r => () => l() * r() } |
   (factor<~"/")~term ^^ { case l~r => () => l() / r() } |
   factor
 }

 private def factor : Parser[()=>Int] = {
   "("~>expr<~")" |
   "\\d+".r ^^ { x => () => x.toInt } |
   failure("Expected a value")
 }

}

object Main {

 def main(args: Array[String]) {
   println("""Please input the expressions. Type "q" to quit.""")
   var input: String = ""

   do {
     input = readLine("> ")
     if (input != "q") {
       ArithmeticParser.readExpression(input).foreach(f => println(f()))
     }
   } while (input != "q")
 }

} </lang>

Example:

C:\Workset>scala org.rosetta.arithmetic_evaluator.scala.ArithmeticEvaluator
Please input the expressions. Type "q" to quit.
> 2+3*2
8
> (1+3)*7
28
> 1+a
[1.3] failure: Expected a number

1+a
  ^
> 2 + 2
4
> q

This example was made rather more complex by the requirement of generating an AST tree. With a Scala distribution there are many examples of arithmetic parsers, as small as half a dozen lines.

Tcl

Works with: Tcl version 8.5

The code below delivers the AST for an expression in a form that it can be immediately eval-led, using Tcl's prefix operators. <lang Tcl>namespace import tcl::mathop::*

proc ast str {

   # produce abstract syntax tree for an expression
   regsub -all {[-+*/()]} $str { & } str ;# "tokenizer"
   s $str

} proc s {args} {

   # parse "(a + b) * c + d" to "+ [* [+ a b] c] d"
   if {[llength $args] == 1} {set args [lindex $args 0]}
   if [regexp {[()]} $args] {
       eval s [string map {( "\[s " ) \]} $args]
   } elseif {"*" in $args} {

s [s_group $args *]

   } elseif {"/" in $args} {

s [s_group $args /]

   } elseif {"+" in $args} {
       s [s_group $args +]
   } elseif {"-" in $args} {
       s [s_group $args -]
   } else {
       string map {\{ \[ \} \]} [join $args]
   }

} proc s_group {list op} {

   # turn ".. a op b .." to ".. {op a b} .."
   set pos [lsearch -exact $list $op]
   set p_1 [- $pos 1]
   set p1  [+ $pos 1]
   lreplace $list $p_1 $p1 \
                 [list $op [lindex $list $p_1] [lindex $list $p1]]

}

-- Test suite

foreach test [split {

   ast 2-2
   ast 1-2-3
   ast (1-2)-3
   ast 1-(2-3)
   ast (1+2)*3
   ast (1+2)/3-4*5
   ast ((1+2)/3-4)*5

} \n] {

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

}</lang>

Output:

    ast 2-2 ..... - 2 2 ..... 0
    ast 1-2-3 ..... - [- 1 2] 3 ..... -4
    ast (1-2)-3 ..... - [- 1 2] 3 ..... -4
    ast 1-(2-3) ..... - 1 [- 2 3] ..... 2
    ast (1+2)*3 ..... * [+ 1 2] 3 ..... 9
    ast (1+2)/3-4*5 ..... - [/ [+ 1 2] 3] [* 4 5] ..... -19
    ast ((1+2)/3-4)*5 ..... * [- [/ [+ 1 2] 3] 4] 5 ..... -15

TXR

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

<lang txr>@(next :args) @(define space)@/ */@(end) @(define mulop (nod))@\

  @(local op)@\
  @(space)@\
  @(cases)@\
    @{op /[*]/}@(bind nod @(intern op *user-package*))@\
  @(or)@\
    @{op /\//}@(bind (nod) @(list 'trunc))@\
  @(end)@\
  @(space)@\

@(end) @(define addop (nod))@\

  @(local op)@(space)@{op /[+\-]/}@(space)@\
  @(bind nod @(intern op *user-package*))@\

@(end) @(define number (nod))@\

 @(local n)@(space)@{n /[0-9]+/}@(space)@\
 @(bind nod @(int-str n 10))@\

@(end) @(define factor (nod))@(cases)(@(expr nod))@(or)@(number nod)@(end)@(end) @(define term (nod))@\

 @(local op nod1 nod2)@\
 @(cases)@\
   @(factor nod1)@\
   @(cases)@(mulop op)@(term nod2)@(bind nod (op nod1 nod2))@\
   @(or)@(bind nod nod1)@\
   @(end)@\
 @(or)@\
   @(addop op)@(factor nod1)@\
   @(bind nod (op nod1))@\
 @(end)@\

@(end) @(define expr (nod))@\

 @(local op nod1 nod2)@\
 @(term nod1)@\
 @(cases)@(addop op)@(expr nod2)@(bind nod (op nod1 nod2))@\
 @(or)@(bind nod nod1)@\
 @(end)@\

@(end) @(cases) @ {source (expr e)} @ (output) source: @source AST: @(format nil "~s" e) value: @(eval e nil) @ (end) @(or) @ (maybe)@(expr e)@(end)@bad @ (output) erroneous suffix "@bad" @ (end) @(end)</lang>

Run:

$  txr expr-ast.txr '3 + 3/4 * (2 + 2) + (4*4)'
source: 3 + 3/4 * (2 + 2) + (4*4)
AST:    (+ 3 (+ (trunc 3 (* 4 (+ 2 2))) (* 4 4)))
value:  19

Ursala

with no error checking other than removal of spaces <lang Ursala>#import std

import nat
import flo

lex = ~=' '*~F+ rlc both -=digits # separate into tokens

parse = # build a tree

--<';'>; @iNX ~&l->rh ^/~&lt cases~&lhh\~&lhPNVrC {

  '*/': ^|C/~&hNV associate '*/',
  '+-': ^|C/~&hNV associate '*/+-',
  ');': @r ~&htitBPC+ associate '*/+-'}

associate "ops" = ~&tihdh2B-="ops"-> ~&thd2tth2hNCCVttt2C

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

evaluate = traverse+ parse+ lex</lang>

test program: <lang Ursala>#cast %eL

test = evaluate*t

-[ 1+1 4/5 2-1 3*7 3+4+5 9-2-4 7/3/2 4+2*3 5*2-1 5-3*2 (1+1)*(2+3) (2-4)/(3+5*(8-1))]-</lang> output:

<
   2.000000e+00,
   8.000000e-01,
   1.000000e+00,
   2.100000e+01,
   1.200000e+01,
   3.000000e+00,
   1.166667e+00,
   1.000000e+01,
   9.000000e+00,
   -1.000000e+00,
   1.000000e+01,
   -5.263158e-02>

Arithmetic evaluation

Ada

ALGOL 68

AutoHotkey

C

C++

Clojure

Common Lisp

D

E

Elena

Factor

F#

Go

Groovy

Haskell

Icon and Unicon

J

Java

JavaScript

Lua

OCaml

Oz

Pascal

Perl

Perl 6

PicoLisp

Pop11

Prolog

Python

ast standard library module

Ruby

Scala

Tcl

TXR

Ursala