UVa 215 Spreadsheet Calculator

题目分析本题要求实现一个简单的电子表格计算器。电子表格是一个矩形网格每个单元格包含一个整数或者一个表达式。表达式由整数常量、单元格引用以及和-运算符组成计算时遵循从左到右的结合顺序。输入首先给出行数rrr和列数ccc其中r≤20r \leq 20r≤20c≤10c \leq 10c≤10。行用大写字母A\texttt{A}A到T\texttt{T}T标记列用数字000到999标记因此单元格A0\texttt{A0}A0表示第111行第111列。随后按行主序输入每个单元格的内容。输入以0 0结束。输出要求分为两种情况如果所有单元格都能成功计算无循环引用则输出整个表格列号右对齐宽度为666每行以行字母开头。如果存在循环引用导致部分单元格无法计算则按行主序输出所有未计算单元格的标签、原始表达式每个单元格一行。解题思路核心难点本题的核心难点在于处理循环依赖。例如单元格A1\texttt{A1}A1引用了B1\texttt{B1}B1而B1\texttt{B1}B1又引用了A1\texttt{A1}A1这就形成了循环引用导致无法计算出数值。解决方案我们可以采用带标记的深度优先搜索DFS\texttt{DFS}DFS 来计算每个单元格的值表达式预处理对于每个单元格的原始表达式将运算符和-用空格包围以便后续使用字符串流进行拆分。注意减法运算符前的负号需要与操作数分开处理。递归求值定义函数evaluate(i, j)计算单元格(i,j)(i, j)(i,j)的值。在求值过程中如果当前单元格已经计算过直接返回其值。否则将其表达式拆分成若干项每个项是整数或单元格引用。对于每个项调用getValue获取其值。如果getValue返回false说明存在循环引用则当前单元格也无法计算。循环检测使用一个集合undefined记录当前递归路径上正在计算的单元格标签。当遇到一个已经在集合中的单元格引用时说明形成了循环此时返回false。这就是典型的DFS\texttt{DFS}DFS环检测方法。输出处理遍历所有单元格尝试计算。如果全部成功输出格式化表格。否则输出所有未成功计算的单元格的原始表达式。代码结构说明trim(line)去除行末尾的空白字符。split(line)将表达式中的运算符和-替换为空格便于分词。注意减法运算符前插入一个空格使其成为独立的负号标记。getValue(variable, value)解析一个字符串项可能为整数或单元格引用递归计算其数值。evaluate(i, j)计算当前单元格的值。calculate()主计算函数决定最终输出格式。代码实现// Spreadsheet Calculator// UVa ID: 215// Verdict: Accepted// Submission Date: 2016-04-30// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intcell[20][10];// 存储每个单元格的计算结果boolcalculated[20][10];// 标记单元格是否已成功计算string original[20][10];// 存储单元格的原始表达式string expression[20][10];// 存储预处理后的表达式便于拆分introws,columns;// 表格的行数和列数setstringundefined;// 存储当前递归路径上的单元格标签用于检测循环引用// 去除字符串末尾的空白字符stringtrim(string line){for(intiline.length()-1;i0;i--)if(isblank(line[i]))line.erase(line.begin()i);returnline;}// 预处理表达式将 和 - 替换为空格便于字符串流拆分stringsplit(string line){for(intiline.length()-1;i0;i--){if(line[i])line[i] ;elseif(line[i]-)line.insert(line.begin()i, );// 在 - 前插入空格}returnline;}boolevaluate(int,int);// 获取一个操作数的值操作数可以是整数或单元格引用boolgetValue(string variable,intvalue){intsign1;if(variable[0]-){sign-1;variable.erase(variable.begin());}// 如果操作数是单元格引用以字母开头if(isalpha(variable[0])){intiivariable[0]-A;intjjvariable[1]-0;if(calculated[ii][jj]){valuesign*cell[ii][jj];returntrue;}else{// 检测循环引用如果当前单元格已在递归路径中if(undefined.count(variable)0)returnfalse;undefined.insert(variable);// 标记进入当前单元格if(evaluate(ii,jj))// 递归计算引用的单元格{undefined.erase(variable);// 递归返回清除标记calculated[ii][jj]true;valuesign*cell[ii][jj];returntrue;}returnfalse;}}// 操作数是整数常量else{valuesign*stoi(variable);returntrue;}}// 计算单元格 (i, j) 的值boolevaluate(inti,intj){string variable;vectorstringvariables;istringstreamiss(expression[i][j]);// 拆分预处理后的表达式得到各个操作数while(issvariable)variables.push_back(variable);intsum0;for(inti0;ivariables.size();i){intvalue;if(getValue(variables[i],value))sumvalue;elsereturnfalse;}cell[i][j]sum;calculated[i][j]true;returntrue;}// 主计算函数voidcalculate(){intcellCalculated0;for(inti0;irows;i)for(intj0;jcolumns;j){undefined.clear();if(calculated[i][j]||evaluate(i,j))cellCalculated;}// 所有单元格均成功计算输出整个表格if(cellCalculatedrows*columns){cout ;for(inti0;icolumns;i)coutsetw(6)righti;coutendl;for(inti0;irows;i){cout(char)(Ai);for(intj0;jcolumns;j)coutsetw(6)rightcell[i][j];coutendl;}}// 存在循环引用输出所有未计算的单元格的原始表达式else{for(inti0;irows;i)for(intj0;jcolumns;j)if(calculated[i][j]false)cout(char)(Ai)j: original[i][j]endl;}}intmain(){cin.tie(0);cin.sync_with_stdio(false);string line;while(cinrowscolumns,rowscolumns){cin.ignore();for(inti0;irows;i)for(intj0;jcolumns;j){getline(cin,line);original[i][j]trim(line);expression[i][j]split(original[i][j]);calculated[i][j]false;cell[i][j]0;}calculate();coutendl;}return0;}