1

すぐに - いいえ、これは宿題ではありません。

Pythonでプレフィックス表記パーサーを書きたいと思います（現在の合計用）...たとえば

与えられた場合:+ 2 2それは以下を返します:4

アイデア？

4

8 に答える 8

23

プレフィックス表記は、再帰的に非常に簡単に評価できます。基本的に最初のトークンが表示され、それが「+」の場合は、後続の部分式を評価して、追加する値を取得し、それらを合計します。数値の場合は、数値を返すだけです。

次のコードは、入力が適切にフォーマットされており、有効な式であることを前提としています。

#! /usr/bin/env python
from collections import deque
def parse(tokens):
    token=tokens.popleft()
    if token=='+':
            return parse(tokens)+parse(tokens)
    elif token=='-':
            return parse(tokens)-parse(tokens)
    elif token=='*':
            return parse(tokens)*parse(tokens)
    elif token=='/':
            return parse(tokens)/parse(tokens)
    else:
            # must be just a number
            return int(token)


if __name__=='__main__':
        expression="+ 2 2"
        print parse(deque(expression.split()))
于 2011-03-15T04:32:02.643 に答える
6

これが私が取り組んだものです。オペレーターのスタックを保持します。十分な数値を受け取ると、演算子をポップして部分式を評価します。

# Bring in the system module to get command line parameters
import sys

# This function takes in some binary operator, which is just an arbitrary
#  string, and two values.  It looks up the method associated with the
#  operator, passes the two values into that method, and returns the
#  method's result.
def eval_expression(operator, value_one, value_two):
  if operator == "+":
    return value_one + value_two
  elif operator == "-":
    return value_one - value_two
  elif operator == "*":
    return value_one * value_two
  elif operator == "/":
    return value_one / value_two
  # Add new operators here.  For example a modulus operator could be
  #  created as follows:
  #       elif operator == "mod":
  #         return value_one % value_two
  else:
    raise Exception(operator, "Unknown operator")

# This function takes in a string representing a prefix equation to
#  evaluate and returns the result.  The equation's values and
#  operators are space delimited.
def calculate( equation ):
  # Gather the equation tokens
  tokens = equation.split( " " )

  # Initialize the evaluation stack.  This will contain the operators
  #  with index 0 always containing the next operator to utilize.  As
  #  values become available an operator will be removed and
  #  eval_expression called to calculate the result.
  eval_stack = [ ]
  total = None

  # Process all the equation tokens
  for token in tokens:
    if token.isdigit():
      # Save the first value.  Subsequent values trigger the evaluation
      #  of the next operator applied to the total and next values
      token = int(token)
      if total is None:
        total = token
      else:
        total = eval_expression(eval_stack.pop(0), total, token)

    else:
      # Save the new operator to the evaluation stack
      eval_stack.insert(0, token)

  # Done!  Provide the equation's value
  return total

# If running standalone pass the first command line parameter as
#  an expression and print the result.  Example:
#       python prefix.py "+ / 6 2 3 - 6"
if __name__ == '__main__':
  print calculate( sys.argv[1] )

MAK の再帰関数も気に入っています。

于 2011-03-15T04:46:59.250 に答える
4

トークンを逆にして、次のようなスタック マシンを使用します。

def prefix_eval(tokens):
    stack = []
    for t in reversed(tokens):
        if   t == '+': stack[-2:] = [stack[-1] + stack[-2]]
        elif t == '-': stack[-2:] = [stack[-1] - stack[-2]]
        elif t == '*': stack[-2:] = [stack[-1] * stack[-2]]
        elif t == '/': stack[-2:] = [stack[-1] / stack[-2]]
        else: stack.append(t)
    assert len(stack) == 1, 'Malformed expression'
    return stack[0]

>>> prefix_eval(['+', 2, 2])
4
>>> prefix_eval(['-', '*', 3, 7, '/', 20, 4])
16

通常のスタック マシンとはstack[-1]とが逆になっていることに注意してください。stack[-2]これは、実際には逆の接頭表記であるという事実に対応するためです。

私が使用したいくつかの Python イディオムを説明する必要があります。

  1. stack = []: Python には組み込みのスタック オブジェクトはありませんが、リストは同じ目的で簡単に作成できます。
  2. stack[-1]and stack[-2]: Python は負のインデックスをサポートしています。stack[-2]リストの最後から 2 番目の要素を参照します。
  3. stack[-2:] = ...: この割り当ては、負の索引付けに加えて 2 つの慣用句を組み合わせたものです。
    1. スライス:を含むが除くA[x:y]すべての要素を参照しますA(たとえば、A[3:5] は要素 3 と 4 を参照します)。省略された番号は、リストの開始または終了を意味します。したがって、リストの最後から 2 番目の要素から最後までのすべての要素、つまり最後の 2 つの要素を参照します。xyxystack[-2:]
    2. スライスの割り当て: Python では、スライスに割り当てることができます。これにより、スライスが参照する要素の代わりに新しいリストを接合する効果があります。

すべてをまとめるとstack[-2:] = [stack[-1] + stack[-2]]、スタックの最後の 2 つの要素が加算され、合計から単一要素のリストが作成され、このリストが 2 つの数値で構成されるスライスに割り当てられます。最終的な効果は、スタックの一番上の 2 つの数値をそれらの合計に置き換えることです。

文字列から始めたい場合は、単純なフロントエンド パーサーがそのトリックを実行します。

def string_eval(expr):
    import re
    return prefix_eval([t if t in '+-*/' else int(t)
                        for t in re.split(r'\s+', expr)])

>>> string_eval('/ 15 - 6 3')
5
于 2011-03-15T04:57:47.167 に答える
1

そのような正規表現：

import re
prefix_re = re.compile(r"(+|-|*|/)\s+(\d+)\s+(\d+)")
for line in get_lines_to_parse():
    match = prefix_re.match(line)
    if match:
        operand = match.group(1)
    if operand == '+':
        return int(match.group(2))+int(match.group(3))
    elif operand == '-':
        return int(match.group(2))-int(match.group(3))
#etc...
于 2011-03-15T03:50:09.960 に答える
0

他の回答に基づいていますが、ロジックは少ないです。 

import operator

def eval_prefix(tokens):
    operators = {'+': operator.add, '-': operator.sub, '/': operator.truediv, 
                 '*': operator.mul, '%': operator.mod}

    stack = []
    for i in reversed(tokens):
        if i in operators:
            stack[-2] = operators[i](int(stack[-1]), int(stack[-2]))
            del stack[-1]
        else:
            stack.append(i)
    return stack[0]
于 2014-05-23T05:20:03.243 に答える
-1 
def prefix(input):
  op, num1, num2 = input.split(" ")
  num1 = int(num1)
  num2 = int(num2)
  if op == "+":
    return num1 + num2
  elif op == "*":
    return num1 * num2
  else:
    # handle invalid op
    return 0

print prefix("+ 2 2")

プリント4には、それを展開する方法を示すためだけに乗算演算子も含まれています。

于 2011-03-15T03:42:34.460 に答える