daily pastebin goal
49%
SHARE
TWEET

Untitled

a guest Mar 25th, 2019 66 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4.  
  5. using namespace std;
  6.  
  7. struct node {
  8.     char val;
  9.     node *left, *right;
  10.    
  11.     node(char x): val(x) {}
  12. };
  13.  
  14. pair<string, string> parse(string s) {
  15.     int n = (int) s.length();
  16.     int cnt = 0, ind = -1;
  17.     for (int i = 1; i < n - 1; i++) {
  18.         if (s[i] == '(') {
  19.             cnt++;
  20.         } else if (s[i] == ')') {
  21.             cnt--;
  22.         } else if (s[i] == ',' && cnt == 0) {
  23.             ind = i;
  24.             break;
  25.         }
  26.     }
  27.     string a = s.substr(1, ind - 1);
  28.     string b = s.substr(ind + 1, n - ind - 2);
  29.     return make_pair(a, b);
  30. }
  31.  
  32. node *build(string s) {
  33.     node *root;
  34.     if (s.length() == 1) {
  35.         root = new node(s[0]);
  36.         return root;
  37.     } else {
  38.         root = new node(0);
  39.     }
  40.     pair<string, string> res = parse(s);
  41.     root->left = build(res.first);
  42.     root->right = build(res.second);
  43.     return root;
  44. }
  45.  
  46. int main() {
  47.     int k;
  48.     cin >> k;
  49.     while (k--) {
  50.         string s;
  51.         cin >> s;
  52.         node *root = build(s);
  53.         node *ptr = root;
  54.         string t;
  55.         cin >> t;
  56.         for (int i = 0; i < t.length(); i++) {
  57.             if (t[i] == '0') {
  58.                 ptr = ptr->left;
  59.             } else {
  60.                 ptr = ptr->right;
  61.             }
  62.             if (ptr->val != 0) {
  63.                 cout << ptr->val;
  64.                 ptr = root;
  65.             }
  66.         }
  67.         cout << endl;
  68.     }
  69. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top