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

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