主要内容 #

1. 问题描述
2. 问题分析
3. 参考代码

1. 问题描述 #

假设一个表达式有英文字母（小写）、运算符（+，—，∗，/）和左右小（圆）括号构成，以“@”作为表达式的结束符。请编写一个程序检查表达式中的左右圆括号是否匹配，若匹配，则返回“YES”；否则返回“NO”。表达式长度小于255，左圆括号少于20个。
输入描述
一行数据，即表达式。
输出描述
一行，即“YES” 或“NO”。
输入样例
2*(x+y)/(1-x)@
输出样例
YES

2. 问题分析 #

假设输入的字符串存储在一个C风格的字符串中（char str[255]）。
我们可以定义一个栈：char str[256]，用它来存放从左到右的括号。
自左向右地逐个考查 str 中每个字符，如果遇到左括号，则将该括号入栈，如果遇到右括号，则将其与栈顶的括号比对，如果能正好凑成一对括号，则将栈顶的括号出栈，继续考查str中的下一个字符。如果不能正好凑成一对括号，则该str中的括号一定是不匹配的。如果str中所有字符都考察完了，而栈不为空，str中的括号也是不匹配的。

3. 参考程序 #

#include <iostream>
#include <cstring>
#include <cstdio> 
using namespace std;
int main()
{
	char str[255];
	cin >>str;		
	int i=0,top=0;	
	cout << 3 << endl;
	while(str[i]!='@')	
	{
		if(str[i]=='(') top++; //表示左括号的数量	 
		if(str[i]==')')  		 
		{
			if(top>=0) top--; //遇到匹配的括号则将相应的左括号弹出	  
			else	break;    //右括号数目多于左括号数目
		}
		i++;					 
	}
	if(top!=0) cout<<"NO";
	else cout<<"YES"; 
}