P1739 表达式括号匹配
题目描述
给定一个表达式。该表达式由数字、小写英文字母、运算符 ‘+’、‘-’、‘*’、‘/’ 和左右圆括号构成,并以字符 ‘@’ 作为结束符。
请你检查表达式中的左右圆括号是否匹配:若匹配,输出 "YES";否则输出 "NO"。
这里,称一个表达式中的左右圆括号匹配,当且仅当从左到右扫描这个表达式时,任意时刻已经出现的右括号数量都不超过已经出现的左括号数量,并且扫描结束时左右括号数量相等。
输入格式
输入一行一个字符串 s(1≦∣s∣<255) 代表待检查的表达式。s 由数字、小写英文字母、运算符 ‘+’、‘-’、‘*’、‘/’ 和左右圆括号构成,且以字符 ‘@’ 结尾,‘@’ 只在末尾出现一次;s 中的左圆括号少于 20 个。
输出格式
若表达式中的左右圆括号匹配,在一行上输出 "YES";否则输出 "NO"。
测试样例
2*(x+y)/(1-x)@
YES
样例 1 解释
用余额表示当前已经出现的左括号数量减去右括号数量。从左到右扫描表达式:
∙遇到左括号时余额加 1,遇到右括号时余额减 1,其余字符不影响余额;
∙表达式中的括号依次为 "("、")"、"("、")",余额依次为 1,0,1,0,整个过程中从未出现负数;
∙扫描结束后余额为 0,即左右括号数量相等,因此输出 "YES"。
(25+x)*(a*(a+b+b)@
NO