检查括号算法

Question

一边学习数据结构，一边自己做检查括号算法。我编写了如下所示的 python 代码，但是如果使用 ')'、'}'、']'，输出总是 'No'... 我该如何修复代码？

条件1）左右括号的个数必须相同
条件 2) 左括号必须在右括号之前。
条件3)括号之间只存在包含关系

堆栈

class Stack:
    def __init__(self):
        self.top = []

    def isEmpty(self): 
        return len(self.top) == 0

    def size(self):
        return len(self.top)

    def clear(self):
        self.top = []

    def push(self, item):
        self.top.append(item)

    def pop(self):
        if not self.isEmpty():
            return self.top.pop()

    def peek(self):
        if not self.isEmpty():
            return self.top[-1]

检查括号功能

def check(statement):
    stack = Stack()
    msg = ""

    for ch in statement:
        if ch in ('{', '[', '('):
            stack.push(ch)
            msg = "Yes"
            return msg, stack
        elif ch in ('}', ']', ')'):
            if stack.isEmpty():     # Condition 2
                msg = "No"
                return msg, stack
            else:
                left = stack.pop(-1)
                if (ch == "}" and left != "{") or \
                        (ch == "]" and left != "[") or \
                        (ch == ")" and left != "(") :   # Condition 3
                        msg = "No"
                        return msg, stack
                else:
                    msg = "Yes"
                    return msg, stack
    
    if (stack.isEmpty() == 0):  # Condition 1
        msg = "No"
        return msg, stack

    msg = "Yes"
    return msg, stack

主要

text = input()
count = 0
result = "Yes"
messages = []

for t in text:
    message = check(t)[0]
    if (t in ['(',')','{','}','[',']']):
        messages.append(message)

for message in messages:
    count += 1
    if message == "No":
        result = "No"
    
print(result + '_' + str(count))
print(messages)

输入

(2*{137+(8-2)/2} + [9*{14-5* (8-1)}])

输出

No_12
['Yes', 'Yes', 'Yes', 'No', 'No', 'Yes', 'Yes', 'Yes', 'No', 'No', 'No', 'No']

预期输出

Yes_12
['Yes', 'Yes', 'Yes', 'Yes', 'Yes', 'Yes', 'Yes', 'Yes', 'Yes', 'Yes', 'Yes', 'Yes']

Answer 1

我认为你把它弄得比实际情况更复杂。最终你只需要知道两件事。 1) 所有括号匹配 - 即每种类型的 left/right 括号数量相等 2) 当没有相应的（前面的）左括号时，没有右括号（任何类型）。

因此：

class Brackets:
    left = '([{'
    right = ')]}'
    def __init__(self):
        self.brackets = []
    def isvalid(self):
        return len(self.brackets) == 0
    def add(self, b):
        if b in Brackets.left:
            self.brackets.append(b)
        else:
            if b in Brackets.right:
                i = Brackets.right.index(b)
                if self.brackets[-1] != Brackets.left[i]:
                    raise ValueError 
                self.brackets.pop(-1)


brackets = Brackets()

input_ = '(2*{137+(8-2)/2} + [9*{14-5* (8-1)}])'

for c in input_:
    brackets.add(c)

print(brackets.isvalid())

这个输出将是

True

如果字符串包含一个模式，由此观察到 right-bracket 而列表中的前一个条目不是相应的 left-bracket，那么将引发 ValueError 异常。

如果字符串包含 right-bracket 并且列表为空，则会引发 IndexError

检查括号算法

Checking Brackets Algorithm

python

stack