题目描述本题要求计算一系列简单C表达式的值。每个表达式占一行长度不超过110110110个字符。表达式中只包含简单的整型变量和有限的操作符没有常量。共有262626个变量a到z仅小写字母。在每个表达式开始求值时这262626个变量的初值分别为111到262626即a 1,b 2, …,z 26。每个变量在表达式中最多出现一次许多变量可能根本不会出现。表达式中可以出现的操作符包括二元操作符和-加法与减法具有通常的含义一元操作符和--自增和自减可以出现在变量之前或之后自增/自减运算符的语义前缀形式如a在变量值被使用之前先将其增加111后缀形式如a在变量值被使用之后再将其增加111减号运算符-同理为自减求值算法简化版找出每个变量前面的运算符生成赋值语句递增这些变量并从表达式中移除这些运算符找出每个变量后面的运算符生成赋值语句递增这些变量并从表达式中移除这些运算符此时表达式只包含二元运算符计算其值按顺序执行第一步的赋值 → 第三步的计算 → 第二步的赋值输入格式输入包含多行每行一个表达式直到文件结束。输出格式对于每个表达式第一行输出Expression:后跟原表达式第二行输出value 后跟表达式的值后续每行输出变量 值按字母顺序输出只输出表达式中使用过的变量样例输入ab b-z ab- - c cf- - - - a f- - c- - d- e样例输出Expression: ab value 3 a 1 b 2 Expression: b-z value -24 b 2 z 26 Expression: ab- - c value 6 a 1 b 1 c 4 Expression: cf- - - - a value 9 a 0 c 3 f 5 Expression: f- - c- - d- e value 7 c 2 d 4 e 6 f 5题目分析问题的本质这是一个表达式求值问题但具有特殊的自增/自减运算符语义。由于表达式不包含括号且变量最多出现一次我们可以采用线性扫描 状态机的方式解析。关键难点自增/自减运算符的前缀与后缀区别需要正确处理前缀a先自增再使用值后缀a先使用值再自增由于变量在表达式中最多出现一次我们不需要考虑复杂的副作用顺序问题。解析策略由于表达式中可能含有空格需要先过滤掉空白字符。然后从左到右扫描识别一元运算符、-、、--二元运算符、-变量名a~z表达式结构简化观察表达式ab- - c去除空格后ab--c根据自增/自减的语义可以将其分解为前缀或--紧跟在二元运算符之后后缀或--紧跟在变量之后参考代码// Evaluating Simple C Expressions// UVa ID: 327// Verdict: Accepted// Submission Date: 2016-07-01// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);charreaded[1024];// 存储过滤后的表达式字符string line;while(getline(cin,line)){// 初始化变量-1 表示未使用否则存储最终值intvariable[26]{};intused[26]{};intposition0;intvalue0;// 过滤空白字符将有效字符存入 readedfor(inti0;iline.length();i){if(line[i] ||line[i]\t)continue;if(line[i]||line[i]-||isalpha(line[i])){readed[position]line[i];// 模式1后缀自增/自减 ... 变量 或 变量 --// 序列变量、运算符、运算符if(position3isalpha(readed[position-3])){if((readed[position-1]readed[position-2])||(readed[position-1]-readed[position-2]-)){intsign1;intletterreaded[position-3]-a;// 检查前面的符号决定正负if(position4readed[position-4]-)sign-1;// 后缀形式使用原值然后自增/自减value(letter1)*sign;used[letter]1;// 最终值原值 1 或 -1variable[letter]letter(readed[position-1]?2:0);// 移除已处理的 3 或 4 个字符position-(position4?4:3);}}// 模式2前缀自增/自减 变量 或 -- 变量// 序列运算符、运算符、变量elseif(position3isalpha(readed[position-1])){if((readed[position-2]readed[position-3])||(readed[position-2]-readed[position-3]-)){intsign1;intletterreaded[position-1]-a;if(position4readed[position-4]-)sign-1;// 前缀形式先自增/自减再使用值value(letter(readed[position-2]?2:0))*sign;used[letter]1;variable[letter]letter(readed[position-2]?2:0);position-(position4?4:3);}}}}// 处理剩余的二元表达式只有变量和 / - 运算符for(inti0;iposition;i)if(isalpha(readed[i])){intletterreaded[i]-a;used[letter]1;// 如果变量尚未赋值没有自增/自减初始值为 letter1if(variable[letter]0)variable[letter]letter1;intsign1;if(i0readed[i-1]-)sign-1;valuesign*variable[letter];}// 输出结果coutExpression: line\n;cout value value\n;for(inti0;i26;i)if(used[i])cout (char)(ai) variable[i]\n;}return0;}