**Discussion 11: Stacks**
11/03 (election day holiday), 11/05
[(back to course webpage)](./mcs360_fall2020.html)
# Exercise 1
Given a string of parantheses, write a function that returns `true` if it is balanced, and `false` if it is unbalanced. For example, `(())()` is balanced but `)(` and `())` and `()(` etc. are unbalanced.
Think of an algorithm that uses stacks to solve this problem!
## Algorithm `isStringBalanced(string s)`
+ Create a stack of characters, `stk`. Loop through `i=0` to `s.length()-1`:
* If `s[i] == '('` push `s[i]` on the top of `stk`.
* If `s[i] == ')'` and `stk` is empty, return `false`.
* If `s[i] == ')'` and `stk.top() == '(', do `stk.pop()`.
+ After looping through the string, we want `stk` to be empty. If `!stk.empty()`, return `false` (this means there were too many opening parantheses). Otherwise, return `true`.
## Solution
```cpp
#include
#include
#include
bool isStringBalanced(std::string s) {
std::stack stk;
for(int i = 0; i < s.length(); i++) {
if(s[i] == '(') {
stk.push(s[i]);
}
else if(s[i] == ')') {
if(stk.empty())
return false;
else
stk.pop();
}
// If string has characters not equal to '(' or ')', show an error
else {
std::cout << "Invalid String.\n";
return false;
}
}
// If stack is empty, return true, else return false:
return stk.empty();
}
int main() {
std::vector A ({"(())()", "()(", "(()", ")", ")(", "()()(((()()(()))))"});
for(int i = 0; i < A.size(); i++) {
if(isStringBalanced(A[i]))
std::cout << "String " << A[i] << " is balanced.\n";
else
std::cout << "String " << A[i] << " is unbalanced.\n";
}
return 0;
}
```
## Output
```
(base) potla@EKR:~/Desktop/mcs360$ ./d11
String (())() is balanced.
String ()( is unbalanced.
String (() is unbalanced.
String ) is unbalanced.
String )( is unbalanced.
String ()()(((()()(())))) is balanced.
```