题目描述

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，如果发现=，改变flag和sign，如果是数字，则截取一个完整的数字(注意：结束时，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));//计算答案并返回
    }
};