设计一个算法利用顺序栈检查用户输入的表达式中括号是否配对(假设表达式中可能含有圆括号、中括号和大括号)。并用相关数据进行测试。
时间: 2024-11-05 07:26:30 浏览: 22
设计这样一个算法,我们可以创建一个顺序栈(通常基于数组或链表),用于存储左括号。遍历输入的表达式字符串,对于每一个字符:
1. 如果遇到开放括号(如 '(', '[', '{'),将其压入栈中。
2. 如果遇到关闭括号(如 ')', ']', '}'),首先检查栈是否为空。如果空,表示缺少匹配的左括号,返回false。如果非空,弹出栈顶元素,比较其与当前闭合括号是否匹配。如果不匹配,也返回false。如果匹配,则继续处理下一个字符。
3. 遍历完整个表达式后,如果栈为空,说明所有括号都已找到匹配,返回true;否则,返回false,表示还有未匹配的左括号。
下面是一个简单的伪代码示例:
```
function isParenthesesMatch(expression):
stack = []
openBrackets = ['(', '[', '{']
closeBrackets = [')', ']', '}']
for char in expression:
if char in openBrackets:
stack.append(char)
elif char in closeBrackets:
if not stack or stack.pop() != openBrackets[closeBrackets.index(char)]:
return false
return stack.isEmpty()
```
测试示例:
- 测试数据1: 输入 "()",预期结果为 true,因为左右括号配对。
- 测试数据2: 输入 "([])",预期结果为 true,因为所有括号配对。
- 测试数据3: 输入 "({[})]",预期结果为 true,因为所有括号配对。
- 测试数据4: 输入 "([)]",预期结果为 false,因为右括号']'没有匹配的左括号。
- 测试数据5: 输入 "])}",预期结果为 false,因为右括号先于相应的左括号出现。
阅读全文