LG#P1739. 表达式括号匹配

表达式括号匹配

P1739 表达式括号匹配

题目描述

\hspace{15pt}给定一个表达式。该表达式由数字、小写英文字母、运算符 ‘+’\texttt{`+'}、‘-’\texttt{`-'}、‘*’\texttt{`*'}、‘/’\texttt{`/'} 和左右圆括号构成,并以字符 ‘@’\texttt{`@'} 作为结束符。

\hspace{15pt}请你检查表达式中的左右圆括号是否匹配:若匹配,输出 "YES"\texttt{"YES"};否则输出 "NO"\texttt{"NO"}。

\hspace{15pt}这里,称一个表达式中的左右圆括号匹配,当且仅当从左到右扫描这个表达式时,任意时刻已经出现的右括号数量都不超过已经出现的左括号数量,并且扫描结束时左右括号数量相等。

输入格式

\hspace{15pt}输入一行一个字符串 s(1≦∣s∣<255)s \left(1 \leqq |s| < 255\right) 代表待检查的表达式。ss 由数字、小写英文字母、运算符 ‘+’\texttt{`+'}、‘-’\texttt{`-'}、‘*’\texttt{`*'}、‘/’\texttt{`/'} 和左右圆括号构成,且以字符 ‘@’\texttt{`@'} 结尾,‘@’\texttt{`@'} 只在末尾出现一次;ss 中的左圆括号少于 2020 个。

输出格式

\hspace{15pt}若表达式中的左右圆括号匹配,在一行上输出 "YES"\texttt{"YES"};否则输出 "NO"\texttt{"NO"}。

测试样例

2*(x+y)/(1-x)@
YES

样例 1 解释

\hspace{15pt}用余额表示当前已经出现的左括号数量减去右括号数量。从左到右扫描表达式:

∙ \hspace{23pt}\bullet\,遇到左括号时余额加 11,遇到右括号时余额减 11,其余字符不影响余额;

∙ \hspace{23pt}\bullet\,表达式中的括号依次为 "("\texttt{"("}、")"\texttt{")"}、"("\texttt{"("}、")"\texttt{")"},余额依次为 1,0,1,01,0,1,0,整个过程中从未出现负数;

∙ \hspace{23pt}\bullet\,扫描结束后余额为 00,即左右括号数量相等,因此输出 "YES"\texttt{"YES"}。

(25+x)*(a*(a+b+b)@
NO