cs204/brackets.cpp at master · ktk53x/cs204 · GitHub

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include<bits/stdc++.h>

using namespace std;

bool isBalanced(string expr)
{
	stack<char> s;
	char x;
	for(int i = 0; i < expr.length(); i++)
	{
		if(expr[i] == '(' || expr[i] == '{' || expr[i] == '[' || expr[i] == '<')
		{
				s.push(expr[i]);
		}

		if(expr[i] == '|')
		{
				if(!s.empty() && s.top() == '|')
					s.pop();
				else
					s.push(expr[i]);
		}
		else
		{
			if(s.empty())
				return false;
			switch(expr[i])
			{
				case ')':
					x = s.top();
					s.pop();
					if(x != '(')
						return false;
					break;
				case '}':
					x = s.top();
					s.pop();
					if(x != '{')
						return false;
					break;
				case ']':
					x = s.top();
					s.pop();
					if(x != '[')
						return false;
					break;
				case '>':
					x = s.top();
					s.pop();
					if(x != '<')
						return false;
					break;

			}
		}
	}
	return (s.empty());
}

int main()
{
	int n;
	cin >> n;
	string expr;
	while(n--)
	{
		cin >> expr;
		if(isBalanced(expr))
			cout << "YES\n";
		else
			cout << "NO\n";
	}
	return 0;
}