小王同学做事马虎,特别是做数学作业时,经常会漏掉小括号或左右小括号不匹配。设计一个算法,判断输入的数学公式中小括号是否匹配正确,如果括号匹配错误就给出提示。 例如:输入数学公式 '(1+2) / (4-1 = 1',检查后发现位置 7 的左括号不匹配,输出'位置7的括号不匹配'。注意:位置从1开始计算,并且数学公式里的空格不计算位置。
时间: 2023-05-29 14:06:06 浏览: 354
数据结构中关于括号匹配问题的算法.pdf
算法思路:
使用一个栈(stack)来存储左括号,从左到右遍历字符串,遇到左括号就入栈,遇到右括号就判断栈顶元素是否为相应的左括号,若匹配则出栈,否则括号匹配错误。
具体实现:
1. 定义一个栈,用来存储左括号;
2. 遍历字符串中的每个字符,如果是左括号就入栈,如果是右括号就判断栈顶元素是否为相应的左括号,若匹配则出栈,否则括号匹配错误;
3. 如果遍历完字符串后栈不为空,则说明有左括号没有匹配上右括号,也属于括号匹配错误。
代码实现:
```python
def check_brackets(s):
stack = []
for i, c in enumerate(s):
if c == '(':
stack.append(i) # 左括号入栈
elif c == ')':
if not stack: # 栈为空,说明没有左括号与之匹配
return '位置{}的括号不匹配'.format(i+1)
else:
stack.pop() # 左括号出栈
if stack: # 栈不为空,说明有左括号没有匹配上右括号
return '位置{}的括号不匹配'.format(stack[-1]+1)
else:
return '括号匹配正确'
```
测试:
```python
s = '(1 2) / (4-1 = 1'
print(check_brackets(s)) # 位置7的括号不匹配
s = '(1 + 2) * (5 - 3) / (4 + 1)'
print(check_brackets(s)) # 括号匹配正确
```
阅读全文