« Balanced Parenthesis

Problem

For a given a string expression containing only round brackets or parentheses, check if they are balanced or not. Brackets are said to be balanced if the bracket which opens last, closes first.

Example:

Expression: (()())

Since all the opening brackets have their corresponding closing brackets, we say it is balanced and hence the output will be, 'true'. You need to return a boolean value indicating whether the expression is balanced or not.

Note:

The input expression will not contain spaces in between.

Input Format:

The first and the only line of input contains a string expression without any spaces in between.

Output Format:

The only line of output prints 'true' or 'false'.

Note:

You don't have to print anything explicitly. It has been taken care of. Just implement the function.

Constraints:

1 <= N <= 10^7 Where N is the length of the expression.

Time Limit: 1sec

Sample Input 1 :

(()()())

Sample Output 1 :

true

Sample Input 2 :

()()(()

Sample Output 2 :

false

Explanation to Sample Input 2:

The initial two pairs of brackets are balanced. But when you see, the opening bracket at the fourth index doesn't have its corresponding closing bracket which makes it imbalanced and in turn, making the whole expression imbalanced. Hence the output prints 'false'.

Solution:

Copy
1#include <iostream>
2#include <string>
3#include<stack>
4using namespace std;
5
6bool isBalanced(string expression)
7{
8    stack<char> s;
9    for(int i=0;i<expression.length(); i++){
10        if(expression[i] == '('){
11            s.push('(');
12        }else{
13            if(s.size() > 0 && s.top() == '('){
14                s.pop();
15            }else{
16                return false;
17            }
18        }
19    }
20    if(s.size() == 0){
21        return true;
22    }
23    return false;
24}
25
26int main()
27{
28    string input;
29    cin >> input;
30    cout << ((isBalanced(input)) ? "true" : "false");
31    return 0;
32}