使用堆栈检查 Python 中用户输入的不平衡括号

Question

我需要使用堆栈来检查用户输入中是否有任何不平衡的括号。代码的逻辑应该是使用stack push 方法向栈中添加一个左括号，并在遇到右括号时将其弹出。当左括号和右括号不平衡时，代码应该中断并打印 parenthesis unbalanced。我试图用这段代码作弊，但最后一个测试用例让我失败了

mytext="))((("#this string input is just sample, the real input is captured from user
if(mytext.count(")")!=mytext.count("(")):
    print("The paranthesis are not balanced")
else:
    print("The parenthesis are balanced")

所以决定用它的方法来构建一个堆栈 class bracket ")" 然后调用 pop 从堆栈中删除左括号。我觉得对于输出平衡括号的代码，堆栈应该是空的，对于输出不平衡括号，堆栈应该是空的。代码如下

##First you need to create a stack class
class Stack:
    def __init__(self):
        self.items=[]
    def is_empty(self):
        return self.items==[]
    def push(self,item):
        self.items.insert(0,item)
    def pop(self):
        self.items.pop()#removes last element added
    def print_stack(self):#print function for debugging
        print(self.items)







def balanced(expression):#This function checks whether input from user has balanced parenthesis
    #create a stack object
     mystack=Stack()
    #scan user input for opening bracket and add to stack
    #I need help from this point onwards
    if "(" in expression:#if opening bracket exists in input, i feel like i should iterate through the expression
       mystack.push(0,"(")
    if ")" in expression:#remove the previously added opening bracket
       mystack.pop(0):
     ##implement empty_check and return accordingly
        
print(balanced(input()))

我也觉得我应该只使用列表从字符串中扫描 "(" 将它们添加到列表中，扫描相反的语法 ")" 并对它们的长度进行一些比较。

Answer 1

mytext="))((("#this string input is just sample, the real input is captured from user
if(mytext.count(")")!=mytext.count("(")):
    print("The paranthesis are not balanced")
else:
    print("The parenthesis are balanced")

它失败的原因之一是，它没有检查 - ) 不应该在 ( 之前出现。

您可以使用的一种简单方法是，创建一个初始值为 0 的计数器变量。现在遍历用户字符串并在每个 ( 上执行 counter++ & 在每个 ) 做 counter--.

如果在任何迭代中中断 counter < 0。

现外循环，ifcounter==0有效else无效

示例代码：

mytext="((()()))"

ctr = 0
for c in mytext:
    if c == ')':
        ctr -= 1
    elif c == '(':
        ctr += 1
    print("c={}, ctr={}".format(c,ctr))
    if ctr < 0:
        break
if ctr == 0:
    print("Valid")
else:
    print("Not valid")

Answer 2

您可以试试下面的代码

def check_paranthesis(data):
    stack = []
    pairs = {
        '}': '{',
        ']': '[',
        ')': '('
    }
    for i in data:
        if i in ('(', '[', '{'):
            stack.append(i)
        elif not stack or pairs[i] != stack.pop():
            return False
    
if stack:
        return False
return True


print(check_paranthesis('[()]'))    # True
print(check_paranthesis('[({})]')) # True
print(check_paranthesis('[(})}]'))  # False
print(check_paranthesis('[(])'))  # False
print(check_paranthesis('[()'))  # False
print(check_paranthesis('[(]'))  # False
print(check_paranthesis(']['))  # False
print(check_paranthesis('[['))  # False

想法很简单，继续将左边的对应物推入堆栈，一旦在表达式中遇到右边的对应物，弹出堆栈，看看它是否是对应的右边对应物 bracket/curly/parentheses .

最后如果你的堆栈是空的，说明你的表达是平衡的。

使用堆栈检查 Python 中用户输入的不平衡括号

Use stack to check for any unbalanced paranthesis on user input in Python

python

parentheses