- 题目链接：http://noi.openjudge.cn/ch0303/6263/
- 总时间限制: 1000ms 内存限制: 65536kB
- 描述
-
输入一个布尔表达式，请你输出它的真假值。 比如：( V | V ) & F & ( F | V )
V表示true，F表示false，&表示与，|表示或，!表示非。
上式的结果是F - 输入
- 输入包含多行，每行一个布尔表达式，表达式中可以有空格，总长度不超过1000
- 输出
- 对每行输入，如果表达式为真，输出"V",否则出来"F"
- 样例输入
-
( V | V ) & F & ( F| V) !V | V & V & !F & (F | V ) & (!F | F | !V & V) (F&F|V|!V&!F&!(F|F&V))
- 样例输出
-
F V V
分析：（来源：http://blog.csdn.net/INCINCIBLE/article/details/51151222?locationNum=5&fps=1）
原理很简单，将中缀表达式转化为前缀表达式在计算，只是代码实现比较麻烦。
中缀转前缀的步骤如下：
(1) 首先构造一个运算符栈(也可放置括号)，运算符(以括号分界点)在栈内遵循越往栈顶优先级不降低的原则进行排列。
(2)从右至左扫描中缀表达式，从右边第一个字符开始判断：
如果当前字符是数字，则分析到数字串的结尾并将数字串直接输出。
如果是运算符，则比较优先级。如果当前运算符的优先级大于等于栈顶运算符的优先级(当栈顶是括号时，直接入栈)，则将运算符直接入栈；否则将栈顶运算符出栈并输出，直到当前运算符的优先级大于等于栈顶运算符的优先级(当栈顶是括号时，直接入栈)，再将当前运算符入栈。
如果是括号，则根据括号的方向进行处理。如果是右括号，则直接入栈；否则，遇左括号前将所有的运算符全部出栈并输出，遇右括号后将左右的两括号一起删除。
(3) 重复上述操作(2)直至扫描结束，将栈内剩余运算符全部出栈并输出，再逆缀输出字符串。中缀表达式也就转换为前缀表达式了。
右括号有最高的优先级，左括号优先级最低。
代码：
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<queue> 5 #include<stack> 6 #include<cstring> 7 using namespace std; 8 char calculate(char x, char y,char oper )// 计算 x oper y 9 { 10 bool a=(x=='V'),b=(y=='V'),ans; 11 if(oper=='|') ans=(a||b); 12 else if(oper=='&') ans=(a&&b); 13 return ans?'V':'F'; 14 } 15 char reverse(char x) //将逻辑值取反。其实就是‘！’运算符 16 { 17 if(x=='V')return 'F'; 18 return 'V'; 19 } 20 int main() 21 { 22 string in; 23 int i,j,len; 24 25 while(getline(cin,in)) 26 { 27 stack<char> Oper,num; //oper保存运算符，num保存运算结果 28 queue<char> s; //s就是前缀表达式 29 len=in.length(); 30 i=len; 31 in=" "+in; 32 while(i>0)// 从右往左，中缀表达式转前缀表达式 33 { 34 if(in[i]==' ') 35 { 36 i--;continue; 37 } 38 else if(isalpha(in[i])) s.push(in[i--]);//isalpha()函数：如果参数是字母字符，函数返回非零值，否则返回零值 39 else if(in[i]=='!') s.push(in[i--]); //最高级的运算，直接进入表达式(这里主要是因为！运算符是单目运算符) 40 else 41 { 42 if(in[i]=='&'||in[i]=='|'||in[i]==')') //低级运算，进栈 43 Oper.push(in[i--]); 44 else if(in[i]=='(') //一个括号结束，弹出中间的所有运算符 45 { 46 while(Oper.top()!=')') 47 { 48 s.push(Oper.top()); 49 Oper.pop(); 50 } 51 Oper.pop(); 52 i--; 53 } 54 } 55 } 56 while(!Oper.empty()) //栈中剩下的运算符 57 s.push(Oper.top()),Oper.pop(); 58 59 while(!s.empty()) //计算前缀表达式 60 { 61 char ch=s.front(); s.pop(); 62 if(isalpha(ch)) num.push(ch); 63 else Oper.push(ch); 64 if(!num.empty()&&!Oper.empty()&&Oper.top()=='!') //单目运算符‘！’； 65 { 66 char x=num.top(); 67 num.pop();Oper.pop(); 68 num.push(reverse(x)); 69 } 70 else if(num.size()>=2&&!Oper.empty()) //双目运算符 71 { 72 char oper=Oper.top(),x,y; 73 Oper.pop(); 74 x=num.top();num.pop(); 75 y=num.top();num.pop(); 76 num.push(calculate(x,y,oper)); 77 } 78 } 79 cout<<num.top()<<endl; 80 } 81 }
另外，可以参考http://www.ithao123.cn/content-10400535.html
第二种思路，递归求解。
代码来源：北大郭炜老师MOOC课程的代码。可以参考中缀表达式计算这篇文章的分析。
1 #include <iostream> 2 #include <cstdio> 3 using namespace std; 4 5 char wholeExp[1500];//表示整个表达式的字符串 6 int ptr = 0; 7 8 bool exp();//读入一个表达式并返回其值 9 bool item();//读入一个项并返回其值 10 bool factor();//读入一个因子并返回其值 11 bool notExp();//将表达式取反的操作 12 /* 13 表达式：由单独的"项"或者"项"与"|"运算符连接形成； 14 项：由单独的"因子"或"因子"和&运算符连接而成； 15 因子：可以是单独的V或F，也可以是用括号括起来的"表达式"。 16 */ 17 int main() 18 { 19 freopen("6263.in","r",stdin); 20 int t = 1;//表示第t个测试样例 21 char c; 22 int i = 0; 23 int n = EOF + 1; 24 while(n != EOF) 25 { 26 n = scanf("%c",&c); 27 if( n == EOF || c == '\n') 28 { 29 wholeExp[i] = '\0'; 30 if( i > 0) 31 { 32 ptr = 0; 33 bool res = exp(); 34 if (res) { printf("Expression %d: V\n",t++); } 35 else printf("Expression %d: F\n",t++); 36 /*if (res) { printf("V\n",t++); } 37 else printf("F\n",t++);*/ 38 } 39 i = 0; 40 } 41 else if( c != ' ') wholeExp[i++] = c; 42 } 43 return 0; 44 } 45 46 bool exp() //读入一个表达式并返回其值 47 { 48 bool result = item(); 49 while(wholeExp[ptr] == '|' ) 50 { 51 ++ptr; 52 result = result | item();//注意：这里的或运算不能用C语言逻辑或运算符，因为逻辑或运算符在编译器处理完以后有短路特性，可能会忽略后面的输入。比如(V|V)&F，若是用逻辑或，可能只扫描到第一个V就返回逻辑真，不再继续往后扫描了。但是其实应该是逻辑假。 53 } 54 return result; 55 } 56 57 bool item() //读入一个项并返回其值 58 { 59 bool result = factor(); 60 while(wholeExp[ptr] == '&') 61 { 62 ++ptr; 63 result = result & factor();//同样地，这个地方不能用逻辑与运算符，否则会错忽略后面应该扫描的东西从而返回错误的结果。比如(F&V)|V。 64 } 65 return result; 66 } 67 68 bool factor() //读入一个因子并返回其值 69 { 70 bool result; 71 switch( wholeExp[ptr]) 72 { 73 case 'F': 74 ++ptr; 75 return false; 76 break; 77 case 'V': 78 ++ptr; 79 return true; 80 break; 81 case '(': 82 ++ptr; 83 result = exp(); 84 ++ptr; //skip ')' 85 return result; 86 break; 87 case '!': 88 result = notExp(); 89 return result; 90 break; 91 } 92 } 93 94 bool notExp() //将表达式取反的操作 95 { 96 //wholeExp[ptr] == '!' when called; 97 ptr++; 98 bool result; 99 switch(wholeExp[ptr]) 100 { 101 case 'F': 102 ++ptr; 103 return true; 104 break; 105 case 'V': 106 ++ptr; 107 return false; 108 break; 109 case '(': 110 ++ptr; 111 result = exp(); 112 ++ptr; //skip ')' 113 return !result; 114 break; 115 case '!': 116 result = notExp(); 117 return !result; 118 break; 119 } 120 }
