题解 P1575 【正误问题】

· · 题解

P1575 正误问题

题目大致的意思就是输入一个逻辑表达式（包含 true、false、and、or 和 not），求此逻辑表达式的值（true 或 false）。

一般来说，计算表达式的值（无论是数学的运算还是逻辑的运算）都可以用栈（stack）来实现。每次取栈顶的一个（一元运算 not）或两个（二元运算 and 和 or）逻辑值进行操作，并将新生成的值压入栈顶。

首先处理输入。我一开始想到的是用 getline() 读入一整行的表达式，然后将逻辑值和运算符分离出来，但发现代码实现的难度很大。

然后我就想到了用 while，这样就免除了分离的麻烦。

while(cin>>p){
    //在这里填入处理的代码
}

其中，p 用来存放输入的运算符或值（下同）。

其次就是考虑怎么计算。逻辑表达式的运算符和数学运算一样，存在优先级，即 not、and 和 or（从大到小）。

所以当我们输入这个运算符时，就可以把它的优先级存入栈。注意，如果直接将字符串作为运算符存入栈，会增加很多的代码量，所以为了方便起见，我们可以使用将优先级存入栈的策略。

if(p=="not") f.push(3);
if(p=="and") f.push(2);
if(p=="or") f.push(1);

其中，f 是存放运算符优先级的一个整型的栈（下同）。

怎么处理输入的逻辑值呢？很简单，将 true 或 false 压入栈就好了：

if(p=="true") v.push(true);
if(p=="false") v.push(false);

其中，v 是存放逻辑值的一个布尔型的栈（下同）。

处理逻辑值的计算时，取栈顶元素计算即可：

void calc() {
    if(f.empty()) return;//当f为空时表示栈中没有运算符，不需要进行任何处理
    if(f.top()==3) {
        t=v.top();
        v.pop();
        t=!t;//3表示not
        v.push(t);
    }
    if(f.top()==2) {
        t2=v.top();
        v.pop();
        t1=v.top();
        v.pop();
        t=(t1 && t2);//2表示and
        v.push(t);
    }
    if(f.top()==1) {
        t2=v.top();
        v.pop();
        t1=v.top();
        v.pop();
        t=(t1 || t2);//1表示or
        v.push(t);
    }
    f.pop();
}

其中，t、t1、t2 都是布尔型的变量。

但是，我们知道，由于 and 和 or 是二元运算，所以当输入它（们）时，如果值栈（即 v，下同）中没有元素（栈为空），那么所输入的表达式就是错误的，这时，我们应该输出 \texttt{error}，并结束程序。同理，当输入 not 时，若值栈中没有元素，也应该做出错处理。

if(v.empty()){
    printf("error\n");
    exit(0);//或return 0;
}

这段代码应该放在主函数中输入的位置，作为输入时的处理。

当我们调用 calc() 函数时，如果也遇到类似的情况，也作类似处理。但要注意，and 和 or 应判断元素个数不小于 2，因为此时已经不存在未输入的逻辑值了，故必有 2 个或 2 个以上的值在栈中，否则就是错误的表达式。

最后，如果栈中还有未完成的运算，就继续调用 calc()，直到栈中没有运算符为止。

while(!f.empty()) calc();

输出时需要注意，如果值栈中存在多个元素，就说明表达式有误，应输出 \texttt{error}。但是即使表达式是对的，我们也不能直接输出答案，因为 true 或 false 直接输出会得到 1 或 0，我们应该输出 \texttt{true} 或 \texttt{false}（字符串）。

if(v.size()==1)
    if(v.top()) printf("true\n");
    else printf("false\n");
else printf("error\n");

至此，P1575 正误问题一题我们已经解决了，如果你还有什么不明白的，或存在未解决的问题，可以参考其他大佬的题解，相信你可以完美地解决这道题。

附：完整的代码（仅供学习参考）