【P No. 1739】 括号匹配

【P No. 1739】 括号匹配

洛谷原题地址

【题意】

假设一个表达式由英文字母（小写）、运算符（+、-、*、/）和左右小圆括号构成，以“@”作为表达式的结束符（表达式的长度小于255，左圆括号少于20个）。请编写一个程序检查表达式中的左右圆括号是否匹配，若匹配，则返回“YES”，否则返回“NO”。

【输入输出】

输入：

每个测试用例都对应一行表达式。

输出：

对每个测试用例都单行输出“YES” 或“NO”。

【样例】

【思路分析】

简单题，只有左右小括号，可以将左圆括号入栈，遇到右圆括号时，弹出栈顶的左圆括号，如果栈空，则说明右圆括号多了。

如果在表达式处理完毕后，在栈中还有元素，则说明左圆括号多了。

【算法设计】

① 初始化一个栈s。

② 读取字符c，如果 c != ‘@’，则执行第 3 步，否则转向 第 5 步。

③ 如果 c = ‘(’，则入栈 s.push©。

④ 如果c =‘)’，则判断栈是否为空，如果栈非空，则出栈，否则输出“NO”，结束。

⑤ 在字符串处理完毕，判断栈是否为空，如果栈为空，则说明正好配对，输出“YES”，否则输出“NO”，结束。

【完美图解】

① 以输入样例“2*(x+y)/(1-x)@”为例，初始化一个栈

② 读入字符“2*(”，遇到左圆括号时入栈

③ 继续读入“x+y)”，遇到右圆括号时，如果栈非空，则出栈

④ 继续读入“/(”，遇到左圆括号时入栈

⑤ 继续读入“1-x)”，遇到右圆括号时，如果栈非空，则出栈

⑥ 继续读入“@”，遇到“@”，字符串读入完毕，此时栈为空，说明括号匹配，输出“YES”。

【算法实现】

#include
#include
#include
#include
using namespace std;

int main(){
	
	char c;
	
	stack<char> s;
	while(cin >> c && c != '@'){
		
		if( c== '('){
			s.push(c);
		}
		
		if(c == ')'){
			if(!s.empty()){	
				s.pop();	
			}
			else{
				cout << "NO" << endl;
				return 0;
			}
		}
	}	
	if(s.empty()){
		cout << "YES" << endl;
	}
	else{
		
		cout << "NO" << endl;
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36