Advertisement
Guest User

Parse

a guest
Oct 22nd, 2019
95
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.19 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. using ll = long long;
  6. using ld = long double;
  7. using ull = unsigned long long;
  8.  
  9. bool bad = false;
  10.  
  11. bool isdig(char x) {
  12.     return x == '0' || x == '1';
  13. }
  14.  
  15. ll parseE(const string& s);
  16.  
  17. ll parseN(const string& s) {
  18.     if (s.empty()) {
  19.         bad = true;
  20.         return 0;
  21.     }
  22.     if (s[0] == '0') {
  23.         if (s.size() != 1) {
  24.             bad = true;
  25.         }
  26.         return 0;
  27.     }
  28.  
  29.     ll ans = 0;
  30.     for (char c : s) {
  31.         if (!isdig(c)) {
  32.             bad = true;
  33.             return 0;
  34.         }
  35.         ans = 2 * ans + c - '0';
  36.     }
  37.     return ans;
  38. }
  39.  
  40. ll parseF(const string& s) {
  41.     if (s.empty()) {
  42.         bad = true;
  43.         return 0;
  44.     }
  45.     if (s[0] == '-') {
  46.         return -parseF(s.substr(1, s.size()));
  47.     } else if (s[0] == '(') {
  48.         if (s.back() != ')') {
  49.             bad = true;
  50.             return 0;
  51.         }
  52.         return parseE(s.substr(1, s.size() - 2));
  53.     } else {
  54.         return parseN(s);
  55.     }
  56. }
  57.  
  58. ll parseT(const string& s) {
  59.   //  cerr << s << endl;
  60.     if (s.empty()) {
  61.         bad = true;
  62.         return 0;
  63.     }
  64.     int bal = 0;
  65.     for (int i = s.length() - 1; i >= 0; i--){
  66.         if (s[i] == ')') bal++;
  67.         if (s[i] == '(') bal--;
  68.         if (s[i] == '*' && bal == 0) {
  69.             ll lhs = parseT(s.substr(0, i)), rhs = parseF(s.substr(i + 1, s.size()));
  70.             return lhs * rhs;
  71.         }
  72.     }
  73.  
  74.     return parseF(s);
  75. }
  76.  
  77. ll parseE(const string& s) {
  78.     if (s.empty()) {
  79.         bad = true;
  80.         return 0;
  81.     }
  82.     int bal = 0;
  83.     for (int i = s.length() - 1; i >= 0; i--) {
  84.         if (s[i] == ')') {
  85.             bal++;
  86.         } else if (s[i] == '(') {
  87.             bal--;
  88.         } else if (bal == 0) {
  89.             if (s[i] == '+' || s[i] == '-') {
  90.                 if (i != 0 && i + 1 != s.length()) {
  91.                     if (s[i - 1] == '(') continue;
  92.                     if (s[i - 1] == '+') continue;
  93.                     if (s[i - 1] == '-') continue;
  94.                     if (s[i - 1] == '*') continue;
  95.  
  96.                     ll lhs = parseE(s.substr(0, i));
  97.                     ll rhs = parseT(s.substr(i + 1, s.size()));
  98.                     if (s[i] == '+') {
  99.                         return lhs + rhs;
  100.                     } else {
  101.                         return lhs - rhs;
  102.                     }
  103.                 }
  104.             }
  105.         }
  106.  
  107.         if (bal < 0) {
  108.             bad = true;
  109.             return 0;
  110.         }
  111.     }
  112.     if (bal != 0) {
  113.         bad = true;
  114.         return 0;
  115.     }
  116.     return parseT(s);
  117. }
  118.  
  119. bool check(const string& expr) {
  120.     vector<int> pos;
  121.     for (int i = 0; i < expr.size(); i++) {
  122.         if (expr[i] == '=') {
  123.             pos.push_back(i);
  124.         }
  125.     }
  126.  
  127.     if (pos.size() != 1) {
  128.         return false;
  129.     }
  130.  
  131.     string lhs = expr.substr(0, pos[0]);
  132.     string rhs = expr.substr(pos[0] + 1, expr.size());
  133.     if (lhs.empty() || rhs.empty()) {
  134.         return false;
  135.     }
  136.  
  137.     bad = false;
  138.     bool ok = (parseE(lhs) == parseE(rhs));
  139.     if (bad) {
  140.         return false;
  141.     }
  142.     return ok;
  143. }
  144.  
  145. int main() {
  146. #ifdef NIZNIY_MAGAZIN_MIR_V_CENTRE_VINNITSY
  147.     freopen("in", "r", stdin);
  148. #endif
  149.     ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
  150.     string s;
  151.     cin >> s;
  152.     vector<char> have;
  153.     for (char c : s) {
  154.         if (isupper(c) || islower(c)) {
  155.             have.push_back(c);
  156.         }
  157.     }
  158.  
  159.     sort(have.begin(), have.end());
  160.     have.resize(unique(have.begin(), have.end()) - have.begin());
  161.  
  162.     vector<char> p = {'0', '1', '+', '-', '*', '(', ')', '='};
  163.  
  164.     sort(p.begin(), p.end());
  165.     set<string> go;
  166.  
  167.     do {
  168.         string expr;
  169.         for (int i = 0; i < s.size(); i++) {
  170.             if (isupper(s[i]) || islower(s[i])) {
  171.                 int pos = 0;
  172.                 while (have[pos] != s[i]) pos++;
  173.                 expr += p[pos];
  174.             } else {
  175.                 expr += s[i];
  176.             }
  177.         }
  178.  
  179.  //       assert(expr != "-0=0");
  180.         if (check(expr)) {
  181.             go.insert(expr);
  182.         }
  183.     } while (next_permutation(p.begin(), p.end()));
  184.  
  185.     cout << go.size() << endl;
  186. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement