fork download
copy 
  1. '''
  2. Created on 10.10.2012
  3.  
  4. @author: pycz
  5. '''
  6.  
  7. import copy
  8.  
  9. class Num:
  10.     def __init__(self):
  11.         self.num='#'
  12.         self.next=None
  13.  
  14.  
  15. class LongNum(object):
  16.     def __init__(self,ln=0):
  17.         self.head=Num()
  18.         self.sign='+'
  19.         self._fill(str(ln))
  20.  
  21.     def _addFirst(self,el):
  22.         x=Num()
  23.         x.num=el
  24.         x.next=self.head.next
  25.         self.head.next=x 
  26.  
  27.     def _del(self):
  28.         self.head.next=None
  29.         self.sign="+"
  30.  
  31.     def _fill(self,ln):
  32.         ln=str(ln)
  33.         self._del()
  34.         self.sign="+"
  35.         if ln and ln[0]=='-':
  36.             self.sign='-'
  37.             ln=ln[1:]
  38.         if ln and ln[0]=='+':
  39.             ln=ln[1:]
  40.         for l in ln:
  41.             x=int(l)
  42.             self._addFirst(x)
  43.         if ln:
  44.             self._reduce_zeros()
  45.             self._isZero()
  46.  
  47.     def _isZero(self):
  48.         if self.head.next and self.head.next.num==0 and self.head.next.next==None:
  49.             self.sign='+'
  50.             return True
  51.         else:
  52.             return False
  53.  
  54.     def __str__(self):
  55.         res=""
  56.         p=self.head.next
  57.         while p!=None:
  58.             res=str(p.num)+res
  59.             p=p.next
  60.         if not self._isZero() and self.sign!='+':
  61.             res='-'+res
  62.         return res
  63.  
  64.     def empty(self):
  65.         return not self.head.next
  66.  
  67.     def __neg__(self):
  68.         res=copy.deepcopy(self)
  69.         if self._isZero():
  70.             return res
  71.         if self.sign=='+':
  72.             res.sign="-"
  73.         else:
  74.             res.sign="+"
  75.         return res
  76.  
  77.     def __abs__(self):
  78.         res=copy.deepcopy(self)
  79.         res.sign="+"
  80.         return res
  81.  
  82.     def _simple_add(self,other):
  83.         '''
  84.         return simple a+b, no signs
  85.         '''
  86.         res=LongNum()
  87.         per=0
  88.         p1=self.head.next
  89.         p2=other.head.next
  90.         p3=res.head
  91.         while not (p1==None and p2==None):
  92.             if p1!=None and p2==None:
  93.                 p3.next=Num()
  94.                 p3=p3.next
  95.                 p3.num=(p1.num+per)%10
  96.                 per=(p1.num+per)/10
  97.                 p1=p1.next
  98.             if p1==None and p2!=None:
  99.                 p3.next=Num()
  100.                 p3=p3.next
  101.                 p3.num=(p2.num+per)%10
  102.                 per=(p2.num+per)/10
  103.                 p2=p2.next
  104.             if p1!=None and p2!=None:
  105.                 p3.next=Num()
  106.                 p3=p3.next            
  107.                 p3.num=(p2.num+per+p1.num)%10
  108.                 per=(p2.num+per+p1.num)/10
  109.                 p2=p2.next
  110.                 p1=p1.next
  111.         if per!=0:
  112.             p3.next=Num()
  113.             p3=p3.next
  114.             p3.num=per        
  115.         return res
  116.  
  117.     def _reduce_zeros(self):
  118.         p=self.head.next
  119.         mark=None
  120.         while(p.next):
  121.             if(p.next.num!=0):
  122.                 mark=p
  123.             p=p.next
  124.         if mark:
  125.             mark.next.next=None
  126.         else:
  127.             self.head.next.next=None
  128.  
  129.     def _simple_sub(self,other):
  130.         '''
  131.         return simple a-b, no signs, a>=b
  132.         '''
  133.         res=LongNum()
  134.         per=0
  135.         p1=self.head.next
  136.         p2=other.head.next
  137.         p3=res.head
  138.         while p1!=None:
  139.             if p1!=None and p2==None:
  140.                 p3.next=Num()
  141.                 p3=p3.next                
  142.                 p3.num=(p1.num-per)#%10
  143.                 if p3.num<0:
  144.                     p3.num+=10
  145.                     per=1
  146.                 else:
  147.                     per=0
  148.                 p1=p1.next
  149.             if p1!=None and p2!=None:
  150.                 p3.next=Num()
  151.                 p3=p3.next            
  152.                 p3.num=(p1.num-p2.num-per)#%10
  153.                 if p3.num<0:
  154.                     p3.num+=10
  155.                     per=1
  156.                 else:
  157.                     per=0
  158.                 p2=p2.next
  159.                 p1=p1.next
  160.         res._reduce_zeros()
  161.         return res                           
  162.  
  163.     def __eq__(self,other):
  164.         p1=self.head.next
  165.         p2=other.head.next
  166.         if self.sign==other.sign:
  167.             equ=True
  168.         else:
  169.             equ=False
  170.  
  171.         while p1 and p2 and equ:
  172.             equ=(p1.num==p2.num)
  173.             p1=p1.next
  174.             p2=p2.next
  175.         if not p1 and not p2 and equ:
  176.             return True
  177.         else:
  178.             return False
  179.  
  180.     def __len__(self):
  181.         '''
  182.         length without sign
  183.         '''
  184.         count=0
  185.         p=self.head
  186.         while(p.next):
  187.             count+=1
  188.             p=p.next
  189.         return count
  190.  
  191.     def reverse(self):
  192.         t1 = self.head.next
  193.         s = None;
  194.         while t1 <> None: 
  195.             p = t1
  196.             t1 = t1.next
  197.             p.next = s
  198.             s = p
  199.         self.head.next = s 
  200.  
  201.     def _low_then(self,other):
  202.         '''
  203.         A<B, A>=0, B>=0
  204.         '''
  205.         if len(self)<len(other):
  206.             return True
  207.         elif len(self)>len(other):
  208.             return False
  209.         else:
  210.             s=copy.deepcopy(self)
  211.             o=copy.deepcopy(other)
  212.             s.reverse()
  213.             o.reverse()
  214.             p1=s.head.next
  215.             p2=o.head.next
  216.             while p1.num==p2.num and p1.next:
  217.                 p1=p1.next
  218.                 p2=p2.next
  219.             if p1.num<p2.num:
  220.                 return True
  221.             else:
  222.                 return False
  223.  
  224.     def __lt__(self,other):
  225.         if self.sign=="+" and other.sign=="-":
  226.             return False
  227.         elif self.sign=="-" and other.sign=="+":
  228.             return True
  229.         elif self.sign=="-" and other.sign=="-":
  230.             return other._low_then(self)
  231.         else:
  232.             return self._low_then(other)   
  233.  
  234.     def __le__(self,other):
  235.         if self<other or self==other:
  236.             return True
  237.         else:
  238.             return False
  239.  
  240.     def __ne__(self,other):
  241.         if self==other:
  242.             return False
  243.         else:
  244.             return True
  245.  
  246.     def __gt__(self,other):
  247.         if other<self:
  248.             return True
  249.         else:
  250.             return False
  251.  
  252.     def __ge__(self,other):
  253.         if self<other:
  254.             return False
  255.         else:
  256.             return True    
  257.  
  258.     def __add__(self,other):
  259.         if self.sign=="+" and other.sign=="+":
  260.             return self._simple_add(other)
  261.         elif self.sign=="-" and other.sign=="-":
  262.             res=self._simple_add(other)
  263.             res.sign="-"
  264.             return res
  265.         elif self.sign=="-" and other.sign=="+":
  266.             s=abs(self)
  267.             o=abs(other)
  268.             if o>s:
  269.                 res=o._simple_sub(s)
  270.                 res.sign="+"
  271.             else:
  272.                 res=s._simple_sub(o)
  273.                 res.sign="-"
  274.             return res
  275.         else:
  276.             return other+self
  277.  
  278.     def __sub__(self,other):
  279.         return self+(-other)
  280.  
  281.     def _x10mul(self,count=1):
  282.         for i in xrange(count):
  283.             self._addFirst(0)
  284.  
  285.     def _x10div(self,count=1):
  286.         for i in xrange(count):
  287.             self.head.next=self.head.next.next
  288.  
  289.     def _simple_mul(self,other):
  290.         '''
  291.         a*b, a>=0, b>=0
  292.         '''
  293.         summa=LongNum()
  294.         temp=LongNum()
  295.         p2=other.head.next
  296.         level=0
  297.         while p2:
  298.             per=0
  299.             tres=temp.head
  300.             p1=self.head.next
  301.             while p1:
  302.                 tres.next=Num()
  303.                 tres=tres.next
  304.                 tres.num=((p1.num*p2.num)+per)%10
  305.                 per=((p1.num*p2.num)+per)/10
  306.                 p1=p1.next
  307.             tres.next=Num()
  308.             tres=tres.next
  309.             tres.num=per            
  310.             temp._x10mul(level)
  311.             summa=summa+temp
  312.             temp=LongNum()
  313.             level+=1
  314.             p2=p2.next
  315.         summa._reduce_zeros()
  316.         return summa
  317.  
  318.     def __mul__(self,other):
  319.         if  (self.sign=="+" and other.sign=="+") or (self.sign=="-" and other.sign=="-"):
  320.             return self._simple_mul(other)
  321.         elif  self.sign=="-" and other.sign=="+":
  322.             return -(self._simple_mul(other))
  323.         else:
  324.             return other*self
  325.  
  326.     def __sub_left(self,other):
  327.         '''
  328.         A=aaaa;B=bb; A-B=aaaa-bb00
  329.         '''
  330.         o=abs(other)
  331.         o._x10mul(len(self)-len(other))
  332.         if o<=self:
  333.             return self-o
  334.         else:
  335.             o._x10div(1)
  336.             return self-o
  337.  
  338.     def _simple_div(self,other):
  339.         '''
  340.         A/B; B!=0; no signs
  341.         '''
  342.         s=abs(self)
  343.         o=abs(other)
  344.         res=LongNum()
  345.         delit=copy.deepcopy(o)
  346.  
  347.         count=0
  348.         while(o<=s):
  349.             count+=1
  350.             o._x10mul()
  351.         o._x10div()
  352.         count-=1
  353.         j=0
  354.         while j<=count:
  355.             C=LongNum()
  356.             i=0
  357.             C._fill(i)
  358.             while C*o<=s:
  359.                 i+=1
  360.                 C._fill(i)
  361.             i-=1
  362.             res._addFirst(i)
  363.             if i==-1: i=0
  364.             C._fill(i)
  365.             s=s-(C*o)
  366.             if o!=delit:
  367.                 o._x10div()
  368.             j+=1
  369.  
  370.         res._reduce_zeros()
  371.         return res
  372.  
  373.  
  374.  
  375.  
  376. if __name__== "__main__":
  377.     x1=LongNum()
  378.     x2=LongNum()
  379.     y1=1010
  380.     y2=101
  381.     x1._fill(y1)
  382.  
  383.     x2._fill(y2)
  384.     lol=x1._simple_div(x2)
  385.     print lol
  386.     print y1/y2
  387.  
  388.  
  389. #    print 
  390. #    print x1+x2
  391. #    print x2+x1   
  392.  
Success #stdin #stdout 0.1s 10968KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1-1
10
https://ideone.com/wLbwF
language:
Python (cpython 2.7.16)
created:
12 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!