#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAX 20
#define OK 1
constexpr auto ERROR = 0;
typedef char Elemtype;
typedef struct {
Elemtype data[MAX];
int top;
}Stack;
typedef struct {
char ch[MAX];
char vaule[MAX];
}Val;
typedef struct Stack_num
{
int num;
struct Stack_num* next;
}Stack_num, * LinkStack_num_ptr;
typedef struct LinkStack_num
{
struct Stack_num* top;
int count;
}LinkStack_num;
typedef struct Stack_opt
{
char opt;
struct Stack_opt* next;
}Stack_opt, * LinkStack_opt_ptr;
typedef struct LinkStack_opt
{
struct Stack_opt* top;
int count;
}LinkStack_opt;
bool Push_num(LinkStack_num* S, int e)
{
LinkStack_num_ptr s = (LinkStack_num_ptr)malloc(sizeof(Stack_num));
s->num = e;
s->next = S->top;
S->top = s;
S->count++;
return OK;
}
bool Pop_num(LinkStack_num* S, int* e)
{
LinkStack_num_ptr p;
if (S->top == NULL)
{
return ERROR;
}
*e = S->top->num;
p = S->top;
S->top = S->top->next;
free(p);
S->count--;
return OK;
}
bool Push_opt(LinkStack_opt* S, char e)
{
LinkStack_opt_ptr s = (LinkStack_opt_ptr)malloc(sizeof(Stack_opt));
s->opt = e;
s->next = S->top;
S->top = s;
S->count++;
return OK;
}
bool Pop_opt(LinkStack_opt* S, char* e)
{
LinkStack_opt_ptr p;
if (S->top == NULL)
{
return ERROR;
}
*e = S->top->opt;
p = S->top;
S->top = S->top->next;
free(p);
S->count--;
return OK;
}
int Priority(char ch)
{
switch (ch)
{
case '(':
return 3;
case '*':
case '/':
return 2;
default:
return 0;
}
}
//获取几元表达式
int numofstr(char e[], int length) {
int num = 0;
int j = 0;
for (int i = 0; i < length; i++) {
if (e[i] > 'A' && e[i] < 'Z') {
for (j = 0; j < i; j++) {
if (e[j] == e[i]) {
break;
}
}
if (i == j) num++;
}
}
return num;
}
//根据二进制，改变val的值，000，001，010，011。。。
Val* getcal(int num, Val* val,int z) {
for (int i = 0; i < num; i++) {
val->vaule[i] = z % 2 + '0';
z /= 2;
}
return val;
}
//将表达式转换为0 1表达式
Val* getVal(char e[], int length, char temp[],int num,int z) {
Val* val = (Val*)malloc(sizeof(Val));
int j = 0, n = 0;
for (int i = 0; i < num; i++) {
val->vaule[i] = '0';//﹍て
}
getcal(num, val, z);
for (int i = 0; i < length; i++) {
temp[i] = e[i];
}
for (int i = 0; i < length; i++) {
if (e[i] > 'A' && e[i] < 'Z') {
for (j = 0; j < i; j++) {
if (e[j] == e[i]) {
break;
}
}
if (i == j) val->ch[n++] = e[i];
}
}
for (int i = 0; i < num; i++) {
for (int j = 0; j < length; j++) {
if (val->ch[i] == e[j]) {
temp[j] = val->vaule[i];
}
}
}
return val;
}
void print1(char e[], int length) {
for (int i = 0; i < length; i++) {
printf("%c ", e[i]);
}
}
//计算 0 1表达式
int cal(char opt[],int length) {
LinkStack_num* stack_num = (LinkStack_num*)malloc(sizeo/f(LinkStack_num));
LinkStack_opt* stack_opt = (LinkStack_opt*)malloc(sizeof(LinkStack_opt));
stack_num->top = NULL;
stack_num->count = 0;
stack_opt->top = NULL;
stack_opt->count = 0;
int i = 0, tmp = 0;
char option;
int num1, num2;
while (opt[i] != '\0' || stack_opt->top != NULL)
{
if (opt[i] == '1'||opt[i]=='0')
{
Push_num(stack_num, opt[i]-'0');
i++;
}
else
{
if (stack_opt->top == NULL || (stack_opt->top->opt == '(' && opt[i] != ')') || Priority(opt[i]) > Priority(stack_opt->top->opt))
{
Push_opt(stack_opt, opt[i]);
i++;
continue;
}
if (stack_opt->top->opt == '(' && opt[i] == ')')
{
char temp;
Pop_opt(stack_opt, &temp);
i++;
continue;
}
if ((opt[i] == '\0' && stack_opt->top != NULL) || opt[i] == ')' && stack_opt->top->opt != '(' || Priority(opt[i]) <= Priority(stack_opt->top->opt))
{
Pop_opt(stack_opt, &option);
switch (option)
{
case '|':
{
int sum = 0;
Pop_num(stack_num, &num1);
Pop_num(stack_num, &num2);
sum = num1 + num2;
if (sum == 2) sum = 1;
Push_num(stack_num, sum);
break;
}
case '!':
{
Pop_num(stack_num, &num1);
if (num1 == 0) num1 = 1;
else num1 = 0;
Push_num(stack_num, num1);
break;
}
case '&':
{
Pop_num(stack_num, &num1);
Pop_num(stack_num, &num2);
Push_num(stack_num, (num1 * num2));
break;
}
}
}
}
}
return stack_num->top->num;
}
//控制循环次数，2^n
int number(int num) {
int sum = 1;
for (int i = 0; i < num; i++) {
sum = sum * 2;
}
return sum;
}
//主析取范式中的一个值
void xiqu(Val* val,int num) {
int j = 0;
printf("(");
for (int i = 0; i < num; i++) {
if (val->vaule[i]== 1+'0') {
//e[j++] = val->ch[i];
if(i!=num-1) printf("%c&", val->ch[i]);
else printf("%c", val->ch[i]);
}
else {
//e[j++] = '!';
//e[j++] = val->ch[i];
if (i != num - 1) printf("!%c&", val->ch[i]);
else printf("!%c", val->ch[i]);
}
}
printf(")");
}
//主合取范式中的一个值
void hequ(Val* val, int num) {
int j = 0;
printf("(");
for (int i = 0; i < num; i++) {
if (val->vaule[i] == 1 + '0') {
//e[j++] = val->ch[i];
if (i != num - 1) printf("%c|", val->ch[i]);
else printf("%c", val->ch[i]);
}
else {
//e[j++] = '!';
//e[j++] = val->ch[i];
if (i != num - 1) printf("!%c|", val->ch[i]);
else printf("!%c", val->ch[i]);
}
}
printf(")");
}
int main()
{
//输入规则
printf("“|”表示析取，“&表示合取”，“！”表示否定,“( )”和括号。\n");
printf("输入任意长度的表达式，得到真值表和主析取范式和主合取范式。\n");
printf("有否定请把否定元加上括号,括号使用半角括号，例如：(!P)\n");
printf("表达式中不要出现空格，例如:Q|P&(Q|Y)|(!P)\n");
printf("不满足单条件和双条件，以后优化。。。\n");
char str[MAX];
char temp[MAX];
Val* val;
int length = 0;
int num = 0;
printf("\n input the str:\n");
scanf("%s", str);
length = strlen(str);
num = numofstr(str, MAX);
printf("%d", num);
printf("\n-------真值表--------\n");
for (int i = 0; i < number(num); i++) {//真值表
getVal(str, length, temp, num, i);
print1(temp, length);
int sum = cal(temp, length);
printf(" %d \n\n", sum);
}
printf("\n主析取范式：\n");
for (int i = 0; i < number(num); i++) {//主析取
val=getVal(str, length, temp, num, i);
int sum = cal(temp, length);
if (sum == 1) {
xiqu(val,num);
printf("|");
}
}
printf("\n主合取范式：\n");
for (int i = 0; i < number(num); i++) {//主合取
val = getVal(str, length, temp, num, i);
int sum = cal(temp, length);
if (sum == 0) {
hequ(val, num);
printf("&");
}
}
}
