南京邮电大学离散数学实验

#include <cmath> #include <iostream> #include <set> #include <stack> #include <string> #include <vector> using std::set; using std::vector; using std::string; using std::cin; using std::cout; using std::endl; bool cToB(char input) { return input == '1'; } char bToC(bool input) { return input ? 1 : 0; } string bToS(bool input) { return input ? "1" : "0"; } int strReplace(string& str, const string& src, const string& dest) { int counter = 0; string::size_type pos = 0; while ((pos = str.find(src, pos)) != string::npos) { str.replace(pos, src.size(), dest); ++counter; pos += dest.size(); } return counter; } string inffixToSuffix(string input) { std::stack<char> s; string output = ""; for (string::iterator c = input.begin(); c != input.end(); ++c) { switch (*c) { case '1': case '0': output += *c; break; case '(': s.push(*c); break; case ')': while (!s.empty()) { if (s.top() == '(') { s.pop(); break; } output += s.top(); s.pop(); } break; case '!': s.push(*c); break; case '|': case '&': while (!s.empty() && s.top() != '(' && s.top() != '>' && s.top() != '=') { output += s.top(); s.pop(); } s.push(*c); break; case '>': case '=': while (!s.empty() && s.top() != '(') { output += s.top(); s.pop(); } s.push(*c); break; } } while (!s.empty()) { output += s.top(); s.pop(); } return output; } bool calcSuffixExpr(string input) { std::stack<bool> s; for (string::iterator c = input.begin(); c != input.end(); ++c) { if (*c == '0' || *c == '1') { s.push(cToB(*c)); } else if (*c == '!') { bool x = s.top(); s.pop(); s.push(!x); } else { bool x = s.top(); s.pop(); bool y = s.top(); s.pop(); bool result; switch (*c) { case '|': result = x | y; break; case '&': result = x & y; break; case '>': result = (!x) | y; break; case '=': result = (x == y); break; } s.push(result); } } return s.top(); } void parseInput(string input, vector<string>& output) { string now; string symbols = "!()&|=>"; set<string> outputSet; for (string::iterator c = input.begin(); c != input.end(); ++c) { if (symbols.find(*c) == string::npos) { now += *c; } else { if (now.length() != 0) { outputSet.insert(now); now = ""; } } } if (now.length() != 0) { outputSet.insert(now); now = ""; } for (set<string>::iterator str = outputSet.begin(); str != outputSet.end(); ++str) { output.push_back(*str); } } int main() { cout << "请使用 ! | & > =" << endl; cout << "hello,using ! | & > = please" << endl; string input; cin >> input; vector<string> varName; parseInput(input, varName); int varNum = varName.size(); int tableNum = (int)pow(2, varNum); bool table[tableNum][varNum + 1]; for (int i = 0; i < tableNum; i++) { int num = i; for (int j = 0; j < varNum; j++) { table[i][j] = num % 2; num /= 2; } } cout << "真值表" << endl; cout << "Truth table" << endl; for (int i = 0; i < varNum; i++) { cout << varName[i] << '\t'; } cout << input << endl; for (int i = 0; i < varNum + 1; i++) { cout << "-\t"; } cout << endl; for (int i = 0; i < tableNum; i++) { string expr = input; for (int j = 0; j < varNum; j++) { strReplace(expr, varName[j], bToS(table[i][j])); cout << bToS(table[i][j]) << "\t"; } string suffixExpr = inffixToSuffix(expr); table[i][varNum] = calcSuffixExpr(suffixExpr); cout << table[i][varNum] << endl; } cout << "主合取范式" << endl; cout << "Principal Conjunctive Normal Form" << endl; bool first = true; for (int i = 0; i < tableNum; i++) { if (table[i][varNum]) { continue; } if (first) { first = false; } else { cout << "&"; } cout << "("; for (int j = 0; j < varNum; j++) { if (table[i][j]) { cout << "!"; } cout << varName[j]; if (j != varNum - 1) { cout << "|"; } } cout << ")"; } cout << endl; cout << "主析取范式" << endl; cout << "Principal Disjunctive Normal Form" << endl; first = true; for (int i = 0; i < tableNum; i++) { if (table[i][varNum] == false) { continue; } if (first) { first = false; } else { cout << "|"; } cout << "("; for (int j = 0; j < varNum; j++) { if (table[i][j] == false) { cout << "!"; } cout << varName[j]; if (j != varNum - 1) { cout << "&"; } } cout << ")"; } cout << endl; return 0; }