布尔表达式问题编程

老师在openjudge上布置了这个问题，这是我第二次做，还是调了很久。
#
布尔表达式 题目描述：

总时间限制: 1000ms 内存限制: 65536kB 描述输入一个布尔表达式，请你输出它的真假值。比如：( V | V ) &
F & ( F |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
##我的思路！

在读取数据时将所有空格去掉，方便后续操作
建立两个stack。一个命名为num用于存储bool值。另一个命名为mark用于存储符号。
首先要定义两种操作：且操作，或操作。分别是从num顶上弹出两个值，从mark上弹出一个符号（&/|），计算出的值重新压入num。
历遍字符串。在读到bool值时存入num；因为存在优先级！ > & > |, 和括号, 读到符号时需要分情况讨论：
- ’(‘,‘!’直接存入mark
- 读入其他任何符号，包括右括号，（由于优先级低于！）弹出’！’，并对num顶上的bool值取相反值,然后
  -如果是’&’, 压入mark
  -如果是’|’, （由于优先级高于’&’), 如果mark顶上有’&’，循环进行{且操作}，把’&‘消耗完。
  -如果是’）‘，那么根据mark顶的符号循环进行且操作/或操作，然后弹出’（‘，接着看mark顶部是不是’！‘，如果是要取相反值。
最后，如果mark内有符号，循环进行且操作/或操作（也有可能有’!‘操作），把符号消耗完，最后num中会剩下一个值。
其输出。

我中的招…

在读入‘|’时，需要循环把‘&’消耗完，而不是只操作了一次。
最后一步中，如果只输入了‘！V’或‘！F’，mark中只有一个‘！’。因为其他任何输入都不会导致这个中间结果，所以容易忽略这种情况。
在计算完一个括号内的值时，需要判断一次是否需要‘！’，应付！（）的情况。

我的代码（AC）-_-写得很丑…

#include #include #include using namespace std; int clean(string& s); int deal(string s); void neg(); char calcu(); stack mark; stack num; int main() { string line; while (getline(cin, line)) { clean(line); //去除空格deal(line); //进行处理while (!mark.empty()) { num.push(calcu()); }cout << num.top() << endl; } }int clean(string& s) { for (int i = 0; i < s.length(); i++) { if (s[i] == ' ') { s.erase(i, 1); } } return 0; }int deal(string s)//进行处理 { for (int i = 0; i < s.length(); i++) { char c = s[i]; if (c == 'F' || c == 'V') { num.push(c); } else if (c == '&' || c == '|') { while (!mark.empty() && mark.top() == '!') { neg(); } while (c == '|' && !mark.empty() && mark.top() == '&') { num.push(calcu()); } mark.push(c); } else if (c == '!') { mark.push(c); } else if (c == '(') { mark.push(c); } else if (c == ')') { while (!mark.empty() && mark.top() == '!') { neg(); } while (mark.top() != '(') { num.push(calcu()); } mark.pop(); } } return 0; } char calcu()//单次操作-且操作/或操作 { char x; x = mark.top(); mark.pop(); if (x == '!') { char tmp = num.top(); num.pop(); if (tmp == 'F') { return 'V'; } else { return 'F'; } }else { char value1, value2; value1 = num.top(); num.pop(); value2 = num.top(); num.pop(); if (value1 == 'V' && value2 == 'V') { return 'V'; } else if (value1 == 'F' && value2 == 'F') { return 'F'; } else if ((value1 == 'V' || value2 == 'V') && x == '|') { return 'V'; } else if ((value1 == 'F' || value2 == 'F') && x == '&') { return 'F'; } } } void neg() //!操作 { char tmp = num.top(); num.pop(); if (tmp == 'F') { num.push('V'); } else { num.push('F'); } mark.pop(); }

【布尔表达式问题】2015年9月19日，大二上学期。才疏学浅，希望给有疑问的同学带来帮助。