WHCSRL 技术网

利用真值表法求取主析取范式以及主合取范式的实现(C++)_m0

代码如下:

#include <iostream>
#include <stack>
#include <string>
#include <vector>
using namespace std;
const int N = 300;
stack<char> s;
stack<char> v;
int seq;
bool vis[N];
bool flag[N];
void dfs(int n);
vector<int> ans_v;
vector<int> ans_vf;


void printMenu()
{
	cout << "代码其实有点不健壮,需要用括号来手动处理优先级!" << endl;
	cout << "比如:!!!(a&b&c)  要写成!(!(!(a&b&c)))" << endl;
	cout << "比如:!(a&b)->c 要写成 (!(a&b))>c" << endl;
	cout << "合取& 析取| 非! 条件> 双条件~ 括号() " << endl;
	cout << endl;
}

void printAns(vector<int> &ans_v, char f, char v)
{
	for (int i = 0; i < ans_v.size(); i++)
	{
		cout << f << ans_v[i];
		if (i != ans_v.size() - 1)
		{
			cout << v;
		}
	}
	cout << endl;
}




void calculator(int n, string &str)
{
	str = '(' + str + ')';
	for (int i = 0; i < str.length(); i++)
	{
		char tmp = str[i];

		if (tmp >= 'a' && tmp <= 'z')
		{
			vis[tmp - 'a'] = true;
			s.push(tmp);
		}
		else if (tmp == '(')
		{
			v.push(tmp);
		}
		else if (tmp == ')')
		{
			while (v.top() != '(')
			{
				s.push(v.top());
				v.pop();
			}
			v.pop();
		}
		else
		{
			v.push(tmp);
		}
	}




	stack<char>t;
	while (!s.empty())
	{
		t.push(s.top());
		s.pop();
	}
	s = t;


	stack<char>h(s);
	while (!h.empty())
	{
		cout << h.top();
		h.pop();
	}
	cout << endl;

	dfs(0);
	cout << "主合取范式为:" << endl;
	printAns(ans_v, 'm', '&');
	cout << "主析取范式为:" << endl;
	printAns(ans_vf, 'M', '|');


}




void dfs(int n)
{
	if (n == 26)
	{

		stack<char> s_s(s);
		stack<bool> s_t;
		while (!s_s.empty())
		{
			if (s_s.top() == '&' || s_s.top() == '|' || s_s.top() == '~' || s_s.top() == '>')
			{
				if (s_s.top() == '&')
				{
					s_s.pop();
					bool a2 = s_t.top();
					s_t.pop();
					bool a1 = s_t.top();
					s_t.pop();
					bool ans = a2 && a1;
					s_t.push(ans);
				}
				else if (s_s.top() == '|')
				{
					s_s.pop();
					bool a2 = s_t.top();
					s_t.pop();
					bool a1 = s_t.top();
					s_t.pop();
					bool ans = a2 || a1;
					s_t.push(ans);
				}
				else if (s_s.top() == '>')
				{
					s_s.pop();
					bool a2 = s_t.top();
					s_t.pop();
					bool a1 = s_t.top();
					s_t.pop();
					if (a1 == true && a2 == true)
					{
						s_t.push(true);
					}
					else if (a1 == true && a2 == false)
					{
						s_t.push(false);
					}
					else if (a1 == false)
					{
						s_t.push(true);
					}
				}
				else if (s_s.top() == '~')
				{
					s_s.pop();
					bool a2 = s_t.top();
					s_t.pop();
					bool a1 = s_t.top();
					s_t.pop();
					if (a1 == a2)
					{
						s_t.push(true);
					}
					else s_t.push(false);
				}
			}
			else if (s_s.top() == '!')
			{
				s_s.pop();
				bool tmp = !s_t.top();
				s_t.pop();
				s_t.push(tmp);
			}
			else
			{
				s_t.push(flag[s_s.top() - 'a']);
				s_s.pop();
			}

		}

		for (int i = 0; i < 26; i++)
		{
			if (vis[i])
			{
				cout << char(i + 'a') << "=" << flag[i] << " ";
			}
		}



		if (s_t.top())
		{

			ans_v.push_back(seq);
			cout << "ans=true" << endl;
		}
		else
		{
			ans_vf.push_back(seq);
			cout << "ans=false" << endl;
		}
		seq++;

		return;

	}

	if (vis[n])
	{
		for (int i = 0; i <= 1; i++)
		{
			flag[n] = i;
			dfs(n + 1);
		}
	}
	else
	{
		dfs(n + 1);
	}


}




int main()
{
	int n;
	string str;
	printMenu();
	cout << "请先输入式子含有的变量个数" << endl;
	cin >> n;
	cout << "按格式输入式子" << endl;
	cin >> str;
	calculator(n, str);
	return 0;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138
  • 139
  • 140
  • 141
  • 142
  • 143
  • 144
  • 145
  • 146
  • 147
  • 148
  • 149
  • 150
  • 151
  • 152
  • 153
  • 154
  • 155
  • 156
  • 157
  • 158
  • 159
  • 160
  • 161
  • 162
  • 163
  • 164
  • 165
  • 166
  • 167
  • 168
  • 169
  • 170
  • 171
  • 172
  • 173
  • 174
  • 175
  • 176
  • 177
  • 178
  • 179
  • 180
  • 181
  • 182
  • 183
  • 184
  • 185
  • 186
  • 187
  • 188
  • 189
  • 190
  • 191
  • 192
  • 193
  • 194
  • 195
  • 196
  • 197
  • 198
  • 199
  • 200
  • 201
  • 202
  • 203
  • 204
  • 205
  • 206
  • 207
  • 208
  • 209
  • 210
  • 211
  • 212
  • 213
  • 214
  • 215
  • 216
  • 217
  • 218
  • 219
  • 220
  • 221
  • 222
  • 223
  • 224
  • 225
  • 226
  • 227
  • 228
  • 229
  • 230
  • 231
  • 232
  • 233
  • 234
  • 235
  • 236
  • 237
  • 238
  • 239
  • 240
  • 241
  • 242

运行示例:

在这里插入图片描述

推荐阅读