UVA215 Spreadsheet

这道题题目大意就是计算带有单元格引用的各单元格的值。

这道题本身不难，有以下几个关键点：

1.如何判断一个单元格循环引用

2.注意对字符串的细致处理

我出现的错误出现在以上两个方面，思路本身是不难的。

第一条，我的错误在于第66行起初并没有加上。如果不加那一行，就代表了你同层之间不能是相同的单元格，但实际情况是逐层往下递归过程中出现重复才是真正的循环引用。

1到2到3到1属于循环引用，但假如去掉1,3连线，1随后会再访问一次，但此时我之前错误代码会认为出现循环引用，这实际上是两个相同单元格相加（A0+A0）

第二条，注意题目说的判断是单元格引用还是数值的方法很明白了，静下心来的仔细看，我的问题出在负数上。

  1 #include <cstdio>
  2 #include <cctype>
  3 #include <iostream>
  4 #include <set>
  5 #include <map>
  6 #include <climits>
  7 using namespace std;
  8 const int inv = INT_MIN;
  9 string maps[25][25];
 10 set<string> sheeps;
 11 int strtoint(string s,int begin,int &end){
 12     int i = begin;
 13     int sum = 0;
 14     for(;isdigit(s[i]);i++){
 15         sum = sum*10 + s[i] - '0';
 16     }
 17     end=i;
 18     return sum;
 19 }
 20 bool isdigits(const char * d){
 21     int i=0;
 22     for(i;d[i];i++){
 23         if(!isdigit(d[i]))return false;
 24     }
 25     return true;
 26 }
 27 int get_value(string str){
 28     string s = maps[str[0] - 'A'][str[1] - '0'];
 29     if(!sheeps.count(str) ){
 30         if(!isdigit(s[0]))sheeps.insert(str);
 31         }
 32     else return inv;
 33     int i=0;
 34     int sum = 0;
 35     char oper  = '+'; 
 36     while(i<s.size()){
 37         if(!isdigit(s[i])&&(i||s[i]!='-')){//注意
 38             if(s.substr(i,2)=="in")return inv;
 39             int v = get_value(s.substr(i,2));
 40             if(v == inv)return inv;
 41             switch(oper){
 42                 case '+':sum+=v;break;
 43                 case '-':sum-=v;break;
 44             }
 45             i+=2;
 46             if(i>=s.size())break;
 47             oper = s[i];
 48             i++;
 49         }
 50         else {
 51             if(s[i] == '-'){
 52                 i++;
 53                 if(oper == '+')oper = '-';
 54                 else oper = '+';
 55             }
 56             int v = strtoint(s,i,i);
 57             switch(oper){
 58                 case '+':sum+=v;break;
 59                 case '-':sum-=v;break;
 60             }
 61             if(i>=s.size())break;
 62             oper = s[i];
 63             i++;
 64         }
 65     }
 66     if(sheeps.count(str))sheeps.erase(str);
 67    return sum; 
 68 }
 69 
 70 int main(){
 71     int r,c;
 72     while(cin >> r >> c && (r || c)){
 73         for(int i=0;i<r*c;i++){
 74             cin >> maps[i/c][i%c];
 75         }
 76         map<string,string> invstr;
 77         for(int i=0;i<r*c;i++){
 78             if(!isdigits(maps[i/c][i%c].c_str())){
 79                 sheeps.clear();
 80                 string str ;
 81                 str.push_back(i/c+'A');
 82                 str.push_back(i%c+'0');
 83                 int v = get_value(str);
 84                 if(v==inv) {
 85                     invstr[str] = maps[i/c][i%c];
 86                     maps[i/c][i%c] = "in";
 87                 }
 88                 else maps[i/c][i%c] =to_string(v);
 89             }
 90         }
 91         if(invstr.empty()){
 92             putchar(' ');
 93             for(int i=0;i<c;i++)
 94                 printf("%6d",i);
 95             putchar('
');
 96             for(int i=0;i<r;i++){
 97                 putchar(i+'A');
 98                 for(int j=0;j<c;j++){
 99                     printf("%6s",maps[i][j].c_str());
100                 }
101                 putchar('
');
102             }  
103         }
104         else{
105             for(auto it = invstr.begin();it!=invstr.end();it++){
106                 cout << it->first <<": "<<it->second <<endl;
107             }
108         }
109         puts("");
110     }
111     return 0;
112 }