Anonymous user
Arithmetic evaluation: Difference between revisions
→{{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.
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)))
(
((
((#\(
((#\
((#\
((#\
((#\
((#\
(
(
(
(unless (or (null
(unless (find token #(:integer :eof))▼
(read-char stream))
(defun group-parentheses (tokens &optional (delimited nil))
Line 628 ⟶ 638:
(defun group-operations (expression)
(flet ((gop (exp) (group-operations exp)))
(if (
(destructuring-bind (
▲ expression
expression
(error "syntax error: in expr ~a expecting operator, not ~a"
(unless (member op2 '(+ - * / nil))
(error "syntax error: in expr ~a expecting operator, not ~a"
(cond
((not
((not
(t (let ((a (gop
(if (and (
(gop `(,a
(gop `(
(defun
▲ (cdr expression))
`(,op ,(infix-to-prefix a) ,(infix-to-prefix b)))))
▲ (t (destructuring-bind (e1 op e2) expression
▲ (let ((v1 (evaluate-expression e1))
▲ (v2 (evaluate-expression e2)))
(defun evaluate (string)
(with-input-from-string (in string)
(
(
(group-
collect token)))))))</lang>
Examples
|