这学期上离散数学实验课，遇到了两个有意思的题目
第一个是输入表达式例如p&q，求出这个表达式的真值表，进而求出它的主合取范式和主析取范式。
其实后面的很无聊，有意思的是根据表达是生成真值表，这就类似于给你一个数学表达式（a+b)/(c*d),然后根据a b c d 的不同取值求出表达式的结果，这里解析这个表达式是一个重点，还要考虑括号的优先级问题，如果你想到把中缀表达式换成后缀表达式，那么好吧，你已经大概知道这个程序的主要结构了～
#include <iostream>
#include <cmath>
#include<stack>
#include<deque>
#include<string>
#include<map>
using namespace std;
const int M = 10; //真值表最大列数
const int N = 520; //真值表最大行数
class Expression {
private:
string coll1; //中缀表达式
stack<char> coll2; //操作符
deque<char> coll3; //后缀表达式
stack<int> coll4; //辅助计算后缀表达式
//获得条件表达式的值
int getValueSingle(int a, int b){
if (a == 1 && b == 0)
return 0;
else
return 1;
}
//获得双条件表达式的值
int getValueDouble(int a, int b){
if ((a == 1 && b == 1) || (a == 0 && b == 0))
return 1;
else
return 0;
}
//获得符号的优先性
int getPri(char c) {
switch(c) {
case '!':
return 4;
break;
case '&':
return 3;
break;
case '|':
return 2;
break;
case '-':
return 1;
break;
case '=':
return 0;
break;
case '(':
case ')':
return -1;
break;
}
}
//处理符号
void check(char c) {
if(coll2.empty()) {
coll2.push(c);
return;
}
if(c == '(' || c == ')') {
if(c=='(')
coll2.push(c);
else {
while(coll2.top()!='(') { //弹出所有元素直到遇到左括号
char ch = coll2.top();
coll3.push_back(ch);
coll2.pop();
}
coll2.pop();
}
}
else {
char sym = coll2.top();
if(getPri(c)<=getPri(sym)) {
coll2.pop();
coll3.push_back(sym);
check(c);
}
else {
coll2.push(c);
}
}
}
//从coll中取出元素，分配元素到coll2和coll3中
void allocate() {
for (int i=0; i<coll1.size(); i++) {
char c = coll1[i];
if('A'<c && 'Z'>c) {
coll3.push_back(c);
}
else
check(c);
}
while(!coll2.empty()) { //如果输入结束，将coll2的元素全部弹出，加入后缀表达式中
char c = coll2.top();
coll3.push_back(c);
coll2.pop();
}
}
public:
Expression(string str): coll1(str){
allocate(); //从coll中取出元素，分配元素到coll2和coll3中
}
//计算后缀表达式
int calculate(char bianyuan[], int array[], int n) {
deque<char>coll3 = this->coll3;
stack<int>coll4;//辅助计算结果
map<char, int> myMap;
for (int i=0; i<n; i++){
myMap[bianyuan[i]] = array[i];
}
while(!coll3.empty()) {
char c = coll3.front();
coll3.pop_front();
if('A'<c && c<'Z') {
int op = myMap[c];
coll4.push(op);
}
else if (c == '!'){
int op = coll4.top();
coll4.pop();
coll4.push(!op);
}
else { //如果是操作符，从栈中弹出元素进行计算
int op1 = coll4.top();
coll4.pop();
int op2 = coll4.top();
coll4.pop();
switch(c) {
case '&':
coll4.push(op2&op1);
break;
case '|':
coll4.push(op2|op1);
break;
case '-':
coll4.push(getValueSingle(op2, op1));
break;
case '=':
coll4.push(getValueDouble(op2, op1));
break;
}
}
}
return coll4.top();
}
};
//二进制转化成为十进制
int changeToDec(int a[], int n){
int sum = 0;
for (int i=0; i<n; i++){
sum += (int)pow(2, n-i-1) * a[i];
}
return sum;
}
int main(){
string str; //表达式
int num; //变元个数
int small[M] = {0}; //存储小项
int big[M] = {0}; //存储大项
char bianyuan[M-1]; //变元数组
int elements[N][M] = {0}; //真值表矩阵
cout << "请输入变元数量(小于等于9)" << endl;
cin >> num;
cout << "请依次输入各个变元名称" << endl;
char temp;
//输入变元并判断输入是否合法
for (int i=0; i<num; i++){
while (true){
cin >> temp;
if (temp<'A' || temp>'Z')
cout << "请输入大写字母" << endl;
else{
bool flag = true;
for (int k=0; k<M-1; k++){
if (temp == bianyuan[k]){
cout << "不能与已输入字符相同" << endl;
flag = false;
break;
}
}
if (!flag)
continue;
bianyuan[i] = temp;
break;
}
}
}
//生成真值表
int rows = (int)pow(2, num); //行数
for (int j=0; j<num; j++){
int flag = 0;
int k = (int)pow(2, num-j-1);
int count = 0;
for (int l=0; l<rows; l++){
if (!flag){
elements[l][j] = 0;
count++;
}
else{
elements[l][j] = 1;
count++;
}
if (!(count % k))
flag = !flag;
}
}
//输入表达式并得到结果
cout << "请输入表达式";
cin >> str;
Expression e(str);
int rcount = 0;
int lcount = 0;
for (int m=0; m<rows; m++){
elements[m][num] = e.calculate(bianyuan, elements[m], num);
if (elements[m][num] == 1){
small[rcount] = changeToDec(elements[m], num);
rcount++;
} else {
big[lcount] = changeToDec(elements[m], num);
lcount++;
}
}
//输出真值表
for (int b=0; b<num; b++){
cout << bianyuan[b] << " ";
}
cout << endl;
for (int a=0; a<rows; a++){
for (int b=0; b<=num; b++){
if (elements[a][b] == 1)
cout << 'T' << " ";
else
cout << 'F' << " ";
}
cout << endl;
}
//输出结果
cout << "主析取范式如下" << endl;
for (int k=0; k<rcount; k++){
cout << "m" << small[k];
if (k!=rcount-1)
cout << "||";
}
cout << endl;
cout << "主合取范式如下" << endl;
for (int l=0; l<lcount; l++){
cout << "M" << big[l];
if (l!=lcount-1)
cout << " && ";
}
cout << endl;
return 0;
}
第二个程序是关于欧拉回路的寻找，这里要用到深度优先的搜索方法。
int P[100][100]; //邻接矩阵
int closeP[100][100]; //邻接矩阵的闭包
int visited[100][100]; //深度优先搜索中已经搜索过的 边
int print[10000]; //路或者回路
int numOfBian = 0; //边的数量
#include <iostream>
#include <ctime>
#include <cstdlib>
using namespace std;
void createP(int n){ //根据节点数量随机创建邻接矩阵
for (int i=0; i<n; i++){
for (int j=0; j<n; j++){
if (i == j){
P[i][j] = 0;
} else {
int temp = rand()%2;
P[i][j] = temp;
P[j][i] = temp;
}
}
}
}
void printP(int n){ //输出邻接矩阵
for (int i=0; i<n; i++){
for (int j=0; j<n; j++){
cout << P[i][j] << " ";
}
cout << endl;
}
}
bool isLianTong(int n){ //生成邻接矩阵的闭包并判断是否连通
for (int i=0; i<n; i++){
for (int j=0; j<n; j++){
closeP[i][j] = P[i][j];
}
}
for (i=0; i<n; i++){
for (int j=0; j<n; j++){
if (closeP[j][i] != 0){
for (int k=0; k<n; k++){
closeP[j][k] += closeP[i][k];
}
}
}
}
for (i=0; i<n; i++){
for (int j=0; j<n; j++){
if (closeP[i][j] == 0)
return false;
}
}
return true;
}
int judge(int n){ //根据奇度数节点和偶度数节点的个数判断图是否为欧拉图（半欧拉图）
int countJi = 0;
int countOu = 0;
for (int i=0; i<n; i++){
int count = 0;
for (int j=0;j<n; j++){
if (P[i][j] == 1)
count++;
}
if (count % 2 == 0)
countOu++;
else
countJi++;
}
//cout << countJi;
//cout << countOu;
if (countJi == 0 && countOu == n){
cout << "是欧拉图" << endl;
return 1;
}
else if (countJi == 2){
cout << "是半欧拉图但不是欧拉图" << endl;
return 2;
}
else{
cout << "不是欧拉半图" << endl;
return 3;
}
}
bool visit(int n, int first, int shengdu){//深度优先搜索欧拉回路
//cout << first << "," << shengdu << endl;
if (shengdu == numOfBian && first == 0){
print[shengdu] = first;
return true;
}
for (int i=0; i<n; i++){
if ((P[i][first] == 1||P[first][i] == 1) && visited[first][i] == 0 && visited[i][first] == 0){
visited[first][i] = 1;
visited[i][first] = 1;
if (visit(n, i,shengdu+1)){
print[shengdu] = first;
return true;
} else {
visited[first][i] = 0;
visited[i][first] = 0;
}
}
}
return false;
}
bool visitHalf(int n, int first, int shengdu){//深度优先搜索欧拉路（非欧拉回路的欧拉路）
//cout << first << "," << shengdu << endl;
if (shengdu == numOfBian){
print[shengdu] = first;
return true;
}
for (int i=0; i<n; i++){
if ((P[i][first] == 1||P[first][i] == 1) && visited[first][i] == 0 && visited[i][first] == 0){
visited[first][i] = 1;
visited[i][first] = 1;
if (visitHalf(n, i,shengdu+1)){
print[shengdu] = first;
return true;
} else {
visited[first][i] = 0;
visited[i][first] = 0;
}
}
}
return false;
}
void findEuler(int n){//搜索欧拉回路
numOfBian = 0;
for (int i=0; i<n; i++){
for (int j=0; j<n; j++){
if (P[i][j] == 1){
numOfBian++;
}
}
}
numOfBian /= 2;
//cout << numOfBian;
memset(print, 0, sizeof(print));
memset(visited, 0, sizeof(visited));
if (visit(n, 0, 0)){
cout << "回路路径为" << endl;
for (i=0; i<=numOfBian; i++){
if (i == 0)
cout << print[i];
else
cout << "->" << print[i];
}
cout << endl;
}
}
void findHalfEuler(int n){//搜索欧拉路（非欧拉回路的欧拉路）
numOfBian = 0;
for (int i=0; i<n; i++){
for (int j=0; j<n; j++){
if (P[i][j] == 1){
numOfBian++;
}
}
}
numOfBian /= 2;
//cout << numOfBian;
memset(print, 0, sizeof(print));
memset(visited, 0, sizeof(visited));
if (visitHalf(n, 0, 0)){
cout << "路路径为" << endl;
int c = 0;
for (i=0; i<=numOfBian; i++){
for (i=0; i<=numOfBian; i++){
if (i == 0)
cout << print[i];
else
cout << "->" << print[i];
}
cout << endl;
}
}
}
int main(){
int n;
srand(time(NULL));
cout << "请输入节点个数";
cin >> n;
createP(n);
printP(n);
int res = 0;
if (isLianTong(n)){
res = judge(n);
} else
cout << "不连通" << endl;
if (res == 1)
findEuler(n);
if (res == 2)
findHalfEuler(n);
return 0;
}其实第二个程序我不确定正确，我只用过有限的几个测试用例，如果要测试的话，得改一下生成邻接矩阵的函数。
突然发现，数据结构算法这些东西好有趣～
版权声明：本文为u012427462原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。