在一个变量中求解线性方程

Question

在作为函数的字符串输入给出的一个变量中求解线性方程的最有效算法是什么？例如,对于输入字符串:

"x + 9 - 2 - 4 + x = - x + 5 - 1 + 3 - x"

输出应为1.

当我在字符串中遇到空格时,我正在考虑使用堆栈并将每个字符串标记推到它上面.如果输入是波兰表示法,那么从堆栈中弹出数字以获得结果会更容易,但我不确定采取何种方法.

这是一个面试问题.

Answer 1

求解线性方程组是(我希望)你非常容易,一旦你已经计算出的系数a,并b在方程a * x + b = 0.

因此,问题的难点在于解析表达式并"评估"它以找到系数.您的示例表达式非常简单,它只使用运算符一元-,二进制-,二进制+.而且=,你可以特别处理.

从问题来看,解决方案是否还应处理涉及二进制*和/括号的表达式并不清楚.我想知道面试问题是否有意:

• 让你写一些简单的代码,或
• 在你写任何东西之前让你问问题的真正范围.

两者都是重要的技能:-)

甚至可能是这个问题的意图:

• 分离那些有很多写解析器经验的人(他们会尽可能快地解决它/解决它)从那些没有解决方案的人(他们可能在几分钟内完全解决它,至少没有一些提示).

无论如何,为了满足未来更复杂的需求,解析算术表达式有两种常用方法:递归下降或Dijkstra的分流码算法.您可以查看这些内容,如果您只需要1.0版中的简单表达式,那么您可以使用简化形式的Dijkstra算法.然后,一旦解析了表达式,就需要对其进行求值:使用线性表达式中的值x并将其解释=为具有最低可能优先级的运算符,这意味着"减去".结果是线性表达式x等于0.

如果你不需要复杂的表达式,那么一旦你对它进行了标记,就可以从左到右直接评估这个简单的例子[*]:

x
x + 9
// set the "we've found minus sign" bit to negate the first thing that follows
x + 7 // and clear the negative bit
x + 3
2 * x + 3
// set the "we've found the equals sign" bit to negate everything that follows
3 * x + 3
3 * x - 2
3 * x - 1
3 * x - 4
4 * x - 4

最后,解决a * x + b = 0为x = - b/a.

[*]示例标记化代码,在Python中:

acc = None
for idx, ch in enumerate(input):
    if ch in '1234567890':
        if acc is None: acc = 0
        acc = 10 * acc + int(ch)
        continue
    if acc != None:
        yield acc
        acc = None
    if ch in '+-=x':
        yield ch
    elif ch == ' ':
        pass
    else:
        raise ValueError('illegal character "%s" at %d' % (ch, idx))

替代示例令牌化代码,也在Python中,假设在示例中将始终存在令牌之间的空格.这会将令牌验证留给解析器:

return input.split()