Rosetta Code

Arithmetic evaluation: Difference between revisions

Page Discussion

Arithmetic evaluation (view source)

Revision as of 00:11, 7 October 2011

398 bytes added ,  12 years ago
→‎{{header|Common Lisp}}: Rewrite using more natural token representation, use of backquote, translation from infix to prefix and direct eval. More syntax error checking cases added.
(→‎{{header|Common Lisp}}: Rewrite using more natural token representation, use of backquote, translation from infix to prefix and direct eval. More syntax error checking cases added.)
Line 571:
=={{header|Common Lisp}}==
 
The following code processes the data in a pipeline of steps which are combined in the <code>evaluate</code> function.
The following code parses a string into a sequence of tokens. The sequence of tokens includes <code>:lparen</code> and <code>:rparen</code> indicating left and right parenthesis, respectively. That sequence of tokens is then transformed by replacing subsequences of the form <code>:lparen ... :rparen</code> with a sublist containing the tokens between the <code>:lparen</code> and <code>:rparen</code>. The resulting tree is then simplified by replacing any subsequence of the form <code>A x B y C …</code> with either <code>(A x B) y C …</code> or <code>A x (B y C)</code> depending on the relative precedence of <code>x</code> and <code>y</code>. This produces a syntax tree each of whose elements is either a node representing an integer, <code>(:integer . <var>n</var>)</code>, a list containing a single expression, <code>(<var>exp</var>), or an operation, <code>(<var>e<sub>1</sub></var> <var>op</var> <var>e<sub>2</sub></var>)</code>. Evaluating such a syntax tree is then trivial. This implementation can read integers, and produce integral and rational values.
 
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 <code>:lparen</code> and <code>:rparen</code> represent the the parentheses. So for instance the input
<code>"1*(3+2)"</code> tokenizes as <code>(1 * :lparen 3 + 2 :rparen)</code>.
 
Next, that sequence of tokens is then transformed by eliminating the parentheses. Subsequences of the form <code>:lparen ... :rparen</code> with a sublist containing the tokens between the <code>:lparen</code> and <code>:rparen</code>. The sequence now has an intermediate tree structure, in which parenthesized fragments like <code>1 + 2 * 3 + 4 / 9</code> still remain flat.
 
At this point, another processing stage parses the operator precedence, and fully parenthesizes fragments, turning <code>(1 + 2 / 3 + 5)</code> into <code>(1 + (2 / 3) + 5)</code>. 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 <code>eval</code>.
 
This implementation can read integers, and produce integral and rational values.
 
<lang lisp>(defun tokenize-stream (stream)
Line 585 ⟶ 597:
(consume-whitespace)
(let ((c (peek-char nil stream nil nil)))
(multiple-value-bindlet ((token value)(case c
((casenil) cnil)
((#\(nil) :eoflparen)
((#\()) :lparenrparen)
((#\)*) :rparen'*)
((#\*/) :multiply'/)
((#\/+) :divide'+)
((#\+-) :add'-)
((#\-) :subtract) (otherwise
(otherwiseunless (digit-char-p c)
(unless (digit-char-pcerror "Skip it." "Unexpected character ~w." c)
(cerror "Skip it." "Unexpected character ~w." c (read-char stream)
(readreturn-charfrom tokenize-stream)
(return-from (tokenize-stream stream)))
(tokenizeread-stream streaminteger)))))
(unless (or (null token) (valuesintegerp :integer (read-integer))token))
(unless (find token #(:integer :eof))▼
(read-char stream))
(if (not (eql token :integer)) token))
(cons token value))))))
 
(defun group-parentheses (tokens &optional (delimited nil))
Line 628 ⟶ 638:
(defun group-operations (expression)
(flet ((gop (exp) (group-operations exp)))
(if (eql (carintegerp expression) :integer) expression
expression▼
(destructuring-bind (Aa &optional (xop1 nilb xp)op2 B (y nil yp) Cc &rest others)
▲ expression
expression
▲ (unless (findmember tokenop1 #'(:integer+ :eof- * / nil))
(error "syntax error: in expr ~a expecting operator, not ~a"
(v2 (evaluate- expression e2)op1))▼
(unless (member op2 '(+ - * / nil))
(error "syntax error: in expr ~a expecting operator, not ~a"
(let ((v1 (evaluate- expression e1op2))▼
(cond
((not xpop1) (gop Aa))
((not ypop2) `(list ,(gop Aa) x,op1 ,(gop Bb)))
(t (let ((a (gop Aa)) (Bb (gop Bb)) (Cc (gop Cc)))
(if (and (findmember xop1 #'(:add+ :subtract-)) (member op2 '(* /)))
(gop `(,a ,op1 (find,b y,op2 #(:multiply,c) :divide),@others))
(gop `(list* A x (list,a B,op1 y C,b) ,op2 ,c ,@others))))))))))
(gop (list* (list A x B) y C others))))))))))
 
(defun evaluateinfix-expressionto-prefix (expression)
(if (cdrintegerp expression))▼
(cond
((eql (car expression) :integer)
(t (destructuring-bind (e1a op e2b) expression▼
▲ (cdr expression))
`(,op ,(infix-to-prefix a) ,(infix-to-prefix b)))))
((endp (cdr expression))
(evaluate-expression (car expression)))
▲ (t (destructuring-bind (e1 op e2) expression
▲ (let ((v1 (evaluate-expression e1))
▲ (v2 (evaluate-expression e2)))
(ecase op
(:add (+ v1 v2))
(:subtract (- v1 v2))
(:multiply (* v1 v2))
(:divide (/ v1 v2))))))))
 
(defun evaluate (string)
(with-input-from-string (in string)
(evaluate-expressioneval
(groupinfix-operationsto-prefix
(group-parenthesesoperations
(loop for token = (tokenizegroup-stream in)parentheses
until (eqlloop :eoffor token = (tokenize-stream in)
collect until (null token))))))</lang>
collect token)))))))</lang>
 
Examples
 
Anonymous user
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/50604"