要求：已知某种类型的布尔表达式由“V”、“F”、“！”、“&”和“|”组成，其中，“V”代表真值True，“F”代表真值False，“！”代表逻辑非运算，“&”代表逻辑或运算。并且，运算符“！”、“&”和“|”的优先级为：“！”最高，“|”最低，“&”介于“！”和“|”之间。你的任务是，计算给定布尔表达式的真值。
例如，布尔表达式“(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] = { // 运算符优先级表 // '~' '&' '|' '>' '(' ')' '#' /*'~'*/'>','>','>','>','>','<','>','>', /*'&'*/'<','>','>','>','>','<','>','>', /*'|'*/'<','<','>','>','>','<','>','>', /*'>'*/'<','<','<','>','>','<','>','>', /*'='*/'<','<','<','<','>','<','>','>', /*'('*/'<','<','<','<','<','<','=','>', /*')'*/'>','>','>','>','>',' ','>','>', /*'#'*/'<','<','<','<','<','<',' ','=' }; //实现两个变元的逻辑运算功能: 非, 合取, 析取, 蕴含, 等价 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; } //对于给定的命题公式, 能够计算其真值 typedef struct Character { char c; struct Character *next; }Ch, *ch; //Character类型的结点Ch typedef struct Char { char f; struct Char *next; }Fl, *fl; //Float类型的结点Fl ch Push(ch s, char c) //Ch类型的指针函数Push，返回p { ch p = (ch)malloc(sizeof(Ch)); //创建新的结点指针 p->c = c; p->next = s; return p; } fl Push(fl s, char f) { //Fl类型的指针Push，返回p fl p = (fl)malloc(sizeof(Fl)); //创建新的结点指针 p->f = f; p->next = s; return p; } ch Pop(ch s) { //SC类型的指针Pop ch q = s; s = s->next; free(q); //删除结点指针 return s; } fl Pop(fl s) { //SF类型的指针Pop fl q = s; s = s->next; free(q); //删除结点指针 return s; } bool Operation(char a, unsigned char c, char b) //计算函数Operate { switch (c) //对输入的运算符进行判别运算 { 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) //计算函数Operate { return fei(a); } char A[Size] = { '~','&','|','>','=','(',')','#' }; //运算符数组 bool Existence(char c, char *A) { bool Find = false; for (int i = 0; i< Size; i++) { if (c == A[i]) //判断输入的字符是否在运算符数组中 Find = true; //存在则返回true } return Find; } int Locate(char c, char *A) { //返回输入的字符在运算符数组里的位置 for (int i = 0; i< Size; i++) { if (c == A[i]) return i; } } char Superior(char c, char d) { //返回两个字符的运算优先级 return Super[Locate(c, A)][Locate(d, A)]; //其中数组A也就是运算字符数组是全局变量 } float Evaluate(char* Expression) { // 算术表达式求值的算符优先算法 // 设OPTR和OPND分别为运算符栈和运算数栈，OP为运算符集合 ch P = NULL; // 运算符栈，字符元素 fl Q = NULL; // 运算数栈，实数元素 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 { //不是运算符则进栈 switch (Superior(P->c, *c)) { case '<': // 栈顶元素优先级低 P = Push(P, *c); c++; break; case '=': // 脱括号并接收下一字符 P = Pop(P); c++; break; case '>': // 退栈并将运算结果入栈 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("请输入表达式:"); 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; }
