检查支架算法

Question

在研究数据结构时，我自己正在制作检查括号算法。 我编写了如下所示的Python代码，但是使用'），'}'，']'，总是出现'no'作为输出... 如何修复代码？

• 条件1）左右支架的数量必须相同。
• 条件2）左支架必须先于右支架。
• 条件3）仅在括号之间存在包含关系。

stack

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

main

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)

input

(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）所有括号匹配 - 即，每种类型的左/右支架的相等数量和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

如果字符串包含一个模式，观察到右支架，并且列表中的先前条目不是相应的左支架，则会提高值。

如果字符串包含一个右托架并且列表为空，则将提高索引