括号平衡算法不检测不平衡的括号

Question

代码接受括号的任意组合并检查它们是否平衡。如果它们是平衡的，它应该输出成功；如果它们不平衡，它应该输出括号不平衡的索引（从索引 1 开始）。示例：

Input: ())
Output: 3
\
Input: ()
Output: Success

无论平衡与否，代码总是显示“成功”。相反，我得到这个：

Input: ())
Output: Success

import sys

def Match(self, c):
    if self == '[' and c == ']':
       return True
    if self == '{' and c == '}':
       return True
    if self == '(' and c == ')':
       return True
    else:    
       return False

if __name__ == "__main__":
    text = sys.stdin.read()
    char_code = 0
    opening_brackets_stack = []
    for i, next in enumerate(text):
        if next == '(' or next == '[' or next == '{':
             char_code += 1
             opening_brackets_stack.append(next)
             stack_pop = opening_brackets_stack.pop()

        if next == ')' or next == ']' or next == '}':
             char_code += 1
             if not Match(stack_pop, next):
                 print(char_code)
        else:
            char_code += 1
    print ('Success')

Answer 1

您的代码正在打印 "Success" 因为您告诉它在完成后它应该总是打印成功

if __name__ == "__main__":
    # A bunch of stuff unrelated to program flow...
    print ('Success')

如果您已到达文本结尾且队列中没有任何内容，您可能只希望成功。

if __name__ == "__main__":
    text = sys.stdin.read()
    char_code = 0
    opening_brackets_stack = []
    for i, next in enumerate(text):
        if next == '(' or next == '[' or next == '{':
             char_code += 1
             opening_brackets_stack.append(next)
             stack_pop = opening_brackets_stack.pop()

        if next == ')' or next == ']' or next == '}':
             char_code += 1
             if not Match(stack_pop, next):
                 print(char_code)
        else:
            char_code += 1
    if not opening_brackets_stack:  # <-- new line
        print ('Success')

除非这也不能解决你的问题，因为你从来没有正确检查过你是否有一个不匹配的 closing 括号，只有一个不匹配的 opening括号。考虑一下：

# this will let us check for an expected closing bracket more easily
opening_brackets = "([{"
closing_brackets = ")]}"
mapping = dict(zip(opening_brackets, closing_brackets))

stack = []
for i, ch in enumerate(text):
    if ch in opening_brackets:
        # throw the closing bracket on the stack
        matching_closer = mapping[ch]
        stack.append(matching_closer)
    elif ch == stack[-1]:
        # if the character closes the last-opened bracket
        stack.pop()  # pop it off
    elif ch in closing_brackets:
        # this is an unmatched closing bracket, making the brackets
        # imbalanced in this expression
        print("FAILED")
        sys.exit(1)  # closes the program immediately with a retcode of 1
    else:
        # not a bracket, continue as normal
        # this is technically a NOP and everything from the `else` can be
        # omitted, but I think this looks more obvious to the reader.
        continue
if not stack:  # empty stack means matched brackets!
    print("SUCCESS")
else:
    print("FAILED")

Answer 2

代码可以包含集合 []{}() 中的任何括号，其中左括号为 [、{ 和 (，与它们对应的右括号为]、} 和 )。为方便起见，文本编辑器不仅要告知用户括号的使用有误，还要指出代码中括号有问题的确切位置。首要任务是找到第一个不匹配的右括号，它之前没有左括号，例如 ]() 中的 ]，或者关闭了错误的左括号，例如 } =21=]。如果没有这样的错误，那么它应该找到第一个不匹配的左括号，后面没有相应的右括号，如 {}([] 中的 (。如果没有错误，文本编辑器应该通知用户括号的使用是正确的。除了括号外，代码还可以包含大小写的拉丁字母、数字和标点符号。更正式地说，代码中的所有括号都应该分成一对匹配的括号，这样在每一对中，左括号在右括号之前，并且对于任何两对括号，其中一个嵌套在另一个括号内，如 (foo[bar]) 或者它们是分开的，如 f(a,b)-g[c]。括号[对应括号]，{对应}，(对应).

# python3
from collections import namedtuple

Bracket = namedtuple("Bracket", ["char", "position"])

def are_matching(left, right):
    return (left + right) in ["()", "[]", "{}"]

def find_mismatch(text):
    opening_brackets_stack = []
    mismatch_pos = None
    for i, next in enumerate(text):
        if next in "([{":
            # Process opening bracket, write your code here
            opening_brackets_stack.append(next)
            if len(opening_brackets_stack) < 2:
                mismatch_pos = Bracket(next, i + 1).position

        if next in ")]}":
            # Process closing bracket, write your code here
            if len(opening_brackets_stack) == 0:
                return Bracket(next, i + 1).position
            
            top = opening_brackets_stack.pop()
            
            if not are_matching(top, next):
                return Bracket(next, i + 1).position
            
    if len(opening_brackets_stack) == 0:
        return "Success"
    return mismatch_pos
        
def main():
    text = input()
    mismatch = find_mismatch(text)
    # Printing answer, write your code here
    print(mismatch)

if __name__ == "__main__":
    main()

括号平衡算法不检测不平衡的括号

Bracket balancing algorithm doesn't detect imbalanced brackets

python

brackets