Python实现括号匹配算法：使用栈解决括号匹配问题

在处理字符串和表达式时，括号匹配是一个常见且重要的问题。本文将介绍如何使用Python实现括号匹配算法，并提供详细的代码示例。

1. 问题描述

给定一个包含左括号'(', 右括号')'和其他字符的字符串，判断字符串中的括号是否匹配。例如：

'((a+b)*c)' 匹配- '((a+b)' 不匹配- ')(a+b)' 不匹配

2. 解决方案：栈

解决括号匹配问题的有效方法是使用栈。栈是一种后进先出（LIFO）的数据结构，其操作原理非常适合处理括号的嵌套关系。

算法步骤：

创建一个空栈。2. 从左到右遍历字符串。 - 如果遇到左括号'('，则将其压入栈中。 - 如果遇到右括号')'，则： - 如果栈为空，则表示右括号没有匹配的左括号，不匹配。 - 如果栈不为空，则将栈顶元素弹出，表示匹配了一个左括号。 - 其他字符忽略。3. 遍历结束后，如果栈为空，则表示所有括号都匹配，否则不匹配。

3. Python代码实现pythonclass IStack: pass

class SqStack(IStack): def init(self, maxSize): self.maxSize = maxSize self.stackElem = [None] * maxSize self.top = 0

def push(self, x):        self.stackElem[self.top] = x        self.top += 1

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

def pop(self):        if self.isEmpty():            return None        self.top -= 1        return self.stackElem[self.top]

def length(self):        return self.top

def display(self):        for i in range(self.top-1, -1, -1):            print(self.stackElem[i], end=' ')

def matchParentheses(s): st = SqStack(len(s)) unmatched = ''

for i, c in enumerate(s):        if c == '(':            st.push(i)        elif c == ')':            if st.isEmpty():                unmatched += '%'            else:                st.pop()        else:            unmatched += ' '

while not st.isEmpty():        unmatched += '#'        st.pop()

return s, unmatched

s = input('请输入一串字符：')result, unmatched = matchParentheses(s)

print(result)print(unmatched)

代码说明：

SqStack 类实现了栈的数据结构，包括入栈 push，出栈 pop，判断栈空 isEmpty 等操作。- matchParentheses 函数实现了括号匹配算法，并使用 # 标记未匹配的左括号，% 标记未匹配的右括号。

4. 测试

输入字符串 （123））（（abc）ABC（（，运行程序，输出：

（123））（（abc）ABC（（ % # ##

结果显示，该字符串的括号不匹配，未匹配的括号已用 # 和 % 标记。

5. 总结

本文介绍了使用栈解决括号匹配问题的算法，并提供了完整的Python代码实现。栈作为一种简单高效的数据结构，在解决此类问题时非常实用。希望本文能帮助你理解括号匹配算法，并在实际应用中发挥作用。