v 0. Pasted by slipstak2 as cpp at 2011-01-11 14:15:10 MSK and set expiration to never.

Paste will expire never.

  1. // Меньшиков. Тренировка 14.
  2. // 14F. Электронная таблица [sprsheet]
  3. // ibelyaev: 11Jan2011
  4.  
  5. #include <iostream>
  6. #include <cstdio>
  7. #include <string>
  8. #include <vector>
  9. #include <stack>
  10. #include <set>
  11. #include <string.h>
  12.  
  13. using namespace std;
  14. const int size = 26 * 9;
  15. const int MAX_SIZE = 255 + 10;
  16. enum TYPE {WHITE, GRAY, BLACK};
  17. int n;
  18. vector<string> exp(size);
  19. vector<int> value(size);
  20. vector<set<int> > adj(size);
  21. vector<TYPE> used(size, WHITE);
  22.  
  23. stack<char> opers;
  24. stack<int>  numbers;
  25. void trim(string &str)
  26. {
  27.     while (str[0] == ' ')
  28.         str.erase(0,1);
  29.     while (str[str.size()-1]==' ')
  30.         str.erase(str.size()-1,1);
  31. }
  32. int code(const char *pos) {
  33.     return (*pos - 'A') * 9 + *(pos+1) - '1';
  34. }
  35. int code(const string &s)
  36. {
  37.     return code(s.c_str());
  38. }
  39.  
  40. bool isLetter(char c) {
  41.     return 'A' <= c && c<= 'Z';
  42. }
  43. bool isDigit(char c) {
  44.     return '0'<= c && c <= '9';
  45. }
  46. void fillAdj(int index, string s)
  47. {
  48.     for (int i = 0; i<s.size();i++) {
  49.         if (isLetter(s[i])) {
  50.             adj[index].insert(code(s.substr(i,2)));
  51.         }
  52.     }
  53. }
  54. void input()
  55. {
  56.     scanf("%d\n",&n);
  57.     string str,f,s;
  58.     int pos;
  59.     for (int i=0;i<n;i++)
  60.     {
  61.         getline(cin,str);
  62.         pos = str.find('=');
  63.         f = str.substr(0,pos);
  64.         s = str.substr(pos+1,str.size() - (pos+1));
  65.         trim(f);
  66.         trim(s);   
  67.         exp[code(f)] = s;
  68.         fillAdj(code(f),s);
  69.     }
  70. }
  71. void dfs(int pos, vector<int> &G, bool &isCircle) {
  72.    
  73.     used[pos] = GRAY;
  74.     for (set<int>::iterator it=adj[pos].begin(); it != adj[pos].end(); it++) {
  75.        
  76.         if (isCircle) return;
  77.  
  78.         if (used[*it] == GRAY) {
  79.             isCircle = true;
  80.             break;
  81.         }
  82.         else if (used[*it] == WHITE){
  83.             dfs(*it,G,isCircle);
  84.         }
  85.     }
  86.     G.push_back(pos);
  87.     used[pos] = BLACK;
  88. }
  89. bool topological_sort(vector<int> &G) {
  90.  
  91.     bool isCircle = false;
  92.     dfs(0,G,isCircle);
  93.     return isCircle;
  94. }
  95. inline bool isEnd(const char * pos) {
  96.     return *pos == 0;
  97. }
  98. void SkipSep(char* &pos) {
  99.     while (!isEnd(pos) && *pos == ' ')
  100.         pos++;
  101. }
  102. bool isOper(const char* pos) {
  103.     return !isEnd(pos) &&
  104.      (  *pos == '+' ||
  105.         *pos == '-' ||
  106.         *pos == '*' ||
  107.         *pos == '/' );
  108. }
  109. int prior (const char pos) {
  110.     if (pos == '+' || pos == '-')
  111.         return 1;
  112.     else
  113.         return 2;
  114. }
  115. void ReadCell(char* &pos, int &number) {
  116.     int cell = code(pos);
  117.     pos+=2;
  118.     number = value[cell];
  119. }
  120. void ReadNumber (char* &pos, int &number) {
  121.     number = 0;
  122.     while (!isEnd(pos) && isDigit(*pos)) {
  123.         number = number * 10 + (*pos - '0');
  124.         pos++;
  125.     }
  126. }
  127. void calcExp(char* &pos, int &res);
  128. void ReadNextValue(char* &pos, int &number) {
  129.  
  130.     if (*pos == '(') {
  131.         pos++;
  132.         calcExp(pos,number);
  133.         pos++;
  134.     }
  135.     else {
  136.  
  137.         if (isLetter(*pos))
  138.             ReadCell(pos, number);
  139.         if (isDigit(*pos))
  140.             ReadNumber(pos, number);
  141.     }
  142. }
  143. int calc(int f, int s, char oper) {
  144.     switch(oper) {
  145.         case '+': return f + s;
  146.         case '-': return f - s;
  147.         case '*': return f * s;
  148.         case '/': if (s == 0)
  149.                       return 0;
  150.                   else
  151.                       return f/s;
  152.     }
  153. }
  154. void calcExp(char* &pos, int &res) {
  155.  
  156.     stack<int> locNumbers;
  157.     stack<char> locOper;
  158.     do
  159.     {
  160.         SkipSep(pos);
  161.         if (isOper(pos)) {
  162.             char curOper = *pos++;
  163.            
  164.             while (!locOper.empty() && prior(locOper.top()) > prior(curOper)) {
  165.                
  166.                 int s = locNumbers.top();               locNumbers.pop();
  167.                 int f = locNumbers.top();               locNumbers.pop();
  168.                 int locRes = calc(f,s,locOper.top());   locOper.pop();
  169.                 locNumbers.push(locRes);
  170.             }
  171.             locOper.push(curOper);
  172.         }
  173.         else {
  174.             int number = 0;
  175.             ReadNextValue(pos, number);
  176.             locNumbers.push(number);
  177.         }
  178.         SkipSep(pos);
  179.     } while (!isEnd(pos) && *pos != ')');
  180.  
  181.     while (!locOper.empty()) {
  182.         int s = locNumbers.top(); locNumbers.pop();
  183.         int f = locNumbers.top(); locNumbers.pop();
  184.         int locRes = calc(f,s,locOper.top());
  185.         locOper.pop();
  186.         locNumbers.push(locRes);
  187.     }
  188.     res = locNumbers.top();
  189. }
  190. void solve()
  191. {
  192.     vector<int> G;
  193.     if (topological_sort(G)) {
  194.         cout<<(int)1e6;
  195.     }
  196.     else {
  197.         if (G.empty()) G.push_back(0);
  198.  
  199.         for (int i=0;i<G.size();i++) {
  200.             char *buf = new char[MAX_SIZE];
  201.             strcpy(buf,exp[G[i]].c_str());
  202.             calcExp(buf,value[G[i]]);
  203.         }
  204.         cout<<value[0];
  205.     }
  206. }
  207. int main()
  208. {
  209.     freopen("input.txt","r",stdin);
  210.     freopen("output.txt","w",stdout);
  211.  
  212.     input();
  213.     solve();
  214.     return 0;
  215. }


Editing is locked.