paren_changes

#include <iostream>
#include <stack>
#include <string>
#include <queue>
#include <vector>
using namespace std;

bool is_valid_parens(const string &parens) {
  stack<char> s;
  for (size_t i = 0; i < parens.length(); ++i) {
    if (parens[i] == '(') {
      s.push(parens[i]);
    } else {
      if (s.size() > 0) {
        s.pop();
      } else {
        return false;
      }
    }
  }
  return (s.size() == 0);
}

void swap(char &c) {
  if (c == '(') c = ')';
  else c = '(';
}

struct Node {
  string parens;
  vector<int> indexes;
};

void bfs(Node n) {
  queue<Node> to_visit;
  to_visit.push(n);

  while (to_visit.size() > 0) {
    Node current = to_visit.front();
    to_visit.pop();

    // cout << current.parens << endl;
    if (is_valid_parens(current.parens)) {
      cout << endl << "Final" << endl;
      cout << current.parens << endl;
      cout << "{ ";
      for (size_t i = 0; i < current.indexes.size(); ++i) {
        cout << current.indexes[i] << " ";
      }
      cout << "}" << endl;
      return;
    }

    for (size_t i = 0; i < current.parens.length(); ++i) {
      Node new_node;
      new_node.parens = current.parens;
      swap(new_node.parens[i]);
      new_node.indexes = current.indexes;
      new_node.indexes.push_back(i);
      to_visit.push(new_node);
    }
  }
}

int main() {
  Node n;
  n.parens = ")))))(((((";
  cout << "Input: " << endl << n.parens << endl;
  bfs(n);
  return 0;
}