1

関数への文字列入力として与えられた 1 つの変数で線形方程式を解く最も効率的なアルゴリズムは何でしょうか? たとえば、入力文字列の場合:

「x + 9 – 2 - 4 + x = – x + 5 – 1 + 3 – x」

出力は 1 になるはずです。

スタックを使用して、文字列内にスペースが発生したときに各文字列トークンをスタックにプッシュすることを検討しています。入力がポーランド語表記の場合は、スタックから数値を取り出して結果を得る方が簡単だったでしょうが、ここでどのようなアプローチを取るべきかわかりません。

面接の質問です。

4

4 に答える 4

1

検討：

from operator import add, sub
def ab(expr):
    a, b, op = 0, 0, add
    for t in expr.split():
        if   t == '+': op = add
        elif t == '-': op = sub
        elif t == 'x': a = op(a, 1)
        else         : b = op(b, int(t))
    return a, b

このような式1 + x - 2 - x...を指定すると、正規形に変換され、ax+b係数のペアが返されます(a,b)。

ここで、式の両方の部分から係数を取得しましょう。

le, ri = equation.split('=')    
a1, b1 = ab(le)
a2, b2 = ab(ri)

最後に自明な方程式を解きますa1*x + b1 = a2*x + b2:

x = (b2 - b1) / (a1 - a2)

もちろん、これは演算子の優先順位や括弧なしで、この特定の例を解決するだけです。後者をサポートするには、手動でコーディングする方が簡単なパーサーが必要です。おそらく再帰的な降下パーサーです。

于 2013-04-29T10:47:09.700 に答える