作为一项任务，我必须编写一个计算器来接受并解决用户输入，例如：
3 + 7 * (!3)^2
我必须用递归来解决这个练习。
def solve(exp):
#Recursion if statement
for op in exp:
if op == "*":
...
elif op == "/":
...
...
return solve(exp)
这就是我假设我的代码的样子，但我无法确定递归的停止条件是什么。
另外，我不确定这种循环是否有用，因为我将无法处理几种情况，例如-3 +5, 或处理括号的使用。
我认为我关于如何解决它的基本想法并不好，我想获得有关如何做到这一点的建议。
嗯，使用“标准”语法解析表达式，通过递归体面几乎是不可能的：
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(*) 语法的过程有点机械......
我通常不会给出任务代码，特别是简单的代码，但这只是为了让你开始，你应该能够实现其余的。
因为空白通常是被忽略的，所以我们将输入量化为一组适用于我们语法的每个规则的值，排除任何空白，除非我们的语法另有规定，这个过程称为分词化，每个值称为令牌，而为此使用正则表达式很常见，我更喜欢手动方法以提高可读性...... 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))
注意：这还没有经过测试！
两条评论：
exp您传递到递归的下一阶段与最初传递的内容没有变化，进一步没有迹象表明任何一个循环通过递归实际上对最终解决方案有任何影响。