Python中的前缀表达式解析

Question

一开始就说，这不是作业。

我想用Python写一个前缀表示法的解析器（目前是用来计算加法）……比如说，

如果输入是：+ 2 2，那么它应该返回：4

有没有什么想法？

Answer 1

这是我做的一个方案。它会保存一个操作符的栈。当接收到足够的数字时，它会弹出一个操作符，并计算出一个子表达式的结果。

# 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的递归函数。

Answer 2

前缀表示法可以很简单地通过递归来计算。你基本上是先看第一个符号，如果它是一个'+'，那么就计算后面的子表达式，得到要相加的值，然后把它们加起来。如果第一个符号是一个数字，那就直接返回这个数字。

下面的代码假设输入格式良好，并且是一个有效的表达式。

#! /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()))

Answer 3

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，这里还加了一个乘法运算符，主要是为了演示怎么扩展这个表达式。

Python中的前缀表达式解析

8 个回答

撰写回答