1

割り当てとして、次のようなユーザー入力を受け入れて解決する計算機を作成する必要があります。

3 + 7 * (!3)^2

この演習問題を再帰で解決する必要があります。

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

これが私のコードがどのように見えるかを想定している方法ですが、再帰の停止条件が何であるかを判断できません。
また、この種のループが役立つかどうかもわかりません-3 +5。

それを解決する方法に関する私の基本的な考えは良くないと思います。これを行う方法について提案を求めたいと思います。

4

2 に答える 2

3

うーん、「標準」文法を使用して式を解析することは、再帰的な適切な方法では事実上不可能です。

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

これは、呼び出しEによって無限再帰が発生する可能性があるためです。演算子の優先順位や結合性などの問題が他にもあります...

このような問題に対処する方法として 2 つの方法がよく知られていますが、実際には、この 2 つの方法はほとんどの問題に適用できます。

1) ボトムアップ アプローチを使用します。1 つの例は、Shift-Reduce 解析http://en.wikipedia.org/wiki/Shift-reduce_parserです。この方法は、コードの複雑さを犠牲にして文法を保持します。

2) トップダウン アプローチを使用します。1 つの例は再帰的適切ですが、別の文法を使用します。http://en.wikipedia.org/wiki/LL_parser左再帰のないものです。これは通常、元の文法を変更してすべてを更新することによって行われます。直接左の再帰呼び出しを削除するルール。これにより、文法が (可能であれば) 変更され、かなり長くなりますが、コードはより単純になります。

メソッドを再帰的にするように要求したので、おそらく2番目の方法がより良いアプローチです。

最初にこの新しい文法を定義し、ルールごとに新しい関数を作成する必要があります。

あなたはこの例を挙げました： 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(*) 文法に変換するプロセスはいくぶん機械的です ...

私は通常、割り当て、特に単純なもののコードを提供しませんが、これは開始するためのものであり、残りは実装できるはずです。

一般に空白は無視されるため、入力を文法の各ルールに適用可能な一連の値に量子化しました。文法で別段の指示がない限り、空白は除外されます。このプロセスはトーキナイゼーションと呼ばれ、各値はトークンと呼ばれます。これにはregexpを使用するのが一般的ですが、読みやすさのために手動のアプローチを好みました... 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))

注: これはテストされていません。

于 2012-12-02T06:11:25.753 に答える
0

2 つのコメント:

  1. 現在のソリューションは興味深いものを返しません。実際exp、再帰の次の段階に渡すと最初に渡されたものから変更されていないため、無限に循環しているように見えます。実際には、最終的なソリューションに何らかの影響を与えます。
  2. 停止条件は空の式である必要があります。つまり、式を文字列として格納する場合は "" にする必要があります。
于 2012-12-02T01:55:30.880 に答える