4

私は現在、singpathと呼ばれるWebサイトでPythonの問題セットに取り組んでいます。質問は：

プレフィックス評価スペースや構文エラーなしでプレフィックス表記の形式で算術式を評価する関数を作成します。式は文字列として指定され、式のすべての数値は0〜9の整数であり、演算子は+（加算）、-（減算）、*（乗算）、/（除算）、％（モジュロ）です。 Pythonとまったく同じように動作します。ポーランド記法とも呼ばれる接頭辞表記法は、論理、算術、および代数の表記法の形式です。オペランドの左側に演算子を配置します。演算子のアリティが固定されている場合、結果は、あいまいさなしに解析できる括弧またはその他の括弧がない構文になります。

これは十分に単純に見えますが、文字列はデータをつなぎ合わせるために入力にスペースを入れずに凝縮されています。モジュールをインポートせずに文字列からデータを分離するにはどうすればよいですか？さらに、データの結果を使用して、与えられた方程式を解くにはどうすればよいですか？また、Singpathソリューションは、標準のPythonライブラリにないメソッドを使用できない1つの関数に含まれている必要があることをminfに留めておいてください。これには、ソリューション内で宣言された関数も含まれます：S

例：

>>> eval_prefix("+34")
7
>>> eval_prefix("*−567")
-7
>>> eval_prefix("-*33+2+11")
5
>>> eval_prefix("-+5*+1243")
14
>>> eval_prefix("*+35-72")
40
>>> eval_prefix("%3/52")
1

私のポイントを参照してくださいスペースなしD：

4

6 に答える 6

3

ここで重要なのは、「式のすべての数値は整数0〜9」だと思います。すべての数字は1桁です。1つの数字がどこで終わり、次の数字がどこから始まるかを見つけるためにスペースは必要ありません。lckknghtが言ったように、文字列インデックスから直接番号にアクセスできます。

文字列内の文字を計算用の整数に変換するには、ord（ch）-48を使用します（「0」のASCIIコードは48であるため）。したがって、入力の位置5に格納されている数値を取得するには、ord（input [5]）-48を使用します。

ネストされた式を評価するために、関数を再帰的に呼び出すことができます。ここでの重要な仮定は、演算子には常に正確に2つの演算子が存在するということです。

于 2012-11-14T22:56:13.410 に答える
3

OK、alexjordanのlanba/ reduceソリューションほど巧妙ではありませんが、ガベージ入力を妨げることはありません。これは、一種の再帰下降パーサーがバブルソートの忌まわしさを満たしているようなものです（最初に戻るよりも、解決可能な部分が見つかった方が少し効率的だと思います。;）

import operator
def eval_prefix(expr):
    d = {'+': operator.add,
         '-': operator.sub,
         '*': operator.mul,
         '/': operator.div, # for 3.x change this to operator.truediv
         '%': operator.mod}
    for n in range(10):
        d[str(n)] = n
    e = list(d.get(e, None) for e in expr)
    i = 0
    while i + 3 <= len(e):
        o, l, r = e[i:i+3]
        if type(o) == type(operator.add) and type(l) == type(r) == type(0):
            e[i:i+3] = [o(l, r)]
            i = 0
        else:
            i += 1
    if len(e) != 1:
        print 'Error in expression:', expr
        return 0
    else:
        return e[0]

def test(s, v):
    r = eval_prefix(s)
    print s, '==', v, r, r == v

test("+34", 7)
test("*-567", -7)
test("-*33+2+11", 5)
test("-+5*+1243", 14)
test("*+35-72", 40)
test("%3/52", 1)
test("****", 0)
test("-5bob", 10)
于 2012-11-14T23:14:45.833 に答える
2

「1つの機能」の制限は、思ったほど悪くはありません。Pythonでは、関数内で関数を定義できます。結局のところ、関数の定義は、関数を（通常は新しい）変数に割り当てることに他なりません。この場合、再帰を使用することをお勧めします。これは追加の関数なしでも実行できますが、追加の再帰関数を定義する方が簡単な場合があります。これはあなたの限界にとって問題ではありません：

def eval_prefix (data):
    def handle_operator (operator, rest):
        # You fill this in.
    # and this, too.

これで十分なヒントになるはずです（再帰的なアプローチを使用する場合）。

于 2012-11-14T21:25:53.187 に答える
2

さて、ワンライナーは収まりますか？python3でのReduceはfunctoolsに隠されています

eval_prefix = lambda inp:\
            reduce(lambda stack, symbol:\
            (
              (stack+[symbol]) if symbol.isdigit() \
             else \
              (
                stack[:-2]+\
                [str(
                      eval(
                           stack[-1]+symbol+stack[-2]
                          )
                    )
                ]
              )
            ), inp[::-1], [])[0]
于 2012-11-14T21:50:33.463 に答える
0

あなたが探している可能性が最も高いヒントは、「文字列は反復可能です」です。

def eval_prefix(data):
    # setup state machine
    for symbol_ in data:
        # update state machine
于 2012-11-14T21:20:44.060 に答える
0

文字列の要素を分離するのは簡単です。すべての要素は1文字の長さであるため、文字列を直接反復（またはインデックス付け）して、各要素を取得できます。または、値を操作できるようにする場合は、文字列をlistコンストラクターに渡すことができます。

これがどのように機能するかの例を次に示します。

string = "*-567"

# iterating over each character, one at a time:
for character in string:
    print(character) # prints one character from the string per line

# accessing a specific character by index:
third_char = string[2] # note indexing is zero-based, so 3rd char is at index 2

# transform string to list
list_of_characters = list(string) # will be ["*", "-", "5", "6", "7"]

方程式を解く方法については、2つのアプローチがあると思います。

1つは、関数を再帰的にして、各呼び出しが単一の操作またはリテラル値を評価するようにすることです。これは、1つの関数のみを使用することになっているため、少し注意が必要です（メインの非再帰関数とは異なるAPIで呼び出される再帰ヘルパー関数を使用できると、はるかに簡単になります）。

もう1つのアプローチは、入力文字列に対して1回の反復を行いながら、評価を待機している値と操作のスタックを構築することです。これは、1つの機能の制限を考えるとおそらく簡単です。

于 2012-11-14T21:29:15.407 に答える