建立一个字符栈,实现括号匹配检查的算法isMatched(char *ex),即输入一个各种括号构成的字符串, 检查每个左括号是否有对应的右括号与其匹配,如果匹配返回1,否则返回0
时间: 2024-10-21 22:07:39 浏览: 14
为了实现这个功能,我们可以使用两个栈数据结构,一个用于存储打开的括号(left stack),另一个用于临时存放当前遇到的左括号(temp stack)。当遍历到一个左括号时,我们将其压入temp栈,然后继续扫描。如果我们遇到一个右括号,我们首先检查temp栈是否为空,如果空则说明无法找到匹配的左括号,返回0。如果temp栈不为空,我们将temp栈顶元素与当前右括号配对,同时将temp栈顶元素弹出,继续扫描。遍历结束后,如果temp栈为空且所有括号都被正确匹配,则返回1;否则返回0。
以下是伪代码的概览:
```python
function isMatched(char* expression):
left_stack = []
temp_stack = []
for char in expression:
if char == '(' or char == '{' or char == '[': // 遇到左括号
temp_stack.push(char)
elif (char == ')' and temp_stack.top() != '(') ||
(char == '}' and temp_stack.top() != '{') ||
(char == ']' and temp_stack.top() != '['): // 匹配失败
return 0
else: // 遇到右括号
temp_stack.pop()
// 如果temp栈为空,表示所有括号都已匹配
return temp_stack.isEmpty()
```
阅读全文