使用遞歸解決用戶輸入表達式（計算器）

Question

作爲一個任務，我必須寫一個計算器，將接受並解決用戶的輸入，如：

3 + 7 * (!3)^2 

我必須解決本練習與遞歸。

def solve(exp): 
    #Recursion if statement 
    for op in exp: 
     if op == "*": 
      ... 
     elif op == "/": 
      ... 
     ... 
    return solve(exp) 

這是我如何認爲我的代碼看起來像，但我無法決定什麼是遞歸的停止條件。
此外，我不確定這種循環是否有用，因爲我將無法處理多個案例，例如-3 +5或處理括號的使用。

我認爲我的關於如何解決這個問題的基本想法並不好，我想獲得關於如何做到這一點的建議。

Answer 1

兩點意見：

1. 您當前的解決方案將不會返回任何有趣的，實際上它似乎循環無限，爲你傳遞給遞歸的下一階段exp不同於這是在傳遞不變原來，進一步沒有跡象表明任何一個循環通過遞歸實際上對最終解決方案都有影響。
2. 停止條件應該是一個空的表達式，也就是說，如果您將表達式存儲爲字符串，它應該是「」。

Answer 2

烏姆魯解析使用「標準」的語法的表達式（S），通過遞歸體面實際上是不可能的：

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所以我按照優先級從高到低的順序推導出下面的運算符。

這裏是一個簡單的，衆所周知的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（*）語法是有點機械的過程...

我通常穿上」不要給出任務代碼，特別簡單的代碼，但這只是爲了讓你開始，你應該能夠實現其餘部分。

因爲一般白色空間是被忽略的，所以我們將輸入量化爲一組適用於我們語法規則的值，排除任何空白，除非我們的語法規定它否則，這個過程被稱爲tokin化，每個值被引用作爲標記，而通常使用正則表達式這一點，我更喜歡手動方法的可讀性... 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)) 

注意：這還沒有被測試！