典型的表达式求值问题
栈来解决表达式问题，构建两个栈，一个是运算数栈，一个是运算符栈。
这篇题解应该是这道题里最麻烦的题解了，没有之一
题目链接：POJ 2106
| Describe: |
| The objective of the program you are going to produce is to evaluate boolean expressions as the one shown next: where V is for True, and F is for False. The expressions may include the following operators: ! for not , & for and, | for or , the use of parenthesis for operations grouping is also allowed. To perform the evaluation of an expression, it will be considered the priority of the operators, the not having the highest, and the or the lowest. The program must yield V or F , as the result for each expression in the input file. |
| Input: |
| The expressions are of a variable length, although will never exceed 100 symbols. Symbols may be separated by any number of spaces or no spaces at all, therefore, the total length of an expression, as a number of characters, is unknown. The number of expressions in the input file is variable and will never be greater than 20. Each expression is presented in a new line, as shown below. |
| Output: |
| For each test expression, print "Expression " followed by its sequence number, ": ", and the resulting value of the corresponding test expression. Separate the output for consecutive test expressions with a new line. Use the same format as that shown in the sample output shown below. |
| Sample Input: |
| ( V | V ) & F & ( F| V) !V | V & V & !F & (F | V ) & (!F | F | !V & V) (F&F|V|!V&!F&!(F|F&V)) |
| Sample Output: |
| Expression 1: F Expression 2: V Expression 3: V |
题目大意：
多个样例，每行一个布尔算式，要求给出每个算式的答案，F是0，V是1，运算符有& ! | ( )这五个，优先级为! > & > |当然有括号肯定先算括号里的，中间会有若干空格。
解题思路：
用了120+行（没有注释情况下）的代码A了此题，代码重复率太高了，想写个函数，但是不太会在c++里如何把stack当作参数来传，写的也比较仓促，可能不是那么好看，唯一的优点可能就是思路简单点吧。
思路：
分析字符串里每个字符，如果是V或者F，则数据栈入栈1或者0，如果是运算符，若堆栈（运算符栈）为空，则直接入栈，否则，将栈顶中优先级不小于它的运算符都出栈计算，每出栈一个运算符，就弹出相应个数的运算数，然后结果再入栈，最后再把那个读入的运算符入栈。直至运算符栈为空，最终数据栈栈顶元素即为答案。
AC代码：
1 #include <cstdio> 2 #include <iostream> 3 #include <stack> 4 using namespace std; 5 int cnt = 1; // 输出用的 6 int main() 7 { 8 char c; // 虽然是字符串，但还是老老实实用字符读入吧 9 while(~scanf("%c",&c)) 10 { 11 stack<int> n; 12 stack<int> p; 13 switch(c) // 注意了，读入的第一个字符别忘了判断并入栈 14 { 15 case ‘(‘:p.push(0);break; // 用数字代表字符了，反正也就5种 16 case ‘!‘:p.push(3);break; 17 case ‘&‘:p.push(2);break; 18 case ‘|‘:p.push(1);break; 19 case ‘F‘:n.push(0);break; 20 case ‘V‘:n.push(1);break; 21 } 22 while(~scanf("%c",&c)) 23 { 24 if(c == ‘ ‘) continue; 25 if(c == ‘\n‘) break; // 这个也很重要，不然一直循环 26 if(c == ‘V‘ || c == ‘F‘) // 运算数入栈 27 { 28 n.push(c==‘V‘?1:0); 29 continue; 30 } 31 if(c == ‘(‘) { 32 p.push(0); 33 } else if(c == ‘!‘) { 34 p.push(3); 35 } else if(c == ‘&‘) { 36 if(p.empty()) {p.push(2); continue;} // 如果为空，直接入栈 37 while(!p.empty() && (p.top() == 3 || p.top() == 2)) // 否则找到优先级不小于它的 38 { 39 if(p.top() == 3) 40 { 41 int a = n.top(); 42 n.pop(); 43 n.push(a^1); 44 p.pop(); 45 } else if(p.top() == 2) { 46 int a = n.top(); n.pop(); 47 int b = n.top(); n.pop(); 48 n.push(a & b); 49 p.pop(); 50 } 51 } 52 p.push(2); 53 } else if(c == ‘|‘) { 54 if(p.empty()) {p.push(1); continue;} 55 while(!p.empty() && (p.top() == 2 || p.top() == 3 ||p.top() == 1)) 56 { 57 if(p.top() == 2) 58 { 59 int a = n.top(); n.pop(); 60 int b = n.top(); n.pop(); 61 n.push(a & b); 62 p.pop(); 63 } else if(p.top() == 3) { 64 int a = n.top(); n.pop(); 65 n.push(a^1); 66 p.pop(); 67 } else if(p.top() == 1) { 68 int a = n.top(); n.pop(); 69 int b = n.top(); n.pop(); 70 n.push(a | b); 71 p.pop(); 72 } 73 } 74 p.push(1); 75 } else if(c == ‘)‘) { 76 while(p.top() != 0) 77 { 78 if(p.top() == 1) 79 { 80 int a = n.top(); n.pop(); 81 int b = n.top(); n.pop(); 82 n.push(a | b); 83 p.pop(); 84 } else if(p.top() == 2) { 85 int a = n.top(); n.pop(); 86 int b = n.top(); n.pop(); 87 n.push(a & b); 88 p.pop(); 89 } else if(p.top() == 3) { 90 int a = n.top(); n.pop(); 91 n.push(a^1); 92 p.pop(); 93 } 94 } 95 if(p.top() == 0) p.pop(); 96 } 97 } 98 while(!p.empty()) // 输出答案前一定要判断看看是否算完了，也就是运算符栈是否为空 99 { // 不为空的话就算就完了 100 if(p.top() == 1) 101 { 102 int a = n.top(); n.pop(); 103 int b = n.top(); n.pop(); 104 n.push(a | b); 105 p.pop(); 106 } else if(p.top() == 2) { 107 int a = n.top(); n.pop(); 108 int b = n.top(); n.pop(); 109 n.push(a & b); 110 p.pop(); 111 } else if(p.top() == 3) { 112 int a = n.top(); n.pop(); 113 n.push(a^1); 114 p.pop(); 115 } 116 } 117 char ans = n.top()?‘V‘:‘F‘; 118 cout << "Expression " << cnt++ << ": " << ans << endl; // 输出，结束 119 } 120 return 0; 121 }
（太长了，我折叠起来了）
小结：
这种表达式求值，有优先级的，可以按照这种计算思路来写题。
POJ 2106 Boolean Expressions （最麻烦的题解）
原文：https://www.cnblogs.com/gblong10/p/13448189.html
