使用递归来解决用户输入的表达式（计算器）

Question

作为作业，我必须编写一个计算器来接受和解决用户输入，例如：

3 + 7 * (!3)^2

我必须用递归来解决这个问题。在

^{pr2}$

我假设我的代码是这样的，但是我无法决定递归的停止条件是什么。
另外，我不确定这种循环是否有用，因为我无法处理诸如-3 +5等几种情况，也无法处理括号的使用。在

我认为我关于如何解决这个问题的基本想法并不好，我想得到一些关于如何解决这个问题的建议。在

Answer 1

umm使用“标准”语法通过递归decept解析表达式实际上是不可能的：

E = E + E | E - E | ... | VALUE

这是因为调用E可能会产生无限递归，还有其他问题，如运算符优先级以及关联性。。。在

处理这类问题有两种众所周知的方法，实际上这两种方法适用于大多数问题。在

1）使用自底向上的方法，一个例子是shift-reduce解析http://en.wikipedia.org/wiki/Shift-reduce_parser这种方法以牺牲代码复杂性为代价来保持语法。在

{2）一个不使用递归的直接方法来更新一个递归的语法，但是一个很好的例子是用一个递归的方法来完成的。这会修改语法（如果可能的话），使其更长，但代码更简单。在

既然您要求方法是递归的，那么第二种方法可能是更好的方法。在

我们首先要定义这个新语法，然后为每个规则创建一个新函数。在

您给出了这个示例：3 + 7 * (!3)^2所以我按照优先级降序推导了以下运算符。在

^{pr2}$

这里有一个简单的，众所周知的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，每个值都被称为tokenization，而通常使用regexp来实现这一点，我更喜欢用手动方式来提高可读性。。。很简单的托日化。。。在

"""
`{}` 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))

注意：这还没有经过测试！

Answer 2

两点意见：

1. 您当前的解决方案不会返回任何有趣的内容，事实上它似乎是无限循环的，因为您传递到下一个递归阶段的exp与最初传入的相同，而且没有迹象表明通过递归的任何一个循环实际上对最终解决方案有任何影响。在
2. 停止条件应该是一个空表达式，也就是说，如果将表达式存储为字符串，它应该是“”。在