给定由小写字母、+-*/()组成,以@结尾的数学表达式,判断括号是否合法匹配,合法两个条件:
全程遍历过程中,右括号数量永远不能超过左括号(防止 ))( 这种错位);
全部遍历完后,左括号总数 = 右括号总数。满足输出 YES,否则 NO。
二、算法思路(计数器模拟栈)
定义变量 cnt 记录未闭合左括号数量,初始为 0;
逐个读取字符,读到 @ 立刻停止循环;
读到 (:cnt += 1;
读到 ):cnt -= 1,若此时 cnt < 0,说明右括号多余,直接跳出;
循环结束后,判断 cnt == 0:相等输出 YES,否则 NO。
三、完整代码(Python)python运行s = input()
cnt = 0
for c in s:
if c == '@':
break
if c == '(':
cnt += 1
elif c == ')':
cnt -= 1
# 中途右括号过多,直接非法
if cnt < 0:
break
if cnt == 0:
print("YES")
else:
print("NO")
四、样例推演
样例 1:2*(x+y)/(1-x)@
括号依次:(、)、(、)cnt 变化:1 → 0 → 1 → 0,最终 cnt=0 → YES
样例 2:(25+x)(a(a+b+b)@
多个左括号无对应右括号,循环结束 cnt>0 → NO
错位测试:())(@
字符依次 ( ) ):cnt:1 → 0 → -1,触发 break,最终 cnt≠0 → NO
五、复杂度说明
时间复杂度:(O(n)),n 为表达式长度,仅遍历一次字符串;
空间复杂度:(O(1)),只用单个计数器,不使用栈数组,空间极省。