题目分析本题要求实现一个简单的计算器语言Calculator Language\texttt{Calculator Language}Calculator Language简称CL\texttt{CL}CL的解释器。该语言支持变量A-Z、整数、四则运算加、减、乘、整除和赋值操作运算符优先级相同且为右结合括号可以任意嵌套。语言规则回顾变量A-Z共 26 个初始值为000在整个程序运行期间保持值直到被显式修改。运算符-*/所有运算符优先级相同右结合。括号(和)强制先计算括号内的表达式。负号仅出现在数字前如_2表示−2-2−2不会出现在变量前。空格可随意插入但负号与数字之间不能有空格。输入每行一个正确的CL\texttt{CL}CL表达式行长度不超过100100100个字符以#单独一行结束。输出对于每行表达式输出值发生改变的变量按字母顺序格式为变量 新值多个变量用,分隔。若没有变量改变输出No Change。关键点变量初值与保留每个变量在程序开始为000且上一次计算的结果会影响下一次。赋值也是运算符具有与等相同的优先级和右结合性因此A B 4等价于A (B 4)。负号处理输入中用_表示负号例如_2表示−2-2−2。多次赋值同一变量在一行中可能被多次赋值只输出最终值。没有变化的变量不输出比较执行前后的值只有变化了的才打印。解题思路本题的核心是表达式求值但由于运算符优先级相同且为右结合加上括号的支持最稳妥的方式是采用**中缀转后缀逆波兰表示法**再求值。整体流程读取一行去掉所有空格负号与数字之间本来无空格去除空格不影响负数解析。词法分析将字符串分解为token\texttt{token}token变量、数字、运算符、括号。数字可能带负号用_表示。中缀转后缀考虑右结合和括号。后缀表达式求值使用栈遇到变量时获取当前值遇到运算符则弹出两个操作数计算遇到则执行赋值并压入结果。记录变化求值前后比较变量值收集变化的变量按字母序输出。关键细节处理1. 负数的处理题目保证负号只出现在数字前且用_表示。在词法分析时当遇到_标记为负号然后继续读取数字组合成一个负的整数字面量作为一个NUMBER token\texttt{NUMBER token}NUMBER token。2. 中缀转后缀的调整由于题目中运算符是右结合的且优先级相同我们可以在转换时采用如下策略遇到操作数变量或数字直接输出到后缀队列。遇到左括号(入栈。遇到右括号)将栈顶直到左括号的运算符弹出。遇到运算符时因为优先级相同且右结合新来的运算符应该先于栈顶已有的相同优先级运算符被处理即栈顶的相同优先级运算符不应先弹出所以应直接将当前运算符入栈。但为了满足右结合实际实现中更简单的方式是反转表达式将(与)互换然后按左结合的常规方式处理最后再反转回来。这是很多 AC 代码采用的方法。本题的参考代码使用了这种“反转变换”技巧先将整个token\texttt{token}token序列反转。同时将(和)互换。然后进行标准的左结合中缀转后缀遇到运算符时弹出栈中优先级大于等于当前运算符的运算符。最后将得到的后缀序列反转回来。这样巧妙地将右结合转换成了左结合问题。3. 赋值运算符的处理在求值时弹出右操作数值或变量和左操作数必须是变量将右操作数的值赋给左变量同时压入该值作为结果以便参与外层运算。例如A B 4后缀形式为A B 4 。先计算B 4将4赋给B压入4。再计算A 4将4赋给A压入4。4. 变量初始值和不变化判断用两个数组original[26]和now[26]每行开始前将now复制到original保存旧值。执行完该行后比较now[i]与original[i]不同则记录。全局变量保留值因此下一行的旧值就是上一行的now。5. 输出格式严格按题目要求变量按字母顺序。等号两边空格A 4。逗号后跟一个空格。无变化输出No Change。代码实现// Calculator Language// UVa ID: 172// Verdict: Accepted// Submission Date: 2016-02-20// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;constintVARIABLE0,OPERATOR1,NUMBER2;structsymbol{inttoken,category;};intoriginal[26]{0};intnow[26]{0};vectorsymbolsymbols;voidcalculate(){stacksymboloperands;for(inti0;isymbols.size();i){symbol ssymbols[i];if(s.categoryVARIABLE||s.categoryNUMBER)operands.push(s);else{symbol aoperands.top();operands.pop();symbol boperands.top();operands.pop();intaa,bb,cc;if(a.categoryVARIABLE)aanow[a.token-A];elseaaa.token;if(b.categoryVARIABLE)bbnow[b.token-A];elsebbb.token;switch(s.token){case:ccaabb;break;case-:ccaa-bb;break;case*:ccaa*bb;break;case/:ccaa/bb;break;case:ccbb;now[a.token-A]bb;break;default:break;}operands.push((symbol){cc,NUMBER});}}}voidinfixToPostfix(){reverse(symbols.begin(),symbols.end());for(inti0;isymbols.size();i)if(symbols[i].categoryOPERATOR){if(symbols[i].token))symbols[i].token(;elseif(symbols[i].token()symbols[i].token);}stacksymboloperands,operators;for(inti0;isymbols.size();i){symbol ssymbols[i];if(s.categoryNUMBER||s.categoryVARIABLE)operands.push(s);else{if(s.token()operators.push(s);elseif(s.token)){while(!operators.empty()operators.top().token!(){operands.push(operators.top());operators.pop();}if(!operators.empty())operators.pop();}else{if(operators.empty()||operators.top().token()operators.push(s);else{while(!operators.empty()operators.top().token!(){operands.push(operators.top());operators.pop();}operators.push(s);}}}}while(!operators.empty()){operands.push(operators.top());operators.pop();}symbols.clear();while(!operands.empty()){symbols.insert(symbols.begin(),operands.top());operands.pop();}}voidparse(string line){for(intiline.length()-1;i0;i--)if(line[i] ||line[i]\t)line.erase(line.begin()i);symbols.clear();intindex0;while(indexline.length()){if((line[index]0line[index]9)||line[index]_){intsignline[index]_?-1:1;intoperands0;if(line[index]_)index;while(indexline.length()(line[index]0line[index]9)){operandsoperands*10line[index]-0;index;}symbols.push_back((symbol){operands*sign,NUMBER});}elseif(line[index]Aline[index]Z){symbols.push_back((symbol){line[index],VARIABLE});index;}else{symbols.push_back((symbol){line[index],OPERATOR});index;}}infixToPostfix();calculate();vectorintoperands;for(inti0;i26;i)if(now[i]!original[i])operands.push_back(i);if(operands.size()0){for(inti0;ioperands.size();i){cout(char)(Aoperands[i]) now[operands[i]];if(ioperands.size()-1)cout, ;}cout\n;}elsecoutNo Change\n;}intmain(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);string line;while(getline(cin,line),line!#){copy(now,now26,original);parse(line);}return0;}总结本题考察的核心是带右结合运算符和赋值操作的表达式求值。通过中缀转后缀并利用栈进行求值可以清晰且正确地处理优先级、括号和右结合性。同时需要注意负数的表示_符号和变量值的持久化。代码实现采用反转括号的手法简化了右结合的中缀转换是一个值得借鉴的技巧。