python写的多项式符号乘法

D:\>poly.py
(x - 1) * (x^2 + x + 1) = x^3 - 1

 1 import ply.lex as lex # pip install ply

 2 import ply.yacc as yacc

 3

 4 def parse(s):

 5     t = {}

 6     tokens = ('NUM', 'VAR'); t_NUM = r'\d+'; t_VAR = r'[x|X]'; literals = ['+', '-', '*', '^']

 7     def t_error(t): t.lexer.skip(1)

 8     precedence = (('left', '+', '-'), ('nonassoc', '*'), ('nonassoc', '^'))

 9     def p_1(p):

10         '''poly : poly '+' term

11                 | poly '-' term'''

12         if p[2] == '-': t[p[3]] = -t[p[3]]

13     def p_2(p): 'poly : term'

14     def p_3(p): "poly : '-' term"; t[p[2]] = -t[p[2]]

15     def p_4(p): 'term : NUM'; t[0] = int(p[1]); p[0] = 0;

16     def p_5(p): 'term : VAR'; t[1] = 1; p[0] = 1;

17     def p_6(p): "term : NUM '*' VAR"; t[1] = int(p[1]); p[0] = 1

18     def p_7(p): "term : VAR '^' NUM"; t[int(p[3])] = 1; p[0] = int(p[3])

19     def p_8(p): "term : NUM '*' VAR '^' NUM"; t[int(p[5])] = int(p[1]); p[0] = int(p[5])

20     def p_error(p): raise Exception()

21     lexer = lex.lex()

22     yacc.yacc().parse(s)

23     return t

24

25 class poly:

26     @staticmethod # e: exponent, c: coefficient

27     def canonical(d): return { e:c for e,c in d.items() if c }

28     def __init__(m, s): m.d = poly.canonical(parse(s) if isinstance(s, str) else s)

29     def __str__(m):

30         first = 1

31         s = ''

32         for e,c in sorted(m.d.items(), key=lambda ec:ec[0], reverse=1):

33             if first: s += '-' if c < 0 else ''

34             else: s += ' - ' if c < 0 else ' + '

35             c = abs(c)

36             if e == 0: s += str(c); continue

37             if c != 1: s += str(c) + '*'

38             s += 'x' if e == 1 else 'x^' + str(e)

39             first = 0

40         return s

41     def __mul__(a, b):

42         d = {}

43         for e,c in a.d.items():

44             for e2,c2 in b.d.items():

45                 e3 = e + e2; d[e3] = d.get(e3, 0) + c * c2

46         return poly(d)

47 #print(poly('-x^4 - 3*x^2 - 2*x - 5'))

48 a = poly('x - 1'); b = poly('x^2 + x + 1')

49 print('(', a, ') * (', b, ') = ', a * b, sep='')

search(computer algebra), search(unexpected applications of polynomials in combinatorics), search(多项式算法快速傅里叶变换FFT)

科学计算可分为数值计算和符号计算两类。MATLAB和SymPy好像两者都用上了。比如MATLAB能分解因式，好像会出来0.999999999999这样的系数，但多项式相乘的复杂度是优化前O(n*n)，用上FFT后O(n*log(n))。

Created by PLY version 3.11 (http://www.dabeaz.com/ply) https://ply.readthedocs.io/en/latest/

Grammar

Rule 0 S' -> poly
Rule 1 poly -> poly + term
Rule 2 poly -> poly - term
Rule 3 poly -> term
Rule 4 poly -> - term
Rule 5 term -> NUM
Rule 6 term -> VAR
Rule 7 term -> NUM * VAR
Rule 8 term -> VAR ^ NUM
Rule 9 term -> NUM * VAR ^ NUM

Terminals, with rules where they appear

* : 7 9
+ : 1
- : 2 4
NUM : 5 7 8 9 9
VAR : 6 7 8 9
^ : 8 9
error :

Nonterminals, with rules where they appear

poly : 1 2 0
term : 1 2 3 4

Parsing method: LALR

state 0

(0) S' -> . poly
(1) poly -> . poly + term
(2) poly -> . poly - term
(3) poly -> . term
(4) poly -> . - term
(5) term -> . NUM
(6) term -> . VAR
(7) term -> . NUM * VAR
(8) term -> . VAR ^ NUM
(9) term -> . NUM * VAR ^ NUM

- shift and go to state 3
NUM shift and go to state 4
VAR shift and go to state 5

poly shift and go to state 1
term shift and go to state 2

state 1

(0) S' -> poly .
(1) poly -> poly . + term
(2) poly -> poly . - term

+ shift and go to state 6
- shift and go to state 7

state 2

(3) poly -> term .

+ reduce using rule 3 (poly -> term .)
- reduce using rule 3 (poly -> term .)
$end reduce using rule 3 (poly -> term .)

state 3

(4) poly -> - . term
(5) term -> . NUM
(6) term -> . VAR
(7) term -> . NUM * VAR
(8) term -> . VAR ^ NUM
(9) term -> . NUM * VAR ^ NUM

NUM shift and go to state 4
VAR shift and go to state 5

term shift and go to state 8

state 4

(5) term -> NUM .
(7) term -> NUM . * VAR
(9) term -> NUM . * VAR ^ NUM

+ reduce using rule 5 (term -> NUM .)
- reduce using rule 5 (term -> NUM .)
$end reduce using rule 5 (term -> NUM .)
* shift and go to state 9

state 5

(6) term -> VAR .
(8) term -> VAR . ^ NUM

+ reduce using rule 6 (term -> VAR .)
- reduce using rule 6 (term -> VAR .)
$end reduce using rule 6 (term -> VAR .)
^ shift and go to state 10

state 6

(1) poly -> poly + . term
(5) term -> . NUM
(6) term -> . VAR
(7) term -> . NUM * VAR
(8) term -> . VAR ^ NUM
(9) term -> . NUM * VAR ^ NUM

NUM shift and go to state 4
VAR shift and go to state 5

term shift and go to state 11

state 7

(2) poly -> poly - . term
(5) term -> . NUM
(6) term -> . VAR
(7) term -> . NUM * VAR
(8) term -> . VAR ^ NUM
(9) term -> . NUM * VAR ^ NUM

NUM shift and go to state 4
VAR shift and go to state 5

term shift and go to state 12

state 8

(4) poly -> - term .

+ reduce using rule 4 (poly -> - term .)
- reduce using rule 4 (poly -> - term .)
$end reduce using rule 4 (poly -> - term .)

state 9

(7) term -> NUM * . VAR
(9) term -> NUM * . VAR ^ NUM

VAR shift and go to state 13

state 10

(8) term -> VAR ^ . NUM

NUM shift and go to state 14

state 11

(1) poly -> poly + term .

+ reduce using rule 1 (poly -> poly + term .)
- reduce using rule 1 (poly -> poly + term .)
$end reduce using rule 1 (poly -> poly + term .)

state 12

(2) poly -> poly - term .

+ reduce using rule 2 (poly -> poly - term .)
- reduce using rule 2 (poly -> poly - term .)
$end reduce using rule 2 (poly -> poly - term .)

state 13

(7) term -> NUM * VAR .
(9) term -> NUM * VAR . ^ NUM

+ reduce using rule 7 (term -> NUM * VAR .)
- reduce using rule 7 (term -> NUM * VAR .)
$end reduce using rule 7 (term -> NUM * VAR .)
^ shift and go to state 15

state 14

(8) term -> VAR ^ NUM .

+ reduce using rule 8 (term -> VAR ^ NUM .)
- reduce using rule 8 (term -> VAR ^ NUM .)
$end reduce using rule 8 (term -> VAR ^ NUM .)

state 15

(9) term -> NUM * VAR ^ . NUM

NUM shift and go to state 16

state 16

(9) term -> NUM * VAR ^ NUM .

+ reduce using rule 9 (term -> NUM * VAR ^ NUM .)
- reduce using rule 9 (term -> NUM * VAR ^ NUM .)
$end reduce using rule 9 (term -> NUM * VAR ^ NUM .)

 1 # parsetab.py

 2 # This file is automatically generated. Do not edit.

 3 # pylint: disable=W,C,R

 4 _tabversion = '3.10'

 5

 6 _lr_method = 'LALR'

 7

 8 _lr_signature = "left+-nonassoc*nonassoc^NUM VARpoly : poly '+' term\n\t\t\t\t\t\t| poly '-' termpoly : termpoly : '-' termterm : NUMterm : VARterm : NUM '*' VARterm : VAR '^' NUMterm : NUM '*' VAR '^' NUM"

 9

10 _lr_action_items = {'-':([0,1,2,4,5,8,11,12,13,14,16,],[3,7,-3,-5,-6,-4,-1,-2,-7,-8,-9,]),'NUM':([0,3,6,7,10,15,],[4,4,4,4,14,16,]),'VAR':([0,3,6,7,9,],[5,5,5,5,13,]),'$end':([1,2,4,5,8,11,12,13,14,16,],[0,-3,-5,-6,-4,-1,-2,-7,-8,-9,]),'+':([1,2,4,5,8,11,12,13,14,16,],[6,-3,-5,-6,-4,-1,-2,-7,-8,-9,]),'*':([4,],[9,]),'^':([5,13,],[10,15,]),}

11

12 _lr_action = {}

13 for _k, _v in _lr_action_items.items():

14    for _x,_y in zip(_v[0],_v[1]):

15       if not _x in _lr_action:  _lr_action[_x] = {}

16       _lr_action[_x][_k] = _y

17 del _lr_action_items

18

19 _lr_goto_items = {'poly':([0,],[1,]),'term':([0,3,6,7,],[2,8,11,12,]),}

20

21 _lr_goto = {}

22 for _k, _v in _lr_goto_items.items():

23    for _x, _y in zip(_v[0], _v[1]):

24        if not _x in _lr_goto: _lr_goto[_x] = {}

25        _lr_goto[_x][_k] = _y

26 del _lr_goto_items

27 _lr_productions = [

28   ("S' -> poly","S'",1,None,None,None),

29   ('poly -> poly + term','poly',3,'p_1','poly.py',10),

30   ('poly -> poly - term','poly',3,'p_1','poly.py',11),

31   ('poly -> term','poly',1,'p_2','poly.py',14),

32   ('poly -> - term','poly',2,'p_3','poly.py',15),

33   ('term -> NUM','term',1,'p_4','poly.py',16),

34   ('term -> VAR','term',1,'p_5','poly.py',17),

35   ('term -> NUM * VAR','term',3,'p_6','poly.py',18),

36   ('term -> VAR ^ NUM','term',3,'p_7','poly.py',19),

37   ('term -> NUM * VAR ^ NUM','term',5,'p_8','poly.py',20),

38 ]

巴特西

python写的多项式符号乘法

最新文章

热门文章