求解方程Java

文章发布较早，内容可能过时，阅读注意甄别。

# 题目

求解一个给定的方程，将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 只有一个 '='.
方程由绝对值在 [0, 100] 范围内且无任何前导零的整数和变量 'x' 组成。

# 思路

其实这类解析字符串的题都可以用状态机来实现

# 解法


class Solution {
    // 其实这类解析字符串的题都可以用状态机来实现，Java实现代码如下。
    // 简易状态机
    public String solveEquation(String equation) {
        char[] cs = equation.toCharArray();
        // 记录所有x的和
        int xCount = 0;
        // 记录所有数字的和
        int total = 0;
        // 是否等号左边
        boolean isLeft = true;
        for (int i = 0; i < cs.length; i++) {
            char c = cs[i];
            // 默认加法
            boolean add = true;
            int val = 0;
            switch (c) {
                case '=':
                    isLeft = false;
                    // 由于需要将等号左边数字的和移动到等号右边，所以需要取反
                    total = -total;
                    break;
                case 'x':
                    val = 1;
                case '0':
                case '1':
                case '2':
                case '3':
                case '4':
                case '5':
                case '6':
                case '7':
                case '8':
                case '9':
                    if (i - 1 >= 0 && cs[i - 1] == '-') add = false;
                    while (i < cs.length && cs[i] >= '0' && cs[i] <= '9') {
                        val = val * 10 + cs[i] - '0';
                        i++;
                    }
                    // 根据符号，进行取反操作
                    if (!add) val = -val;
                    if (isLeft) {
                        if (cs[i] == 'x') {
                            xCount += val;
                        } else {
                            total += val;
                        }
                    } else {
                        if (i < cs.length && cs[i] == 'x') {
                            // 在等号右边时，将x移到等号左边，所以要进行取返操作
                            xCount += -val;
                        } else {
                            total += val;
                        }
                    }
                    if (i < cs.length && cs[i] == '=') {
                        isLeft = false;
                        // 由于需要将左边的和移动到右边，所以需要取反
                        total = -total;
                    }
                    break;

            }
        }
        if (xCount != 0) {
            return "x" + "=" + (total / xCount);
        } else if (total == 0) {
            return "Infinite solutions";
        } else {
            return "No solution";
        }
    }
}

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

# 总结

分析出几种情况，然后分别对各个情况实现