马上蝙蝠 - 不，这不是功课。
我想在python中编写前缀表示法解析器（目前用于总和）...例如
如果给出：+ 2 2它将返回：4
想法？
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，还包括一个乘法运算符，以显示如何扩展它。
可以非常容易地递归地评估前缀表示法。你基本上看到了第一个标记，如果是'+'，你可以评估后面的子表达式来获取要添加的值，然后将它们添加起来。如果是数字，则只返回数字。
以下代码假定输入格式正确并且是有效表达式。
#! /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()))
这是我的工作。它保留了一堆运营商。当它接收到足够的数字时，它会弹出一个运算符并计算子表达式。
# 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的递归功能。
反转令牌并使用如下堆栈计算机：
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习语：
stack = []：Python中没有内置的堆栈对象，但为了相同的目的，列表很容易被征集。stack[-1]和stack[-2]：Python支持负面指数。 stack[-2]指的是列表的倒数第二个元素。stack[-2:] = ...：除负面索引外，此作业还包含两个习语：
切片：A[x:y]指从A到x的y的所有元素，包括x但不包括y（例如，A [3：5]指的是元素3和4）。省略的数字表示列表的开头或结尾。因此，stack[-2:]指的是从列表的倒数第二个到结尾的每个元素，即最后两个元素。
切片赋值：Python允许您分配切片，切片具有拼接新列表以代替切片引用的元素的效果。将所有内容放在一起，stack[-2:] = [stack[-1] + stack[-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
这是lambda函数的示例
ops = {
"+": (lambda a, b: a + b),
"-": (lambda a, b: a - b),
"*": (lambda a, b: a * b),
"/": (lambda a, b: a / b)
}
def eval(expression):
tokens = expression.split()
stack = []
for token in tokens:
if token in ops:
arg2 = stack.pop()
arg1 = stack.pop()
result = ops[token](arg1, arg2)
stack.append(result)
else:
stack.append(int(token))
return stack.pop()
正则表达式：
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...
基于其他答案，但逻辑较少。
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]
这是另一种方法。我在a，b和c上添加了一个“@”切换器，如果a为正则返回b，如果a为负则返回c。我知道它有点冗长而且效率低下但是我希望它能够适用于所有操作。
def operatorhelper(index, answer):
del currentsplitline[index + 2]
del currentsplitline[index + 1]
del currentsplitline[index]
currentsplitline.insert(index, answer)
infilelines = ["+ 2 3", " - 3 2", "* 2 3", "@ 1 3 4"]
for line in infilelines:
currentsplitline = line.split(" ")
for i in range(len(currentsplitline)):
try:
currentsplitline[i] = int(currentsplitline[i])
except:
continue
operatorindexes = [int(i) for i,x in enumerate(currentsplitline) if not type(x) == int]
operatorindexes = operatorindexes[::-1]
for index in operatorindexes:
answer = 0
if(isinstance(currentsplitline[index + 1], int) and isinstance(currentsplitline[index + 2], int)):
operator = currentsplitline[index]
nextnum = currentsplitline[index + 1]
secondnum = currentsplitline[index + 2]
if(operator == "+"):
answer = nextnum + secondnum
operatorhelper(index, answer)
elif(operator == "-"):
answer = nextnum - secondnum
operatorhelper(index, answer)
elif(operator == "*"):
answer = nextnum * secondnum
operatorhelper(index, answer)
elif(operator == "@"):
if(isinstance(currentsplitline[index + 3], int)):
thirdnum = currentsplitline[index + 3]
del currentsplitline[index + 3]
if(nextnum >= 0):
answer = secondnum
else:
answer = thirdnum
operatorhelper(index, answer)
print(currentsplitline[0])