作为一项作业，我必须编写一个计算器来接受并解决用户输入，例如:
3 + 7 * (!3)^2
我必须用递归解决这个练习。
def solve(exp):
#Recursion if statement
for op in exp:
if op == "*":
...
elif op == "/":
...
...
return solve(exp)
这就是我假设我的代码的样子，但我无法决定递归的停止条件是什么。
另外，我不确定这种循环是否有用，因为我无法处理多种情况，例如 -3 +5 或处理括号的使用。
我认为我关于如何解决这个问题的基本想法不好，我想获得有关如何做到这一点的建议。
最佳答案
umm 使用“标准”语法通过递归体例解析表达式实际上是不可能的:
E = E + E | E - E | ... | VALUE
这是因为调用 E 可能会产生无限递归，还有其他问题，例如运算符优先级以及关联性......
有两种众所周知的方法来处理此类问题，实际上这两种方法适用于大多数问题。
1)使用自下而上的方法，一个例子是shift-reduce解析http://en.wikipedia.org/wiki/Shift-reduce_parser此方法以牺牲代码复杂性为代价来保留语法。
2)使用自上而下的方法，一个例子是递归的，但具有不同的语法，http://en.wikipedia.org/wiki/LL_parser一种没有左递归的方法，这通常是通过修改原始语法并更新所有规则来删除任何直接左递归调用来完成的。这会修改语法(如果可能的话)，使其变得更长，但代码更简单。
由于您要求该方法是递归的，也许第二种方法是更好的方法。
我们首先必须定义这个新语法，并为每个规则创建一个新函数。
您给出了这个示例:3 + 7 * (!3)^2，因此我按照优先级降序推导了以下运算符。
operators: +, -, *, /, ^, -, !
values: 0,1,2,3 ...
这是一个简单、众所周知的 LL(1) 语法，它具有优先级......
<arith_expr> : <term> {+ <term>}
| <term> {- <term>}
<term> : <power> {* <power>}
| <power> {/ <power>}
<power> : <factor> <exponent>
<exponent> : ^ <factor> <exponent> | ''
<factor> | NUMERIC_VALUE
| - <factor>
| ! <factor>
| ( <arith_expr> )
它与之前的语法有些等价，但没有直接的左递归调用，将语法转换为 LL(*) 语法的过程有点机械......
我通常不会给出作业代码，特别是简单的代码，但这只是为了让您开始，您应该能够实现其余的。
因为空白通常被忽略，所以我们将输入量化为一组适用于我们语法的每个规则的值，排除任何空白，除非我们的语法另有规定，这个过程称为分词化，每个值被称为token，虽然通常使用正则表达式来实现此目的，但为了可读性，我更喜欢手动方法...tokinization 非常简单...
"""
`{}` means 0 or more
<arith_expr> : <term> {+ <term>}
| <term> {- <term>}
<term> : <factor> {* <factor>}
<factor> | NUMERIC_VALUE
| - <factor>
| ( <arith_expr> )
"""
import string
def evaluate(str_value):
def tokenize(value):
all_symbols = set(('+', '-', '*',)) | set(('(', ')'))
white_space = set((' ', '\n', '\t'))
tokens = []
index = 0
while index < len(value):
current_char = value[index]
if current_char in white_space:
index += 1
continue
if current_char in all_symbols:
tokens.append(current_char)
index += 1
continue
if (current_char in string.digits) or (current_char == '.'):
numeric_value = current_char
index += 1
while (index < len(value)) and ((value[index] in string.digits) or (value[index] == '.')):
if (values[index] == '.') and ('.' in numeric_value):
raise Exception('Multiple decimal points detected while tokenizing numeric value!')
numeric_value.append(value[index])
index += 1
tokens.append(float(numeric_value) if '.' in numeric_value else int(numeric_value))
continue
raise Exception('Unable to tokenize symbol %s' % value[index])
return tokens
def factor(tokens):
'''
<factor> | NUMERIC_VALUE
| - <factor>
| ( <arith_expr> )
'''
if not tokens:
return None
if type(tokens[0]) in set((int, float)): # NUMERIC_VALUE
return tokens.pop(0)
if tokens[0] == '-': # - <factor>
tokens.pop(0)
return -1 * factor(tokens)
if tokens[0] == '(': # ( <arith_expr> )
tokens.pop(0)
value = arith_expr(tokens)
assert tokens.pop(0) == ')'
return value
def term(tokens):
'''
<term> : <factor> {* <factor>}
'''
left_value = factor(tokens)
operators = set(('*',))
while tokens and (tokens[0] in operators): # {* <factor>}
op = tokens.pop(0)
right_value = factor(tokens)
left_value *= right_value
return left_value
def arith_expr(tokens):
'''
<arith_expr> : <term> {+ <term>}
| <term> {- <term>}
'''
left_value = term(tokens)
operators = set(('+', '-'))
while tokens and (tokens[0] in operators):
op = tokens.pop(0)
right_value = term(tokens)
if op == '+':
left_value += right_value
else:
left_value -= right_value
return left_value
return arith_expr(tokenize(str_value))
注意:这尚未经过测试!
关于python - 使用递归来解决用户输入的表达式(计算器)，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/13665640/