39、数据结构与算法实战：计算器的改良

数据结构与算法39-计算器的改良

题目背景

NCL是一家专门从事计算器改良与升级的实验室，最近该实验室收到了某公司所委托的一个任务：需要在该公司某型号的计算器上加上解一元一次方程的功能。实验室将这个任务交给了一个刚进入的新手 ZL 先生。

题目描述

为了很好的完成这个任务，ZL 先生首先研究了一些一元一次方程的实例：

• 4 + 3 x = 8 4+3x=8 4+3x=8。
• 6 a − 5 + 1 = 2 − 2 a 6a-5+1=2-2a 6a−5+1=2−2a。
• − 5 + 12 y = 0 -5+12y=0 −5+12y=0。

ZL先生被主管告之，在计算器上键入的一个一元一次方程中，只包含整数、小写字母及 +、-、= 这三个数学符号（当然，符号“-”既可作减号，也可作负号）。方程中并没有括号，也没有除号，方程中的字母表示未知数。

你可假设对键入的方程的正确性的判断是由另一个程序员在做，或者说可认为键入的一元一次方程均为合法的，且有唯一实数解。

输入格式

一个一元一次方程。

输出格式

解方程的结果（精确至小数点后三位）。

样例 #1

样例输入 #1

6a-5+1=2-2a

样例输出 #1

a=0.750

参考程序

class Var():
    def __init__(self, coef, name):
        self.coef = coef
        self.name = name
class PartEqua():
    def __init__(self):
        self.constant = 0
        self.factor = Var(0, "")

    def AddFactor(self, coef, name):
        temp_factor = Var(coef, name)
        if self.factor.name == "":
            self.factor = temp_factor
        else:
            self.factor.coef += coef

    def AddConst(self, num):
        self.constant += num
def Split(inp):
    ls = []
    substr = ""
    for i in range(len(inp)):
        if inp[i] not in "+-":
            substr += inp[i]
        elif inp[i] == '+':
            ls.append(substr)
            substr = ""
        elif inp[i] == '-':
            if substr:
                ls.append(substr)
            substr = "-"
    if substr:
        ls.append(substr)
    return ls
def GetPartEqua(part_inp):
    part_equa = PartEqua()

    for item in Split(part_inp):
        try:
            num = eval(item)
            part_equa.AddConst(num)
        except:
            tmp_coef = ""
            for i in range(len(item)):
                if item[i] == '-':
                    tmp_coef += '-'
                    continue
                if item[i].isdigit():
                    tmp_coef += item[i]
                else:
                    break
            if tmp_coef == "":
                part_equa.AddFactor(1, item[i:])
            elif tmp_coef == "-":
                part_equa.AddFactor(-1, item[i:])
            else:
                part_equa.AddFactor(eval(tmp_coef), item[i:])
    return part_equa
inp=input()
# inp = "-a+1a-3=a-3"
left_part, right_part = map(GetPartEqua, inp.split("="))

if left_part.factor.name != "":
    name = left_part.factor.name
else:
    name = right_part.factor.name
coef = left_part.factor.coef - right_part.factor.coef
const = right_part.constant - left_part.constant
if coef < 0:
    coef = -coef
    const = -const
print("{0}={1:.3f}".format(name, const / coef))

思路

将大问题分解，首先一个方程可以分解为左右两部分，这两部分式子可以用相同的方法进行处理。对于等号一边的式子，使用+、-将式子拆成多个项，子式分为常数项和含字母的项，这两种项应当用不同的数据结构表示。对于含字母的项，又分为系数和字母。将数据结构分析清楚后再考虑运算操作。解方程的过程实际上就是：合并同类项，将含字母的项放在一边，将常数项放在另一边，未知数系数化为1.因此，项之间的合并运算分为含字母项的合并运算以及常数项的合并运算。
其他特殊情况需要考虑的，比如只有等号一边有未知项、未知数系数为负数但常数项为0，此时应输出0.000,见下面的参考样例。
复杂的数据结构问题的做法：往往都需要我们先将问题分解，分析清楚什么是基本的数据结构，有哪些类型的数据结构，然后再考虑定义在这些数据结构上的操作。最后再考虑求解整个大问题。

其他参考样例 样例输入

5=y
-a+1a-3=a-3

样例输出 #1

y=5.000
a=0.000

版权声明：本文不是「本站」原创文章，版权归原作者所有 | 原文地址: