马上 - 不，这不是家庭作业。
我想在python中编写一个前缀符号解析器（目前用于总和）......例如
如果给出：+ 2 2它将返回：4
想法？
问问题
18505 次
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 习语：
stack = []: Python 中没有内置的堆栈对象，但列表很容易被征召用于相同的目的。stack[-1]和stack[-2]: Python 支持负索引。stack[-2]指列表的倒数第二个元素。stack[-2:] = ...：除了负索引之外，此作业还结合了两个习语：- 切片：
A[x:y]指Afromx到的所有元素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
于 2011-03-15T04:57:47.167 回答
3
这是 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()
于 2019-01-26T14:46:57.710 回答
1
ish 的正则表达式：
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 回答
-1
这是另一种方法。我在 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])
于 2019-04-05T15:33:18.153 回答