UVa 397 Equation Elation

题目描述小学代数教科书的作者希望你编写一个程序来求解简单的代数方程。所有问题都将采用代数等式的形式包含整数常量、四个基本算术运算符、等号和一个变量。例如12 - 4*3 x输出应逐步显示求解过程12 - 4*3 x 12 - 12 x 0 x运算遵循标准优先级先乘除从左到右后加减从左到右。所有除法结果均为整数。输入格式输入文件包含多个待求解的方程。每个方程包含111到202020个运算符222到212121个整数操作数。整数可以带有前导符号即一元运算符。输入行中的空格是可选的。变量名由111到888个字母组成。输出格式每个问题的输出以原问题开始然后每执行一次操作输出一行。每个问题的输出之间用一个空行分隔。样例输入3*44-1/1xyzzy 122*12/2-1y 2*-3-6-4r样例输出3 * 4 4 - 1 / 1 xyzzy 3 * 4 4 - 1 xyzzy 12 4 - 1 xyzzy 16 - 1 xyzzy 15 xyzzy 12 2 * 12 / 2 - 1 y 12 24 / 2 - 1 y 12 12 - 1 y 24 - 1 y 23 y 2 * -3 -6 - 4 r -6 -6 - 4 r -12 - 4 r -16 r题目分析问题的本质这是一个算术表达式逐步求值问题。需要解析表达式处理一元运算符按优先级逐步化简表达式每次化简后输出当前表达式最终得到变量值表达式结构表达式包含整数可能带有前导或-运算符*、/、、-等号变量名由字母组成求值策略先处理所有乘除运算从左到右再处理所有加减运算从左到右每次只执行一个运算然后输出参考代码// Equation Elation// UVa ID: 397// Verdict: Accepted// Submission Date: 2016-07-03// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intmain(intargc,char*argv[]){ios::sync_with_stdio(false);intcases0;string line;while(getline(cin,line)){// 去除空格for(intiline.length()-1;i0;i--)if(isblank(line[i]))line.erase(line.begin()i);vectorstringequation;// 解析表达式intposition0;while(positionline.length()){if(line[position]*||line[position]/){equation.push_back(string(1,line[position]));// 读取数字可能带符号string value;valueline[position];while(positionline.length()isdigit(line[position]))valueline[position];equation.push_back(to_string(stoi(value)));}elseif(line[position]||line[position]-){// 判断是一元还是二元运算符if(position0||(line[position-1]*||line[position-1]/||line[position-1]||line[position-1]-)){// 一元运算符属于数字的一部分string value;valueline[position];while(positionline.length()isdigit(line[position]))valueline[position];equation.push_back(to_string(stoi(value)));}else{// 二元运算符equation.push_back(string(1,line[position]));string value;valueline[position];while(positionline.length()isdigit(line[position]))valueline[position];equation.push_back(to_string(stoi(value)));}}elseif(line[position]){equation.push_back();string variable;position;while(positionline.length())variableline[position];equation.push_back(variable);}elseif(isdigit(line[position])){string value;while(positionline.length()isdigit(line[position]))valueline[position];equation.push_back(to_string(stoi(value)));}}// 测试用例间空行if(cases0)coutendl;// 逐步化简while(equation.size()3){// 输出当前状态for(inti0;iequation.size();i){if(i0)cout ;coutequation[i];}cout\n;// 优先处理乘除boolupdatedfalse;for(inti0;iequation.size();i)if(equation[i]*||equation[i]/){updatedtrue;intastoi(equation[i-1]);intbstoi(equation[i1]);intresult(equation[i]*)?a*b:a/b;equation[i-1]to_string(result);equation.erase(equation.begin()i);equation.erase(equation.begin()i);break;}// 没有乘除处理加减if(!updated){for(inti0;iequation.size();i)if(equation[i]||equation[i]-){intastoi(equation[i-1]);intbstoi(equation[i1]);intresult(equation[i])?ab:a-b;equation[i-1]to_string(result);equation.erase(equation.begin()i);equation.erase(equation.begin()i);break;}}}// 输出最终结果for(inti0;iequation.size();i){if(i0)cout ;coutequation[i];}cout\n;}return0;}