检验括号算法

Question

在研究数据结构的同时，我自己也在做括号算法的检查。我编写了python代码，如下所示，但是如果使用“)”、“}”、“]”，则总是输出“No”.我怎样才能修正密码？

条件1)左括号和右括号的数目必须是same.

• Condition 2)左括号必须位于右bracket.

• Condition3)之前，只有括号之间存在包含关系。

堆栈

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)

输入

(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)所有括号都匹配--即，每种类型的左/右括号数目相等；如果没有对应的左括号，则不存在右括号(任何类型)。

因此：

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

如果字符串包含一个观察右括号的模式，而列表中的前一个条目不是对应的左括号，那么将引发一个ValueError异常。

如果字符串包含右括号且列表为空，则将引发IndexError。