Parentheses

Questions 1 to 5 of 6

1. 1. What does this program print? ``cpp #include <iostream> #include <string> #include <vector> long long calls = 0; void build(int n, int open, int close, std::string& cur, std::vector<std::string>& out) { calls++; if ((int)cur.size() == 2 * n) { out.push_back(cur); return; } if (open < n) { cur.push_back('('); build(n, open + 1, close, cur, out); cur.pop_back(); } if (close < open) { cur.push_back(')'); build(n, open, close + 1, cur, out); cur.pop_back(); } } int main() { std::vector<std::string> out; std::string cur; build(2, 0, 0, cur, out); std::cout << out.size() << " " << calls << "\n"; } ``

   2 55 82 82 22
2. 2. What does this program print? Each 1 means valid and each 0 means not valid. ``cpp #include <iostream> #include <string> bool is_valid(const std::string& s) { int balance = 0; for (char c : s) { balance += (c == '(') ? 1 : -1; if (balance < 0) return false; } return balance == 0; } int main() { std::cout << is_valid("(()())") << " " << is_valid(")(") << "\n"; } ``

   1 00 11 10 0
3. 3. This build function is meant to list the valid strings for n = 1, but it prints )( as well as (). What is the bug? ``cpp void build(int n, int open, int close, std::string& cur, std::vector<std::string>& out) { if ((int)cur.size() == 2 * n) { out.push_back(cur); return; } if (open < n) { cur.push_back('('); build(n, open + 1, close, cur, out); cur.pop_back(); } if (close < n) { cur.push_back(')'); build(n, open, close + 1, cur, out); cur.pop_back(); } } ``

   The base case should check cur.size() == nThe rule for ) should be close < open, not close < n, because a ) needs an unmatched ( before itpop_back should come before the recursive callThe rule for ( should be open <= n
4. 4. For n = 1 this build function prints (( as a valid string. Which line causes it? ``cpp void build(int n, int open, int close, std::string& cur, std::vector<std::string>& out) { if ((int)cur.size() == 2 * n) { out.push_back(cur); return; } if (open <= n) { cur.push_back('('); build(n, open + 1, close, cur, out); cur.pop_back(); } if (close < open) { cur.push_back(')'); build(n, open, close + 1, cur, out); cur.pop_back(); } } ``

   The base case uses 2 * n, so strings can be too longThe rule for ) is close < open, which lets the closing brackets throughThe rule for ( is open <= n, so a bracket can be added after n opening brackets are placedpop_back is missing after the ) call
5. 5. Which of these is a valid arrangement of brackets for n = 2?

   ))(()(()())((())