Algorithm/BalancedParenthesis.cpp at master · vksahu399/Algorithm · 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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include <bits/stdc++.h>

using namespace std;

/*

	this function will return true only when the popped element matches the category of the closing 	bracket.

	Otherwise, we will return false.

*/

bool isMatching(char openingBracket, char closingBracket) {

	if(openingBracket == '{' && closingBracket == '}')

		return true;

	if(openingBracket == '(' && closingBracket == ')')

		return true;

	if(openingBracket == '[' && closingBracket == ']')

		return true;

	return false;

}

/* function which will return whether the expression is balanced or not */

bool isBalanced(string expression) {

	/* initialization of stack of characters */

	stack<char> s;


	/* start iterating over the string */

	for(int i = 0; i < expression.length(); i++) {

		/* if expression is any of the opening brackets, push it onto the stack */

		if(expression[i] == '{' || expression[i] == '(' || expression[i] == '[') {

			s.push(expression[i]);

		}

		else {

			/*

				check if stack is empty, return false directly.

				Because, having a closing bracket without any opening bracket doesn't mean balanced.

			 */

			if(s.empty()) {

				return false;

			}

			/*

				otherwise check if, current closing brackets matches with the

				category of top element of stack, if it so we pop the element.

				Otherwise, we directly return false.

			*/

			else if(!isMatching(s.top(), expression[i])){

					return false;

			}

			s.pop();

		}

	}

	/*

		if everything is perfect till here and stack becomes empty, means the expression is balanced

		otherwise, if stack doesn't become empty, then return false.

	 */

	if(s.empty())

		return true;

	return false;

}

int main(int argc, char const *argv[]) {

	string expression1 = "[[({})]]";

	string expression2 = "[[))";

	cout << isBalanced(expression1) << endl;

	cout << isBalanced(expression2) << endl;

	return 0;

}