假设一个算术表达式中包含三种括号:圆括号“(”和“)”,方括号“[”和“]”以及花括号“{”和“}”,且这三种括号可按任意的次序嵌套使用,如(.. .[.. .{.. .}.. .[.. .].. .].. .( .. .[.. .].. .)。试利用栈的运算编写判断给定表达式中所含括号是否正确配对出现的算法。 其中exp为字符串类型的变量。如果括号正确配对,则输出“ ”并返回1;否则输出“Mismatch”和栈中元素,并返回0。
时间: 2023-06-15 07:06:52 浏览: 104
可以使用栈来判断括号是否正确配对。具体步骤如下:
1.创建一个空栈。
2.遍历表达式中的每个字符,如果是左括号(即“(”、“[”或“{”),则将其压入栈中。
3.如果是右括号(即“)”、“]”或“}”),则弹出栈顶元素并判断其是否与当前右括号匹配。如果不匹配,则输出“Mismatch”和栈中元素,并返回0。
4.如果遍历完表达式后栈为空,则说明括号正确配对,输出“ ”并返回1;否则说明还有括号未被匹配,输出“Mismatch”和栈中元素,并返回0。
下面是具体的实现代码:
```python
def check_brackets(exp):
stack = []
for ch in exp:
if ch in ['(', '[', '{']:
stack.append(ch)
elif ch in [')', ']', '}']:
if not stack:
print("Mismatch")
return 0
top = stack.pop()
if (ch == ')' and top != '(') or (ch == ']' and top != '[') or (ch == '}' and top != '{'):
print("Mismatch")
return 0
if not stack:
print(" ")
return 1
else:
print("Mismatch:", stack)
return 0
```
可以使用以下代码测试该函数:
```python
exp = "(.. .[.. .{.. .}.. .[.. .].. .].. .( .. .[.. .].. .))"
check_brackets(exp) # 输出" "并返回1
exp = "(.. .[.. .{.. .}.. .[.. .].. .].. .( .. .[.. .].. .))"
exp = exp.replace("[", "]")
exp = exp.replace("(", "{")
check_brackets(exp) # 输出"Mismatch: ['{', ']']"并返回0
```
阅读全文