(洛谷) P1739 表达式括号匹配

发表于 更新于 分类于 ，

题目描述

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

输入格式

一行：表达式。

输出格式

一行：YES 或 NO。

样例 #1

样例输入 #1

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

样例输出 #1

1
YES

样例 #2

样例输入 #2

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

样例输出 #2

1
NO

提示

表达式长度小于 255255，左圆括号少于 2020 个。

题解

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
37
38
39
40
41
#include<iostream>
#include<stack>
#include<string>

using namespace std;

int main()
{
	stack<int> input;
	string str;
	cin >> str;
	str.pop_back();
	for (auto i : str)
	{
		if (i == '(')
		{
			input.push(i);
		}
		else if (i == ')')
		{
			if (input.empty())
			{
				cout << "NO" << endl;
				return 0;
			}
			else
			{
				input.pop();
			}
		}
	}
	if (input.empty())
	{
		cout << "YES" << endl;
	}
	else
	{
		cout << "NO" << endl;
	}
	return 0;
}