题目描述

leetcode640. 求解方程

求解一个给定的方程,将x以字符串 "x=#value" 的形式返回。该方程仅包含 '+''-' 操作,变量 x 和其对应系数。

如果方程没有解,请返回 "No solution" 。如果方程有无限解,则返回 “Infinite solutions”

如果方程中只有一个解,要保证返回值 'x' 是一个整数。

 

示例 1:

输入: equation = "x+5-3+x=6+x-2"
输出: "x=2"

示例 2:

输入: equation = "x=x"
输出: "Infinite solutions"

示例 3:

输入: equation = "2x=x"
输出: "x=0"

 

 

提示:

  • 3 <= equation.length <= 1000
  • equation 只有一个 '='.
  • equation 方程由整数组成,其绝对值在 [0, 100] 范围内,不含前导零和变量 'x' 。 ​​​

题解——左右求值解方程

思路

其实对于所有的方程,不论是加减乘除括号都有,还是像这题的只有加减,我们都只要求出等号两边的值(其实是x的多项式),使其相等以解出未知数,就得到了答案。

对于求值的过程,类似于224.基本计算器227.基本计算器II,区别就是遇到的数字可能是x的系数,要判定一下。

对于这题,由于只有加减,我们只要保存两边的x的系数常数值,则结果就是(right_val-left_val)/(left_cnt/right_cnt)

具体实现过程:用一个sign记录符号(默认为正),一个flag记录当前是在左边还是右边,遍历一遍,如果发现+,-,改变sign,如果发现=,改变flagsign,如果是数字,则截取一个完整的数字(注意:结束时,i数字后的位置),并判断此处是不是x,如果是x,存入cnt,否则存入val--i以与for循环的++i抵消,使进入循环时i仍处于数字后的位置。结束后,用上面的式子解出x特判分母为零的情况

代码看上去有点长,但实际上都是条件判断,难度不大;这题可以看做是基本计算器模板的应用,如果再引入了乘除、括号,也只要用同样的方法处理即可(栈、优先级列表……)。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
string solveEquation(string equation) {
int left_val=0,right_val=0,left_cnt=0,right_cnt=0;//cnt保存x系数,val保存常数值
bool sign=1,flag=0;//sign代表符号,flag标记是左边还是右边
for(int i=0;i<equation.size();++i)//遍历
{
if(equation[i]=='+') sign=1;//改变符号
else if(equation[i]=='-') sign=0;//改变符号
else if(equation[i]=='=') { flag=1; sign=1;}//找到等号,flag置为true,sign置为默认(正)
else if(equation[i]>='0'&&equation[i]<='9')//找到数字
{
int num=0;
while(i<equation.size()&&equation[i]>='0'&&equation[i]<='9')//获取完整的数字
num=num*10+equation[i++]-'0';
if(i<equation.size()&&equation[i]=='x')//如果后面是x,保存到cnt里
(flag?right_cnt:left_cnt)+=sign?num:-num;
else//否则存入常数
{
(flag?right_val:left_val)+=sign?num:-num;
--i;//与++i抵消
}
}
else//遇到单独的x,存入cnt,用flag指示左右
(flag?right_cnt:left_cnt)+=sign?1:-1;
}
if(left_cnt==right_cnt)//如果左右未知数数量相等,若常数也相等,无穷多解,否则无解
return left_val==right_val?"Infinite solutions":"No solution";
return "x="+to_string((right_val-left_val)/(left_cnt-right_cnt));//计算答案并返回
}
};