**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. ```