题目链接：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))

样例输出

FVV

分析：（来源：http://blog.csdn.net/INCINCIBLE/article/details/51151222?locationNum=5&fps=1）

原理很简单，将中缀表达式转化为前缀表达式在计算，只是代码实现比较麻烦。

中缀转前缀的步骤如下：

(1) 首先构造一个运算符栈(也可放置括号)，运算符(以括号分界点)在栈内遵循越往栈顶优先级不降低的原则进行排列。

(2)从右至左扫描中缀表达式，从右边第一个字符开始判断：

如果当前字符是数字，则分析到数字串的结尾并将数字串直接输出。

如果是运算符，则比较优先级。如果当前运算符的优先级大于等于栈顶运算符的优先级(当栈顶是括号时，直接入栈)，则将运算符直接入栈；否则将栈顶运算符出栈并输出，直到当前运算符的优先级大于等于栈顶运算符的优先级(当栈顶是括号时，直接入栈)，再将当前运算符入栈。

如果是括号，则根据括号的方向进行处理。如果是右括号，则直接入栈；否则，遇左括号前将所有的运算符全部出栈并输出，遇右括号后将左右的两括号一起删除。

(3) 重复上述操作(2)直至扫描结束，将栈内剩余运算符全部出栈并输出，再逆缀输出字符串。中缀表达式也就转换为前缀表达式了。

 

右括号有最高的优先级，左括号优先级最低。

代码：

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            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
           
             Oper,num; //oper保存运算符，num保存运算结果 28 queue
            
              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 else41 {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<
             
              <
             
            
           
          
         
        
       
      
     

 

另外，可以参考http://www.ithao123.cn/content-10400535.html

 第二种思路，递归求解。

代码来源：北大郭炜老师MOOC课程的代码。可以参考这篇文章的分析。

1 #include 
     
        2 #include 
      
         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 }