【7012】括号的匹配

Time Limit: 10 second
Memory Limit: 2 MB

问题描述
假设一个表达式有英文字母(小写),整数，运算符(+,—,*,/)和左右小(圆)括号构成, 以"@"作为表达式的结束符.请编写一个程序检查表达式中的左右圆括号是否匹配,若匹配,则返回"YES";否则返回"NO".假设表达式长度小于255,左圆括号少于20个.

Input

输入算术表达式

Output

输出大写的英文结果

Sample Input1

(22-(18-7))*15@

Sample Output1

YES

Sample Input2

(a+22-(18-f)*15@

Sample Output2

【题解】

这类括号匹配的问题和栈有关。首先。遇到一个左括号就加入栈中。遇到一个右括号就退一个栈。注意，如果退栈的时候，发生栈的下溢。则说明这个右括号是多余的。则可以直接输出无解信息，然后结束程序。否则，如果最后栈为空的。则说明这个字符串的左右括号是匹配的。如果栈最后不为空。则这个字符串中有多余的左括号。

【代码】

#include <cstdio>
#include <string>
#include <iostream>

using namespace std;

string ss;
int top = 0;
char stack[2000];

int main()
{
	//freopen("F:\rush.txt","r",stdin);
	cin >> ss;
	int l = ss.find('@',0); //找到结束符号的位置 
	for (int i = 0;i <= l-1;i++) //在这个结束符号之前的序列。都是所需要判断的字符。 
		if (ss[i] == '(')
			stack[++top] = '(';
				else
					if (ss[i] == ')')
						if (top == 0) //如果多了右括号。则直接输出无解信息。 
							{
								printf("NO");
								return 0;
							}
							else //如果栈不为空。则可以和之前的一个左括号匹配。 
								top--;
	if (top == 0) //如果最后栈为空。则说明匹配成功！ 
		printf("YES");
			else
				printf("NO");
	return 0;
}