Ãëàâíàÿ ñòðàíèöà


ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Ilia Kantor                          2:5020/1815.6  08 Dec 2001  22:16:42
 To : All
 Subject : FAQ
 -------------------------------------------------------------------------------- 
 
 
 === Cut ===
 Q18. Âpàùåíèå pàñòpîâîé êàpòèíêè (C source)
 A.   (Andrew Usachov  2:5100/87)
 ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ
 
 #include <dos.h>
 #include <alloc.h>
 #include <fcntl.h>
 #include <io.h>
 #include <mem.h>
 #include <math.h>
 
 typedef struct {
  char              bfType[2];
  unsigned long     bfSize;
  unsigned long     bfReserved;
  unsigned long     bfOffBits;
 
  unsigned long     biSize;
  unsigned long     biWidth;
  unsigned long     biHeight;
  unsigned int      biPlanes;
  unsigned int      biBitCount;
  unsigned long     biCompression;
  unsigned long     biSizeImage;
  unsigned long     biXPelsPerMeter;
  unsigned long     biYPelsPerMeter;
  unsigned long     biClrUsed;
  unsigned long     biClrImportant;
 
  struct {
    unsigned char rgbBlue;
    unsigned char rgbGreen;
    unsigned char rgbRed;
    unsigned char rgbReserved;
  } bmiColors[256];
 
 } TBMPFileHeader;
 
 typedef unsigned char Row[320];
 
 main(argc,argv)
 int argc;
 char **argv;
 {
  Row            *screen = MK_FP(0xA000,0),
                 *picture,
                 *buffer;
 
  int            BMP;
  TBMPFileHeader header;
 
  unsigned       x,y,i,
                 xp,yp;
 
  long           x0,y0,
                 xdx,xdy,
                 ydx,ydy,
                 x1,y1;
 
  double         A, SinA, CosA, scale;
 
  int            r,g,b, black, black_bri, bri;
 
  if ( argc<2 ||
       (picture = malloc(64000)) == NULL ||
       (buffer = malloc(64000)) == NULL )
    return(1);
 
  // ÷èòàåì êàpòèíêy èç 256-öâåòíîãî *.BMP ôàéëà ñ pàçìåpîì
 èçîápàæåíèÿ 320x200
  // è áåç èñïîëüçîâàíèÿ êîìïpåññèè. Ðàçìåp ôàéëà äîëæåí áûòü
 65078 áàéò.
 
  BMP = open(argv[1], O_RDONLY | O_BINARY);
  read(BMP,&header,sizeof(header));
  read(BMP,buffer,64000);
  close(BMP);
 
  // ïåpåõîäèì â ãpàôè÷åñêèé påæèì 13h
  _AX=0x13;
  geninterrupt(0x10);
 
  // èçìåíÿåì ïàëèòpy è íàõîäèì ñàìûé ÷åpíûé öâåò
  black_bri=32767; // ÿpêîñòü ñàìîãî ÷åpíîãî èç íàéäåííûõ öâåòîâ
  outportb(0x3c8,0);
  for (i=0; i<256; i++) {
     r=header.bmiColors[i].rgbRed >> 2;
     g=header.bmiColors[i].rgbGreen >> 2;
     b=header.bmiColors[i].rgbBlue >> 2;
     outportb(0x3c9, r);
     outportb(0x3c9, g);
     outportb(0x3c9, b);
     bri=r*r+g*g+b*b; // ÿpêîñòü òåêyùåãî öâåòà
     if (bri<black_bri) {
       black_bri=bri;
       black=i; // ñàìûé ÷åpíûé èç íàéäåííûõ öâåòîâ
     }
  }
  _AX=0x1001; // îêpàøèâåì áîpäþp â ÷åpíûé öâåò
  _BH=black;
  geninterrupt(0x10);
 
  // â ôàéëå ñòpîêè õpàíèëèñü â îápàòíîì ïîpÿäêå, èõ íåîáõîäèìî
 ïåpåñòàâèòü
 
  for (y=0; y<200; y++)
    memcpy(picture[y],buffer[199-y],320);
 
  // âpàùàåì êàpòèíêy
  for (A=0.0; inportb(0x60)!=0x01; A+=0.03) { // ïîêà íå íàæàëè
 ESCAPE
 
     scale=1.0/(1.0+0.2*cos(A*4.0)); // êîýôôèöèåíò yâåëè÷åíèÿ
 êàpòèíêè
     SinA=sin(A);
     CosA=cos(A);
     // êàêyþ òî÷êy êàpòèíêè íàäî èçîápàæàòü â âåpõíåé ëåâîé
 òî÷êå ýêpàíà?
     // (èñïîëüçyþòñÿ âû÷èñëåíèÿ ñ ôèêñèpîâàííîé òî÷êîé â
 ôîpìàòå 16.16)
     x0= (160.0+scale*(-160.0*CosA+100.0*1.2*SinA))*65536.0;
     y0= (100.0+scale*(-100.0*CosA-160.0*SinA/1.2))*65536.0;
     // íà ñêîëüêî íàäî ñìåñòèòüñÿ ïî êàpòèíêå ïpè ïåpåìåøåíèè
 ïî ýêpàíy
     // íà ïèêñåëü âëåâî
     xdx = scale*CosA*65536.0;
     xdy = scale*SinA*65536.0/1.2;
 
     // íà ïèêñåëü âíèç
     ydx = -scale*SinA*65536.0*1.2;
     ydy = scale*CosA*65536.0;
 
     for (y=0; y<200; y++) {
      // x0, y0 - êîîpäèíàòû íà êàpòèíêå íà÷àëà òåêyùåé ñòpîêè
 ñêàíèpîâàíèÿ
      // x1, y1 - êîîpäèíàòû íà êàpòèíêå òåêyùåé pèñyåìîé òî÷êè
      x1 = x0;
      y1 = y0;
      for (x=0; x<320; x++) {
       // xp, yp - êîîpäèíàòû íà êàpòèíêå òåêyùåé pèñyåìîé òî÷êè
 (ôîpìàò 16:0)
       xp = x1 >> 16;
       yp = y1 >> 16;
       // "êëèïïèíã"
       if (/*xp>=0 &&*/ xp<=319 && /*yp>=0 &&*/ yp<=199) // Ò.ê.
 îíè unsigned
          buffer[y][x]=picture[yp][xp];
       else
          buffer[y][x]=black;
       // ïåpåäâèæåíèå âäîëü ñòpîêè ñêàíèpîâàíèÿ
       x1+=xdx;
       y1+=xdy;
      }
      // ïåpåõîä ê íîâîé ñòpîêå ñêàíèpîâàíèÿ
      x0+=ydx;
      y0+=ydy;
     }
 
     // èçîápàæàåì íà ýêpàíå è åùå íåìíîæêî ïîâîpà÷èâàåì
     memcpy(screen,buffer,64000);
  };
 
  _AX=0x03;
  geninterrupt(0x10);
 
  free(buffer);
  free(picture);
  return(0);
 }
 
 ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ
 Q19. Ïîèñê ïî ìàñêå
 A.   (Arkady V.Belousov  ark@belous.munic.msk.su)
 ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ
 
 #include <cv/string2.h>
 /*---------------------------------------------------------------------*/
 /* Ñpàâíåíèå ñòpîêè ñ øàáëîíîì. Â øàáëîíå ìîæíî yïîòpåáëÿòü
 çíàêè '?'   */
 /* (ëþáîé çíàê) è '*' (ëþáîå êîëè÷åñòâî ëþáûõ çíàêîâ)
         */
 
 #define isMaskDone()    ((bool)!*mask)
 
 bool NFAST_ wildcmp(PCStr mask, PCStr name){
         PCStr last;     /* yêàçûâàåò íà ïpåäûäyùèé øàáëîííûé
 ñèìâîë     */
 
         /* Ñpàâíèòü íà÷àëî (äî ïåpâîãî ñèìâîëà '*') øàáëîíà ñ
 èìåíåì    */
         for(;; mask++, name++){
                 char ch = *name; if(*mask != '?' && *mask !=
 ch) break;
                 if(ch == EOS) return isMaskDone();      /*
 *mask == EOS */
         }
         if(*mask != '*') return false;
 
         for(;; mask++, name++){
                 /* Åñëè ñèìâîë ãpyïïû, çíà÷èò ñòàpàÿ ãpyïïà
 ñîâïàëà è   */
                 /* íyæíî çàïîìíèòü íîâûå ñòàpòîâûå ïîçèöèè
 ñpàâíåíèÿ    */
                 while(*mask == '*'){            /* while -
 çàùèòà îò "**" */
                         last = mask++;
                         /* Åñëè '*' ñòîèò â êîíöå øàáëîíà, òî
 ñêàíèpîâàòü */
                         /* õâîñò ñòpîêè íå òpåáyåòñÿ
         */
                         if(*mask == EOS) return isMaskDone();
 /* true */
                 }
 
                 /* Åñëè êîí÷èëîñü èìÿ, âåpíyòü påçyëüòàò
 ñpàâíåíèÿ      */
                 char ch = *name;
                 if(ch == EOS) return isMaskDone();      /*
 *mask == EOS */
                 if(*mask != '?' && *mask != ch){
                         /* Åñëè çíàê øàáëîíà íå ñîâïàäàåò ñî
 çíàêîì èìåíè, */
                         /* íyæíî îòñòyïèòü ê íà÷àëy ïîäñòpîêè è
 ïîïûòàòüñÿ */
                         /* íàéòè å¸ ñî ñëåäyþùåé ïîçèöèè èìåíè
         */
                         name -= (size_t)(mask - last) - 1, mask
 = last;
 }       }       }
 
      Ïpè èñïîëüçîâàíèè äëÿ èì¸í ôàéëîâ åñòü îäíî îãpàíè÷åíèå
 (ñâÿçàííîå ñ
 òåì, ÷òî ýòî yíèâåpñàëüíûé àëãîpèòì, íå pàñ÷èòàííûé èìåííî íà
 èìåíà ôàéëîâ
 MS-DOS) - åñëè â îäíîé ñòpîêå (èìåíè èëè øàáëîíå) çàäàí òèï
 (òî÷êà è ÷òî-òî
 çà íåé), òî â äpyãîé ñòpîêå òèï òàêæå äîëæåí ïpèñyòñòâîâàòü.
 Ðàçyìååòñÿ, ñàì
 òèï ìîæåò áûòü ïyñòûì (òî åñòü òîëüêî îäíà òî÷êà â êîíöå).
 
      À âîò ïpèìåp èñïîëüçîâàíèÿ:
 
         //--- Ïåpåápàòü âñå èìåíà
         for(; !last; last = _dos_findnext(&fi)){
                 register count nlen = checklen(fi.name);
                 *(word*)memcopy(p, fi.name, nlen) = EOS;
 
                 //--- Ïpè ïîèñêå ïî ìåòàèìåíè, åñëè íå yêàçàíî
 èíà÷å,
                 //--- êàòàëîãè äîëæíû èñêëþ÷àòüñÿ
                 if(fi.attrib & _A_SUBDIR){
                         //--- Èñêëþ÷èòü èìåíà "." è ".."
                         if(p[0] == '.' && p[nlen - 1] == '.')
 continue;
 
                         //--- Äîáàâèòü êàòàëîã â òàáëèöy äëÿ
 ïîñëåäyþùåãî
                         //--- påêypñèâíîãî îáõîäà
                         PStr tp = top;
                         if(recurse && tp < dirNameTblTop){
                                 tp = (PStr)memcopy(tp, p,
 nlen);
                                 *(word*)tp = nlen, tp++, tp++,
 top = tp;
                         }
                         if(wildcards && !dirFind) continue;
                 }
 
                 //--- Äîáàâèòü ê èìåíè äëÿ ñpàâíåíèÿ ïpè
 íåîáõîäèìîñòè
                 //--- òî÷êy; èñêëþ÷èòü èìåíà, íå
 ñîîòâåòñòâyþùèå ìàñêå
                 p[memcspan(p, nlen, '.')] = '.';
                 if(wildcmp(wildname, p)){
                         p[nlen] = EOS; total++;
                         doEntry(fi.wr_date, fi.wr_time,
 fi.attrib);
         }       }
 
 ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ
 Q20. Êîä Øåííîíà
 A.   (Serge Gut  2:4625/44.46)
 ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ
 
    Äîïyñòèì òåáå íyæíî çàêîäèpîâàòü íåêîòîpîå ñîîáùåíèå:
    AABCDAABC
 
    Èìååì :
     A - 5     5/10 = 0.5
     B - 2     2/10 = 0.2          <----
     C - 2     2/10 = 0.2               |
     D - 1     1/10 = 0.1               |
                                        |
   Äëèíà    âñåãî    ñîîáùåíèÿ    10   (Âû÷èñëÿåòñÿ   âåpîÿòíîñòü
 âñòpå÷àåìîñòè  êàæäîãî  ñèìâîëà  è  pàñïîëàãàåì  èõ  â ñòîëáèê â
 ïîpÿäêå yáûâàíèÿ âåpîÿòíîñòåé)
   Ïîñëå  ýòîãî  ñòpîèì êîäîâûå êîìáèíàöèè ïpîñòûì ìåòîäîì. Äåëèì
 ñòîëáèê  ñ âåpîÿòíîñòÿìè òàêèì îápàçìî, ÷òîáû ñyììà âåpîÿòíîñòåé
 âåpõíåé ÷àñòè pàâíÿëàñü ïpèáëèçèòåëüíî ñyììå âåpîÿòíîñòåé íèæíåé
 ÷àñòè
 
 0.5 - ïåpâàÿ ÷àñòü   = 0.5
 -+---
 0.2 \
 0.2 | - âòîpàÿ ÷àñòü = 0.5
 0.1 /
 
   Hàïpîòèâ âåpîÿòíîñòåé âåpõíåé ÷àñòè ïpîñòàâëÿåì íyëè, íàïpîòèâ
 íèæíåé - åäèíèöû.  íàøåì ïpèìåpå ïîëy÷èì.
 
 0.5  0
 
 0.2  1
 0.2  1
 0.1  1
 
   Ïpîäåëûâàåì ïîòîì òî æå ñ pàçäåëåííûìè ÷àñòÿìè.  êîíöå-êîíöîâ
 ïpèäåì ê òîìy, ÷òî äåëèòü áîëüøå íå÷åãî.
 
 À  0.5  0
 B  0.2  10
 C  0.2  110
 D  0.1  111
 
 Èòîãî - AABCDAABC = 0 0 10 110 111 0 0 10 110
 
   Ïpè÷åì  çàêîäèpîâàííîå  ñîîáùåíèå  (ýòî  âèäíî)  íå ìîæåò áûòü
 pàñêîäèpîâàíî  íåñêîëüêèìè  ñïîñîáàìè, õîòÿ äëèíà êîäîâ ñèìâîëîâ
 îòëè÷àåòñÿ.  ×òîáû  ïpî÷èòàòü  çàêîäèpîâàííîå ñîîáùåíèå ñòpîèòñÿ
 áèíàpíîå äåpåâî.  íàøåì ñëy÷àå îíî áyäåò òàêîå.
 
                       ()
                     /    \
                   0(A)    1
                         /   \
                       0(B)   1
                            /   \
                          0(C)  1(D)
   Âîò åùå ïpèìåp ñîñòàâëåíèÿ êîäîâûõ êîìáèíàöèé ïî âåpîÿòíîñÿì:
 
 0.3   00
 0.25  01
 -+------------- (ïåpâîå äåëåíèå)
 0.1   100
 0.1   101
 -+-----------   (âòîpîå äåëåíèå)
 0.1   1100
 0.05  1101
 -+---------     (òpåòüå äåëåíèå)
 0.05  1110
 0.05  1111
 
 ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ
 Q21. Hàõîæäåíèå êpàò÷àéøèõ ïyòåé â ãpàôå
 A.   (Alex Chernobaev  2:5020/394.36)
 ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ
 
   1.  Åñëè  íyæíî  íàéòè  êpàò÷àéøèé ïyòü ìåæäy äâyìÿ âåpøèíàìè,
 ìîæíî èñïîëüçîâàòü "âîëíîâîé" àëãîpèòì.
   Ïyñòü äàí íåïyñòîé ãpàô G=(V,E); èùåòñÿ êpàò÷àéøèé ïyòü îò s ê
 t (s <> t).
   (1)  âñåì  âåpøèíàì  vi  ïpèïèñûâàåòñÿ  öåëîå  ÷èñëî  T(vi)  -
 âpåìåíí'àÿ ìåòêà ñ íà÷àëüíûì çíà÷åíèåì, pàâíûì 0;
   (2)  çàâîäÿòñÿ äâà ñïèñêà "ôpîíòà âîëíû" (NewFront, OldFront),
 à òàêæå ïåpåìåííàÿ T (òåêyùåå âpåìÿ);
   (3) OldFront:={s}; NewFront:={}; T:=1;
   (4) äëÿ êàæäîé èç âåpøèí, âõîäÿùèõ â OldFront, ïpîñìàòpèâàþòñÿ
 ñîñåäíèå   âåpøèíû   uj,   è   åñëè  T(uj)  =  0,  òî  T(uj):=T,
 NewFront:=NewFront + {uj};
   (5) åñëè NewFront = {}, òî ïyòè íå ñyùåñòâyåò; ÂÛÕÎÄ;
   (6)  åñëè  îäíà èç âåpøèí uj ñîâïàäàåò t, òî íàéäåí êpàò÷àéøèé
 ïyòü äëèíû T; ÂÛÕÎÄ; èíà÷å
   (7) OldFront:=NewFront; NewFront:={}; T:=T+1; goto (4)
   Åñëè  íà  øàãå  (6) áûëà äîñòèãíyòà âåpøèíà t, òî âîññòàíîâèòü
 êpàò÷àéøèé ïyòü ìîæíî ñëåäyþùèì îápàçîì: ñpåäè ñîñåäåé âåpøèíû t
 íàõîäèòñÿ   âåpøèíà  ñ  âpåìåíí'îé  ìåòêîé  T-1,  ñpåäè  ñîñåäåé
 ïîñëåäíåé  -  âåpøèíà ñ ìåòêîé T-2, è ò.ä., ïîêà íå äîñòèãíåì s;
 åñëè  "ïåpåâåpíyòü"  ïîëy÷åííûé ñïèñîê âåpøèí, òî ïîëy÷èòñÿ îäèí
 èç êpàò÷àéøèõ ïyòåé îò s ê t.
   Hà  ïpàêòèêå  âûãîäíåå ñîõpàíÿòü íà øàãå (4) èíôîpìàöèþ î òîì,
 èç   êàêîé   âåpøèíû   âîëíà   ïpèøëà   â  âåpøèíy  uj  -  òîãäà
 âîññòàíîâëåíèå ïyòè ìîæíî îñyùåñòâèòü áûñòpåå.
   2.  Åñëè  òpåáyåòñÿ íàéòè êpàò÷àéøèé ïyòü âî âçâåøåííîì ãpàôå,
 ãäå  påápàì  ïpèïèñàíû  âåùåñòâåííûå  ÷èñëà  -  âåñà, è ýòè âåñà
 íåîòpèöàòåëüíû,   ìîæíî   èñïîëüçîâàòü  àëãîpèòì  Äåéêñòpû.  Ïpè
 íàëè÷èè  påáåp  ñ  îòpèöàòåëüíûì  âåñîì êpàò÷àéøèé ïyòü ìîæåò íå
 ñyùåñòâîâàòü   äàæå   äëÿ   ñâÿçíîãî   ãpàôà.   Êpàò÷àéøèé  ïyòü
 ñyùåñòâyåò,  òîëüêî  åñëè  â  ãpàôå  íåò  öèêëîâ  îòpèöàòåëüíîãî
 ñyììàpíîãî  âåñà  -  ïî  òàêîìy  öèêëy  ìîæíî  êpyòèòüñÿ ñêîëüêî
 yãîäíî,  yìåíüøàÿ  äëèíy  äî  áåñêîíå÷íîñòè.  Äëÿ  îáùåãî ñëy÷àÿ
 ïîäõîäèò   àëãîpèòì   Ôëîéäà,   êîòîpûé   ïîçâîëÿåò  ëèáî  íàéòè
 êpàò÷àéøèå ïyòè, ëèáî îáíàpyæèòü öèêëû îòpèöàòåëüíîé äëèíû.
   Óïîìÿíyòûå   àëãîpèòìû  ÿâëÿþòñÿ  êëàññè÷åñêèìè  è  îïèñàíû  â
 pàçëè÷íûõ  êíèãàõ ïî òåîpèè ãpàôîâ (íàïp.: H.Êpèñòîôèäåñ. Òåîpèÿ
 ãpàôîâ.  Àëãîpèòìè÷åñêèé  ïîäõîä.  Ì.,  "Ìèp", 1978). Ñyùåñòâyåò
 îãpîìíîå êîëè÷åñòâî äpyãèõ àëãîpèòìîâ, áîëåå âûãîäíûõ â êàêèõ-òî
 ñëy÷àÿõ.
 
 ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ
 Q22. Îápàòíàÿ ïîëüñêàÿ íîòàöèÿ
 A.   (Alexey Olkhovsky  aolkhov@messages.to)
 ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ
 
   Èñïîëüçyåòñÿ  äëÿ  âû÷èñëåíèÿ  àpèôìåòè÷åñêèõ  âûpàæåíèé.  Äëÿ
 ïåpåâîäà â íåå íåîáõîäèì ñòåê àpèôìåòè÷åñêèõ îïåpàöèé.
   Àëãîpèòì  ïåpåâîäà  ïpîèçâîëüíîãî âûpàæåíèÿ â ÎÏH î÷åíü ïpîñò:
 Âûpàæåíèå  ñêàíèpyåòñÿ  ñëåâà  íàïpàâî,  ïpè  ýòîì pàçáèâàÿñü íà
 òîêåíû  -  ÷èñëà è çíàêè àpèôìåòè÷åñêèõ îïåpàöèé. Åñëè î÷åpåäíîé
 òîêåí  -  ÷èñëî,  íå  ãëÿäÿ  ïèøåì åãî â âûõîäíyþ ñòpîêy. Èíà÷å,
 âûòàëêèâàåì  èç  ñòåêà  è ïèøåì â âûõîäíyþ ñòpîêy âñå îïåpàöèè ñ
 ïpèîpèòåòîì  âûøå  òåêyùåé, à ñàìy îïåpàöèþ ïèõàåì â ñòåê. Ëåâàÿ
 ñêîáêà  âñåãäà  ïèøåòñÿ  â  ñòåê  (åå ïpèîpèòåò - ñàìûé íèçêèé).
 Ïpàâàÿ  ñêîáêà âûòàëêèâàåò èç ñòåêà âñå îïåpàöèè âïëîòü äî ëåâîé
 ñêîáêè âêëþ÷èòåëüíî, ñàìà îíà â ñòåê íå ïèøåòñÿ. Êîãäà äîñòèãíyò
 êîíåö  âõîäíîãî âûpàæåíèÿ, ïpîñòî âûòàëêèâàåì èç ñòåêà âñå ÷òî â
 íåì åñòü.
 Ïpèìåp: (2+3)*4+5
 ëåâàÿ ñêîáêà - ïèõàåì â ñòåê
 2 - ïèøåì â âûõîäíyþ ñòpîêy
 + - ñòåê  ïyñò,  ïîýòîìy  íè÷åãî  íå äîñòàåì, à íàïpîòèâ, ïèõàåì
 ïëþñ
 3 - ïèøåì  â  âûõîäíyþ ñòpîêy ïpàâàÿ ñêîáêà - âûòàëêèâàåì ïëþñ è
 ëåâyþ ñêîáêy
 * - ñòåê ñíîâà ïyñò, ïèõàåì yìíîæåíèå
 4 - ïèøåì â âûõîäíyþ ñòpîêy
 + - ïpèîpèòåò  yìíîæåíèÿ  -  âûøå, ïîýòîìy åãî äîñòàåì, à ïëþñ -
 ïèõàå === Cut ===
             Çàêðîé çà ìíîé äâåðü, ÿ óõîæó.. [Team Êèíî]
 --- GoldEd 3.00.Alpha4+
  * Origin: http://algolist.da.ru - Ìèð Àëãîðèòìîâ (2:5020/1815.6)
 
 

Âåðíóòüñÿ ê ñïèñêó òåì, ñîðòèðîâàííûõ ïî: âîçðàñòàíèå äàòû  óìåíüøåíèå äàòû  òåìà  àâòîð 

 Òåìà:    Àâòîð:    Äàòà:  
 FAQ   Ilia Kantor   08 Dec 2001 22:16:42 
Àðõèâíîå /ru.algorithms/39463c128345.html, îöåíêà 3 èç 5, ãîëîñîâ 10
ßíäåêñ.Ìåòðèêà
Valid HTML 4.01 Transitional