スタックなしのバランス括弧チェッカーの問題

debugcn 投稿 Dev

神のスーレマン

Pythonを学んだ後、スタックなしで括弧チェッカーの問題を解決しようとしています。私のコードは多くの式で機能しますが、それらの多くでも失敗します。特に同じタイプのブラケットが同時に表示される場合。

exp = "([[]])"
#input("Enter the expression to evaluate: ")

def sumer(l):
    x=0
    for i in range(len(l)):
      x+=l[i]
    return x  

exp_num = list([])

for i in range(len(exp)):
   if exp[i]=="(":
        exp_num.append(1)
   if exp[i]==")":
        exp_num.append(-1)
   if exp[i]=="[":
        exp_num.append(2)
   if exp[i]=="]":
        exp_num.append(-2)
   if exp[i]=="{":
        exp_num.append(3)
   if exp[i]=="}":
        exp_num.append(-3)
del exp
for g, i in enumerate(exp_num):
    if i>0:
        try:
            op = exp_num.index(-i)
            sm = sumer(exp_num[g+1:op])
            if sm == 0:
                for x in range(g,op+1):
                    exp_num[x]= 0
        except ValueError:
            break
    else:
        continue      
if exp_num.count(0) == len(exp_num):
    print("The entered expression is valid !!")
else:
    print("The entered expression is not valid !!")

上記の文字列では機能しますが、失敗します ([[()]])

これまでのところ、私がやっていることは次のとおりです。

ステップ1：さまざまな種類のブレースに、開く場合は正、閉じる場合は負の番号を付けます。たとえば、 '（' = 1 and '）' = -1です。最後に、入力式を同じ順序の数値のリストに変換します。

ステップ2：リストのスキャンを開始し、正の数（開き角かっこ）が見つかった場合は、対応する負の数（閉じかっこ）を見つけます。これら2つの間の数の合計を見つけます。

ステップ3：合計が0の場合は、リスト内のすべての処理済みアイテムを0に置き換えて、繰り返し続けます。

最終的に、リストのすべての項目がゼロになる場合、式は有効です。それ以外の場合、式は無効です。

Jaideep Shekhar

Pythonを学んだ後、スタックなしで括弧チェッカーの問題を解決しようとしています。

仮に...

リストをスタックとして扱うことができます。

初期化exprしてdelimiters：

expr = '[{[{<>}]}]'
delimiters = list()

そしてdelimitersスタックとして使用します：

# For each character in expression
for character in expr:
    # If it is an opening one
    if character in opening:
        # Add it's unique value to delimiters
        delimiters.append( opening.index(character) )
    # If it is a closing one
    if character in closing:
        # If there are opening delimiters and character matches the last opened one
        if delimiters and delimiters[-1] == closing.index(character):
            # It was valid, remove the opening delimiter
            del delimiters[-1]
        # Else, expression is invalid!
        else:
            break

ここでopening、closingは一致するペアです。

opening = '[({<'
closing = '])}>'

最後に、リスト（以前はスタックと呼ばれていました）が空の場合、式は有効でした。

print('Success!') if not delimiters else print('Invalid Expression!')
# same as:
# print('Success!') if delimiters == [] else print('Invalid Expression!')

この記事はインターネットから収集されたものであり、転載の際にはソースを示してください。

侵害の場合は、連絡してください[email protected]