;;; -*- Mode: Lisp; Syntax: Common-Lisp; Package: Grobner; Base: 10 -*- ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;; ;;; Copyright (C) 1999, 2002, 2009, 2015 Marek Rychlik ;;; ;;; This program is free software; you can redistribute it and/or modify ;;; it under the terms of the GNU General Public License as published by ;;; the Free Software Foundation; either version 2 of the License, or ;;; (at your option) any later version. ;;; ;;; This program is distributed in the hope that it will be useful, ;;; but WITHOUT ANY WARRANTY; without even the implied warranty of ;;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the ;;; GNU General Public License for more details. ;;; ;;; You should have received a copy of the GNU General Public License ;;; along with this program; if not, write to the Free Software ;;; Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. ;;; ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;; ;; Parser of infix notation. This package enables input ;; of polynomials in human-readable notation outside of Maxima, ;; which is very useful for debugging. ;; ;; NOTE: This package is adapted from CGBLisp. ;; ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; (defpackage "PARSE" (:use :cl :order :ring-and-order :monomial :term :polynomial :ring) (:export "PARSE PARSE-TO-ALIST" "PARSE-STRING-TO-ALIST" "PARSE-TO-SORTED-ALIST" "PARSE-STRING-TO-SORTED-ALIST" "^" "[" "POLY-EVAL" )) (in-package "PARSE") (proclaim '(optimize (speed 0) (space 0) (safety 3) (debug 3))) ;; The function PARSE yields the representations as above. The two functions ;; PARSE-TO-ALIST and PARSE-STRING-TO-ALIST parse polynomials to the alist ;; representations. For example ;; ;; >(parse)x^2-y^2+(-4/3)*u^2*w^3-5 ---> ;; (+ (* 1 (^ X 2)) (* -1 (^ Y 2)) (* -4/3 (^ U 2) (^ W 3)) (* -5)) ;; ;; >(parse-to-alist '(x y u w))x^2-y^2+(-4/3)*u^2*w^3-5 ---> ;; (((0 0 2 3) . -4/3) ((0 2 0 0) . -1) ((2 0 0 0) . 1) ((0 0 0 0) . -5)) ;; ;; >(parse-string-to-alist "x^2-y^2+(-4/3)*u^2*w^3-5" '(x y u w)) ---> ;; (((0 0 2 3) . -4/3) ((0 2 0 0) . -1) ((2 0 0 0) . 1) ((0 0 0 0) . -5)) ;; ;; >(parse-string-to-alist "[x^2-y^2+(-4/3)*u^2*w^3-5,y]" '(x y u w)) ;; ([ (((0 0 2 3) . -4/3) ((0 2 0 0) . -1) ((2 0 0 0) . 1) ;; ((0 0 0 0) . -5)) ;; (((0 1 0 0) . 1))) ;; The functions PARSE-TO-SORTED-ALIST and PARSE-STRING-TO-SORTED-ALIST ;; in addition sort terms by the predicate defined in the ORDER package ;; For instance: ;; >(parse-to-sorted-alist '(x y u w))x^2-y^2+(-4/3)*u^2*w^3-5 ;; (((2 0 0 0) . 1) ((0 2 0 0) . -1) ((0 0 2 3) . -4/3) ((0 0 0 0) . -5)) ;; >(parse-to-sorted-alist '(x y u w) t #'grlex>)x^2-y^2+(-4/3)*u^2*w^3-5 ;; (((0 0 2 3) . -4/3) ((2 0 0 0) . 1) ((0 2 0 0) . -1) ((0 0 0 0) . -5)) ;;(eval-when (compile) ;; (proclaim '(optimize safety))) (defun parse (&optional stream) "Parser of infix expressions with integer/rational coefficients The parser will recognize two kinds of polynomial expressions: - polynomials in fully expanded forms with coefficients written in front of symbolic expressions; constants can be optionally enclosed in (); for example, the infix form X^2-Y^2+(-4/3)*U^2*W^3-5 parses to (+ (- (EXPT X 2) (EXPT Y 2)) (* (- (/ 4 3)) (EXPT U 2) (EXPT W 3)) (- 5)) - lists of polynomials; for example [X-Y, X^2+3*Z] parses to (:[ (- X Y) (+ (EXPT X 2) (* 3 Z))) where the first symbol [ marks a list of polynomials. -other infix expressions, for example [(X-Y)*(X+Y)/Z,(X+1)^2] parses to: (:[ (/ (* (- X Y) (+ X Y)) Z) (EXPT (+ X 1) 2)) Currently this function is implemented using M. Kantrowitz's INFIX package." (read-from-string (concatenate 'string "#I(" (with-output-to-string (s) (loop (multiple-value-bind (line eof) (read-line stream t) (format s "~A" line) (when eof (return))))) ")"))) ;; New implementation based on the INFIX package of Mark Kantorowitz (defun parse-to-alist (vars &optional stream) "Parse an expression already in prefix form to an association list form according to the internal CGBlisp polynomial syntax: a polynomial is an alist of pairs (MONOM . COEFFICIENT). For example: (WITH-INPUT-FROM-STRING (S \"X^2-Y^2+(-4/3)*U^2*W^3-5\") (PARSE-TO-ALIST '(X Y U W) S)) evaluates to (((0 0 2 3) . -4/3) ((0 2 0 0) . -1) ((2 0 0 0) . 1) ((0 0 0 0) . -5))" (poly-eval (parse stream) vars)) (defun parse-string-to-alist (str vars) "Parse string STR and return a polynomial as a sorted association list of pairs (MONOM . COEFFICIENT). For example: (parse-string-to-alist \"[x^2-y^2+(-4/3)*u^2*w^3-5,y]\" '(x y u w)) ([ (((0 0 2 3) . -4/3) ((0 2 0 0) . -1) ((2 0 0 0) . 1) ((0 0 0 0) . -5)) (((0 1 0 0) . 1))) The functions PARSE-TO-SORTED-ALIST and PARSE-STRING-TO-SORTED-ALIST sort terms by the predicate defined in the ORDER package." (with-input-from-string (stream str) (parse-to-alist vars stream))) (defun parse-to-sorted-alist (vars &optional (order #'lex>) (stream t)) "Parses streasm STREAM and returns a polynomial represented as a sorted alist. For example: (WITH-INPUT-FROM-STRING (S \"X^2-Y^2+(-4/3)*U^2*W^3-5\") (PARSE-TO-SORTED-ALIST '(X Y U W) S)) returns (((2 0 0 0) . 1) ((0 2 0 0) . -1) ((0 0 2 3) . -4/3) ((0 0 0 0) . -5)) and (WITH-INPUT-FROM-STRING (S \"X^2-Y^2+(-4/3)*U^2*W^3-5\") (PARSE-TO-SORTED-ALIST '(X Y U W) T #'GRLEX>) S) returns (((0 0 2 3) . -4/3) ((2 0 0 0) . 1) ((0 2 0 0) . -1) ((0 0 0 0) . -5))" (sort-poly (parse-to-alist vars stream) order)) (defun parse-string-to-sorted-alist (str vars &optional (order #'lex>)) "Parse a string to a sorted alist form, the internal representation of polynomials used by our system." (with-input-from-string (stream str) (parse-to-sorted-alist vars order stream))) (defun sort-poly-1 (p order) "Sort the terms of a single polynomial P using an admissible monomial order ORDER. Returns the sorted polynomial. Destructively modifies P." (sort p order :key #'first)) ;; Sort a polynomial or polynomial list (defun sort-poly (poly-or-poly-list &optional (order #'lex>)) "Sort POLY-OR-POLY-LIST, which could be either a single polynomial or a list of polynomials in internal alist representation, using admissible monomial order ORDER. Each polynomial is sorted using SORT-POLY-1." (cond ((eql poly-or-poly-list :syntax-error) nil) ((null poly-or-poly-list) nil) ((eql (car poly-or-poly-list) '[) (cons '[ (mapcar #'(lambda (p) (sort-poly-1 p order)) (rest poly-or-poly-list)))) (t (sort-poly-1 poly-or-poly-list order))))