要求：已知某種類型的布爾表達(dá)式由“V”愕把、“F”、“森爽！”恨豁、“&”和“|”組成，其中爬迟，“V”代表真值True橘蜜，“F”代表真值False，“！”代表邏輯非運(yùn)算计福，“&”代表邏輯或運(yùn)算跌捆。并且，運(yùn)算符“象颖！”佩厚、“&”和“|”的優(yōu)先級(jí)為：“！”最高说订，“|”最低抄瓦，“&”介于“！”和“|”之間陶冷。你的任務(wù)是闺鲸，計(jì)算給定布爾表達(dá)式的真值。交流群728483370埃叭，一起學(xué)習(xí)加油摸恍！
例如，布爾表達(dá)式“(V|V)&F&(F|V)”的真值為“F”.
#include<iostream>
#include<string.h>
#include<malloc.h>
#include<math.h>
#include<typeinfo>
#define Size 8
#include <cstdlib>
using namespace std;
unsigned char Super[8][8] =
{ // 運(yùn)算符優(yōu)先級(jí)表
// '~' '&' '|' '>' '(' ')' '#'
/*'~'*/'>','>','>','>','>','<','>','>',
/*'&'*/'<','>','>','>','>','<','>','>',
/*'|'*/'<','<','>','>','>','<','>','>',
/*'>'*/'<','<','<','>','>','<','>','>',
/*'='*/'<','<','<','<','>','<','>','>',
/*'('*/'<','<','<','<','<','<','=','>',
/*')'*/'>','>','>','>','>',' ','>','>',
/*'#'*/'<','<','<','<','<','<',' ','='
};
//實(shí)現(xiàn)兩個(gè)變?cè)倪壿嬤\(yùn)算功能: 非, 合取, 析取, 蘊(yùn)含, 等價(jià)
bool fei(char a) {
if (a == 'V')
return false;
else return true;
}
bool hequ(char a,char b) {
bool m = (a == 'V') ? true : false;
bool n = (b == 'V') ? true : false;
return m&n;
}
bool xiqu(char a,char b) {
bool m = (a == 'V') ? true : false;
bool n = (b == 'V') ? true : false;
return m | n;
}
bool yunhan(char a,char b) {
bool m = (a == 'V') ? true : false;
bool n = (b == 'V') ? true : false;
return (m ^ 0x1) | b;
}
bool dengjia(char a,char b) {
bool m = (a == 'V') ? true : false;
bool n = (b == 'V') ? true : false;
return (m^n) ^ 0x1;
}
//對(duì)于給定的命題公式, 能夠計(jì)算其真值
typedef struct Character
{
char c;
struct Character *next;
}Ch, *ch;
//Character類型的結(jié)點(diǎn)Ch
typedef struct Char
{
char f;
struct Char *next;
}Fl, *fl;
//Float類型的結(jié)點(diǎn)Fl
ch Push(ch s, char c) //Ch類型的指針函數(shù)Push赤屋，返回p
{
ch p = (ch)malloc(sizeof(Ch)); //創(chuàng)建新的結(jié)點(diǎn)指針
p->c = c;
p->next = s;
return p;
}
fl Push(fl s, char f) { //Fl類型的指針Push立镶，返回p
fl p = (fl)malloc(sizeof(Fl)); //創(chuàng)建新的結(jié)點(diǎn)指針
p->f = f;
p->next = s;
return p;
}
ch Pop(ch s) { //SC類型的指針Pop
ch q = s;
s = s->next;
free(q); //刪除結(jié)點(diǎn)指針
return s;
}
fl Pop(fl s) { //SF類型的指針Pop
fl q = s;
s = s->next;
free(q); //刪除結(jié)點(diǎn)指針
return s;
}
bool Operation(char a, unsigned char c, char b) //計(jì)算函數(shù)Operate
{
switch (c) //對(duì)輸入的運(yùn)算符進(jìn)行判別運(yùn)算
{
case '&': return hequ(a, b); break;
case '|': return xiqu(a, b); break;
case '>': return yunhan(a, b); break;
case '=': return dengjia(a, b); break;
default: return 0;
}
}
bool Operation1(char a, unsigned char c) //計(jì)算函數(shù)Operate
{
return fei(a);
}
char A[Size] = { '~','&','|','>','=','(',')','#' }; //運(yùn)算符數(shù)組
bool Existence(char c, char *A)
{
bool Find = false;
for (int i = 0; i< Size; i++)
{
if (c == A[i]) //判斷輸入的字符是否在運(yùn)算符數(shù)組中
Find = true; //存在則返回true
}
return Find;
}
int Locate(char c, char *A) { //返回輸入的字符在運(yùn)算符數(shù)組里的位置
for (int i = 0; i< Size; i++) {
if (c == A[i])
return i;
}
}
char Superior(char c, char d) { //返回兩個(gè)字符的運(yùn)算優(yōu)先級(jí)
return Super[Locate(c, A)][Locate(d, A)]; //其中數(shù)組A也就是運(yùn)算字符數(shù)組是全局變量
}
float Evaluate(char* Expression) {
// 算術(shù)表達(dá)式求值的算符優(yōu)先算法
// 設(shè)OPTR和OPND分別為運(yùn)算符棧和運(yùn)算數(shù)棧，OP為運(yùn)算符集合
ch P = NULL; // 運(yùn)算符棧类早，字符元素
fl Q = NULL; // 運(yùn)算數(shù)棧媚媒，實(shí)數(shù)元素
char a, b;
char d, *c, Two[] = { '#','\0' };
P = Push(P, '#');
c = strcat(Expression, Two);
while (*c != '#' || P->c != '#') {
if (!Existence(*c, A)) {
Q = Push(Q, *c);
c++;
}
else { //不是運(yùn)算符則進(jìn)棧
switch (Superior(P->c, *c)) {
case '<': // 棧頂元素優(yōu)先級(jí)低
P = Push(P, *c);
c++;
break;
case '=': // 脫括號(hào)并接收下一字符
P = Pop(P);
c++;
break;
case '>': // 退棧并將運(yùn)算結(jié)果入棧
d = P->c; P = Pop(P);
if (d == '~') {
a = Q->f; Q = Pop(Q);
Q = Push(Q, Operation1(a, d));
}
else {
b = Q->f; Q = Pop(Q);
a = Q->f; Q = Pop(Q);
Q = Push(Q, Operation(a, d, b));
}
break;
} //switch
}
} //while
return Q->f;
} //Evaluate
int main(void) {
char s[128];
puts("請(qǐng)輸入表達(dá)式:");
gets(s);
cout << s << "的真值為:";
// cout<<typeid(Evaluate(s)).name()<<endl;
if(Evaluate(s)==1) {
cout<<"V"<<endl;
} else {
cout<<"F"<<endl;
}
system("pause");
return 0;
}
