poj2106 Boolean Expressions

题目：

Description
The objective of the program you are going to produce is to evaluate boolean expressions as the one shown next: Expression: ( V | V ) & F & ( F | V )
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

题意：
给你一个布尔表达式，其中V代表true, F代表false.
优先级：括号的优先级最高，其次是!， 再次是&， 最后是|.
根据上述这些条件计算最后的结果。

题意不难，但要想实现则不是很简单。
基本思想就是模拟布尔表达式的运算。这里我们可以把操作数按优先级转换为相应的数字，利用两个栈（一个存数据，一个存符号）。

参考代码：

#include <iostream>
#include <stack>
#include <algorithm>
#include <cstdio>
using namespace std;

//优先级: '('(0), '|'(1), '&'(2), '!'(3), ')'(4);
stack<int> ops;//存放操作数;
stack<int> vals;//存放值;

void insert_cal(int num) {
    while (!ops.empty() && ops.top() == 3) {//将之前未处理的'!'处理;
        num = !num;
        ops.pop();//处理了该符号就将它弹出;    
    }
    vals.push(num);//插入处理后的值;
}

void cal() {//计算双目运算符, 然后插入vals(需对vals进行处理);
    int a = vals.top();//提取第一个值;
    vals.pop();
    int b = vals.top();//提取第二个值;//处理后就要弹出;
    vals.pop();
    int op = ops.top();//提取操作符;
    ops.pop();
    int num;
    if (op == 2) {//'&'运算;
        num = a & b;
    }
    else if (op == 1) {//'|'运算;
        num = a | b;
    }
    insert_cal(num);//处理之前未处理的'!';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    char c;
    int cnt = 0;
    while ((c = getchar()) != EOF) {
        do {//输入的字符串可能出现多个空格;
            if (c == '(') {//处理到前括号;
                ops.push(0);
            }
            else if (c == 'V' || c == 'F') {
                int num = (c == 'V') ? 1 : 0;//如果当前字符是'V', 则转换为1; 如果当前字符是'F', 则转换为0;
                insert_cal(num);
            }
            else if (c == '!') {//'!'优先级较高且是单目运算符, 可到最后统一处理;
                ops.push(3);    
            }
            else if (c == '&') {//处理之前和它优先级相同或比它高的符号;
                while (!ops.empty() && ops.top() >= 2) {
                    cal();
                }
                ops.push(2);
            }
            else if (c == '|') {//处理之前和它优先级相同或比它高的符号;
                while (!ops.empty() && ops.top() >= 1) {
                    cal();
                }
                ops.push(1);
            }
            else if (c == ')') {//遇到后括号则处理前括号和后括号之间的所有符号和值;
                while (!ops.empty() && ops.top() > 0) {
                    cal();
                }
                ops.pop();//弹出前括号;
                int res = vals.top();
                vals.pop();
                insert_cal(res);//处理得到的值;
            }
        } while ((c = getchar()) != '\n' && c != EOF);
        while (!ops.empty()) {
            cal();//处理还未处理完的符号;
        }
        //当前vals的值转换为字符后就是答案;
        int ans;
        cout << "Expression " << ++cnt << ": " << ((ans = vals.top()) ? 'V' : 'F') << endl;
        vals.pop();
    }
    return 0;
}