v 0. Pasted by slipstak2 as cpp at 2011-01-08 14:43:31 MSK and set expiration to never.

Paste will expire never.

  1. // Меньшиков. Тренировка 13.
  2. // 13F. Статическая сложность [icomplex]
  3. // ibelyaev: 07Jan2011
  4.  
  5. #include <iostream>
  6. #include <cstdio>
  7. #include <vector>
  8. #include <string.h>
  9.  
  10. using namespace std;
  11. const int MAX_SIZE = 2048 + 10;
  12. const int MAX_STEPS = 12;
  13.  
  14. int n;
  15. typedef vector<int> algoComplex;
  16.  
  17. void ReadOperatorsList(char* &pos, algoComplex &totalAC);
  18. void output(algoComplex &ac, int num)
  19. {
  20.     printf("Program #%d\n",num);
  21.     printf("Runtime = ");
  22.     bool isFirst = true;
  23.     bool isEmpty = true;
  24.     for (int i = MAX_STEPS-1; i>=0; i--) {
  25.         int mul = ac[i];
  26.         if (mul){
  27.             isEmpty = false;
  28.             if (isFirst)
  29.                 isFirst = false;
  30.             else
  31.                 cout<<"+";
  32.            
  33.             if (mul != 1 || (mul == 1 && i ==0))
  34.                 cout<<mul;
  35.             if (i != 0){
  36.                 if (mul != 1) cout<<"*";
  37.                 cout<<"n";
  38.                 if (i!=1)
  39.                     cout<<"^"<<i;
  40.             }
  41.         }
  42.     }
  43.     if (isEmpty) cout<<0;
  44.     printf("\n\n");
  45. }
  46.  
  47. inline bool _isEnd(const char* pos)
  48. {
  49.     return *pos == 0;
  50. }
  51. inline void _SkipSeps(char* &pos)
  52. {
  53.     if (_isEnd(pos)) return;
  54.     while (!_isEnd(pos) && *pos == ' ')
  55.         pos++;
  56. }
  57. inline bool _isLoopBegin(const char* pos)
  58. {
  59.     if (_isEnd(pos)) return false;
  60.     return *pos == 'L';
  61. }
  62. inline bool _isOpBegin(const char* pos)
  63. {
  64.     if (_isEnd(pos)) return false;
  65.     return *pos == 'O';
  66. }
  67. inline bool _isOperatorBegin(const char* pos)
  68. {
  69.     return _isLoopBegin(pos) || _isOpBegin(pos);
  70. }
  71. inline bool _isDigit(const char pos)
  72. {
  73.     return '0' <= pos && pos <= '9';
  74. }
  75. inline void ReadLex(char* &pos, int len)
  76. {
  77.     for (int i=0;i<len;i++)
  78.         pos++;
  79. }
  80. void ReadNumber(char* &pos, int &number)
  81. {
  82.     if (*pos == 'n') {
  83.         pos++;
  84.         number = -1;
  85.         return;
  86.     }
  87.     while (_isDigit(*pos)) {
  88.         number = number*10 + *pos - '0';
  89.         pos++;
  90.     }
  91. }
  92. void ReadOperatorLoop(char* &pos, algoComplex &listAC)
  93. {
  94.     //<Оператор LOOP> ::= <Заголовок LOOP> <Список операторов> "END"
  95.     //<Заголовок LOOP> ::= "LOOP" <число> | "LOOP n"
  96.     ReadLex(pos, strlen("LOOP"));
  97.     int loopNumber = 0;
  98.  
  99.     _SkipSeps(pos);
  100.     ReadNumber(pos, loopNumber);
  101.     _SkipSeps(pos);
  102.  
  103.     algoComplex loopAC(MAX_STEPS);
  104.  
  105.  
  106.     bool isIns = false;
  107.     while (_isOperatorBegin(pos)) {
  108.  
  109.         isIns = true;
  110.         _SkipSeps(pos);
  111.         ReadOperatorsList(pos,loopAC);
  112.         _SkipSeps(pos);
  113.     }
  114.     if (isIns) {
  115.         if (loopNumber != -1) { // !=n
  116.             for (int i=0;i<MAX_STEPS;i++)
  117.                 loopAC[i] *= loopNumber;
  118.         }
  119.         else {
  120.             for (int i=MAX_STEPS-2;i>=0;i--)
  121.             {
  122.                 loopAC[i+1] = loopAC[i];
  123.                 loopAC[i] = 0;
  124.             }
  125.         }
  126.     }
  127.     else {
  128.         if (loopNumber != -1)  // !=n
  129.             loopAC[0] = loopNumber;
  130.         else
  131.             loopAC[1]++;
  132.     }
  133.  
  134.     for (int i=0;i<MAX_STEPS;i++)
  135.         listAC[i] += loopAC[i];
  136.  
  137.     _SkipSeps(pos);
  138.     ReadLex(pos,strlen("END"));
  139. }
  140.  
  141. void ReadOperatorOp(char* &pos, algoComplex & listAC)
  142. {
  143.     //<Оператор OP> ::= "OP" <число>
  144.     ReadLex(pos, strlen("OP"));
  145.     _SkipSeps(pos);
  146.     int opNumber = 0;
  147.     ReadNumber(pos, opNumber);
  148.     if (opNumber != -1) // !=n
  149.         listAC[0] += opNumber;
  150.     else
  151.         listAC[1]++;   
  152. }
  153.  
  154. void ReadOperator(char* &pos, algoComplex &curAC)
  155. {
  156.     //<Оператор> ::= <Оператор LOOP> | <Оператор OP>
  157.     if (_isLoopBegin(pos))
  158.         ReadOperatorLoop(pos, curAC);
  159.     else
  160.         ReadOperatorOp(pos, curAC);
  161. }
  162. void ReadOperatorsList(char* &pos, algoComplex &totalAC)
  163. {
  164.     //<Список операторов> ::= <Оператор> | <Оператор> <Список операторов>
  165.     do
  166.     {
  167.         _SkipSeps(pos);
  168.         algoComplex curAC(MAX_STEPS);
  169.         ReadOperator(pos, curAC);
  170.         for (int i=0;i<MAX_STEPS;i++)
  171.             totalAC[i] += curAC[i];
  172.         _SkipSeps(pos);
  173.     }
  174.     while (_isOperatorBegin(pos));
  175. }
  176. void ReadProgram(char* &pos, algoComplex &ac)
  177. {
  178.     // <Программа> ::= "BEGIN" <Список операторов> "END"
  179.     _SkipSeps(pos);
  180.     ReadLex(pos, strlen("BEGIN"));
  181.  
  182.     ReadOperatorsList(pos, ac);
  183.  
  184.     _SkipSeps(pos);
  185.     ReadLex(pos, strlen("END"));   
  186. }
  187. void input()
  188. {
  189.     cin>>n;
  190.     string allPrograms = "";
  191.     char buf[MAX_SIZE];
  192.     while (cin.getline(buf,MAX_SIZE)) {
  193.         allPrograms += string(buf);
  194.         allPrograms += " ";
  195.     }
  196.  
  197.     algoComplex progAC(MAX_STEPS);
  198.     char *str  = new char[allPrograms.size()];
  199.     strcpy(str, allPrograms.c_str());
  200.     char *pos = str;
  201.     for (int i=0;i<n;i++)
  202.     {
  203.         progAC.assign(MAX_STEPS,0);
  204.         ReadProgram(pos, progAC);
  205.         output(progAC, i+1);
  206.     }   
  207. }
  208. int main()
  209. {
  210.     freopen("input.txt","r",stdin);
  211.     freopen("output.txt","w",stdout);
  212.  
  213.     input();
  214.     return 0;
  215. }


Editing is locked.