Open the Brackets

题目描述

There is a syntactically correct boolean expression.

The definition of syntactically correct expression follows as:

1. “a”, “b”, “c”, …, “j” are syntactically correct expressions.
2. If A is a correct expression, then !A and (A) are correct expressions too.
3. If A is a correct expression and B is a correct expression, then AB, A&B, A<=>B, A=>B, A#B are syntactically correct expressions too.

Syntactically correct expression doesn’t contain spaces.

Small Latin letters are variables, ! denotes negation, - disjunction, & - conjunction, <=> - equality, => - implication, # - excepting or.

Negation has the highest priority, conjunction has middle priority, and other operations have low priority. Brackets change the order of operations executing.

Two expressions are called identical if their values are the same in any values of variables.

Make the expression, which will be identical with given expression. New expression must be free of brackets.

题意概述

将一个逻辑表达式$s$转化成一个不包含括号的等价表达式$t$。保证$s$中变量的个数不超过$10$。

数据范围：$1 \le |s| \le 2048, \ 1 \le |t| \le 32768$。

算法分析

由于变量数不超过$10$，因此可以枚举每个变量的值，计算表达式的值，若为真，则在答案中加入这个状态（状态间用隔开，变量间用&隔开）。如果最后答案为空，则直接输出!a&a。

代码

#include <cmath>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <stack>

using namespace std;

struct Solver {
private:
  string s;
  void input() { cin >> s; }
  int len(char c) {
    switch (c) {
      case '!' : return 0;
      case '&' : return 0;
      case '|' : return 1;
      case '<' : return 2;
      case '=' : return 1;
      case '#' : return 0;
    }
  }
  int priority(char c) {
    switch (c) {
      case '!' : return 1;
      case '&' : return 2;
      case '|' : return 3;
      case '<' : return 3;
      case '=' : return 3;
      case '#' : return 3;
      case '(' : return 4;
    }
  }
  bool single(bool a, char c, bool b) {
    switch (c) {
      case '&' : return a && b;
      case '|' : return a || b;
      case '<' : return a == b;
      case '=' : return a || ! b;
      case '#' : return a ^ b;
    }
  }
  int match(string s, int p) {
    int cnt = 1;
    while (cnt) ++ p, cnt += (s[p] == '(') - (s[p] == ')');
    return p;
  }
  stack <char> symbol;
  stack <bool> number;
  void pop() {
    if (symbol.top() == '!') {
      symbol.pop(); bool p = number.top(); number.pop(), number.push(! p);
    } else {
      bool p = number.top(); number.pop();
      bool q = number.top(); number.pop();
      number.push(single(p, symbol.top(), q));
      symbol.pop();
    }
  }
  bool calc(string s) {
    for (int i = 0; i < s.length(); ++ i) {
      if (isdigit(s[i])) number.push(s[i] - '0');
      else if (s[i] == '(') symbol.push('(');
      else if (s[i] == ')') {
        while (symbol.top() != '(') pop();
        symbol.pop();
      } else {
        while (! symbol.empty() && priority(symbol.top()) <= priority(s[i])) pop();
        symbol.push(s[i]), i += len(s[i]);
      }
    }
    while (! symbol.empty()) pop();
    return number.top();
  }
  bool check(int p, string s) {
    for (int i = 0; i < s.length(); ++ i)
      if (isalpha(s[i])) s[i] = ((p & 1 << s[i] - 'a') > 0) + '0';
    return calc(s);
  }
  void process() {
    for (int i = 0; i + 1 < s.length(); ++ i)
      while (i + 1 < s.length() && s[i] == '!' && s[i + 1] == '!')
        s = s.substr(0, i) + s.substr(i + 2);
    string ans, sep;
    for (int i = 0; i < 1 << 10; ++ i)
      if (check(i, s)) {
        ans += sep, sep = "||";
        string s;
        for (int j = 0; j < 10; ++ j) {
          ans += s, s = "&";
          if (! (i & 1 << j)) ans += "!";
          ans += j + 'a';
        }
      }
    if (ans.length() == 0) ans = "!a&a";
    cout << ans << endl;
  }

public:
  void solve() { input(), process(); }
} solver;

int main() {
  solver.solve();
  return 0;
}