[CSP-J 2022] 逻辑表达式

· · 个人记录

中缀表达式转后缀表达式 (单调栈) 的模拟题

本蒟蒻在考试前正好刷到了几个与本题类型相似的题目，如下：

  1. P1449 后缀表达式；
  2. P1175 表达式的转换；
  3. P1981 [NOIP2013 普及组] 表达式求值；
  4. 1358：中缀表达式值(expr)。

题解

一. 题目解读分析

本题 意为让程序运算 逻辑表达式。

基本运算：

其中包含的逻辑运算符共有 2 种： & 和 |。

  1. & 的运算规则 ：

两者都为 true 时值为 true

否则值为 false

1 & 1 = 1
1 & 0 = 0
0 & 1 = 0
0 & 0 = 0
  1. ‘|’ 的运算规则 ：

两者都为 false 时值为 false

否则值为 true

1 | 1 = 1
1 | 0 = 1
0 | 1 = 1
0 | 0 = 0

运算优先级：

  1. 括号内的部分先运算。

  2. 两种运算并列时，& 运算优先于 | 运算。

eg: 1 | 0 & 1

先算 & 关联逻辑表达式的值 , 再算 | 关联逻辑表达式的值

  1. 同种运算并列时，从左向右运算。

断路：

对于 a b 两个 bool 类型 或 逻辑表达式。

当 a 的值 能够决定 表达式的值 时 ，计断路一次。

且不用计算 表达式b 中的断路次数。

  1. 第一种 & 断路

    1. 当 a == 0 时 ，a & b 必然等于 0 ，计一次数

2. 当 a == 1 时 ，a & b 不一定等于 1 或 0 ，不计数

  2. 第二种 | 断路

    1. 当 a == 1 时 ，a | b 必然等于 0 ，计一次数

2. 当 a == 0 时 ，a | b 不一定等于 1 或 0 ，不计数

二. 算法部分

  1. 后缀表达式转中缀表达式

规则

运算过程需要运用到 单调栈 的思想

    1. 如果遇到操作数，就直接将其输出。

    2. 如果遇到操作符，则将其放入到栈中，遇到左括号时也将其放入栈中。

    3. 如果遇到一个右括号，则将栈元素弹出，将弹出的操作符输出直到遇到左括号为止。注意，左括号只弹出并不输出。

    4. 如果遇到任何其他的操作符，如（‘+’， ‘*’，‘（’）等，从栈中弹出元素直到遇到发现更低优先级的元素(或者栈为空)为止。弹出完这些元素后，

       才将遇到的操作符压入到栈中。有一点需要注意，只有在遇到 ‘）’ 的情况下才弹出‘（’， 其他情况我们都不会弹出 ‘（’。

    5. 如果读到了输入的末尾，则将栈中所有元素依次弹出。

例如

对于 逻辑表达式 a + b c + ( d e + f ) * g

1）首先读到 a，直接输出。

2）读到 ' + ' ，将其放入到栈中。

3）读到 b，直接输出。

此时栈和输出情况如下：

4）读到 ' ' ，因为栈顶元素 ' + ' 优先级比 ' ' 低 , 所以将 ' * ' 直接压入栈中。

5）读到 c，直接输出。

此时栈和输出情况如下：

6）读到 ' + ' ，因为栈顶元素 ' ' 的优先级比它高 , 所以弹出 ' ' 并输出 , 同理,栈中下一个元素 ' + ' 优先级与读到的操作符 ' + ' 一样 , 所以也要弹出并输出。然后再将读到的 ' + ' 压入栈中。

此时栈和输出情况如下：

7）下一个读到的为 ' ( ' , 它优先级最高，所以直接放入到栈中。

8）读到 d，将其直接输出。

此时栈和输出情况如下：

9）读到 ' ' ，由于只有遇到 ' ) '的时候左括号 ' ( ' 才会弹出,所以 ' ' 直接压入栈中。

10）读到 e，直接输出。

此时栈和输出情况如下：

11）读到 ' + ' , 弹出 ' * ' 并输出 , 然后将 ' + ' 压入栈中。

12）读到 f , 直接输出。

此时栈和输出情况：

13）接下来读到 ' )' , 则直接将栈中元素弹出并输出直到遇到 ' ( ' 为止。这里右括号前只有一个操作符 ' + ' 被弹出并输出。

14）读到 ' * ' , 压入栈中。读到 g，直接输出。

15）此时输入数据已经读到末尾，栈中还有两个操作符 ' * ' 和 ' + ' , 直接弹出并输出。

至此整个转换过程完成。程序实现代码后续再补充了。

  1. 后缀表达式求值

后缀表达式也叫逆波兰表达式，其求值过程可以用到栈来辅助存储。假定待求值的后缀表达式为：6 5 2 3 + 8 + 3 + ，则其求值过程如下：

1）遍历表达式，遇到的数字首先放入栈中，此时栈如下所示：

2）接着读到“+”，则弹出3和2，执行3+2，计算结果等于5，并将5压入到栈中。

3）读到8，将其直接放入栈中。

4）读到“”，弹出8和5，执行85，并将结果40压入栈中。而后过程类似，读到“+”，将40和5弹出，将40+5的结果45压入栈...以此类推。最后求的值288。

  1. 两种断路计数

    对于 a b 两个 AB 类型

    struct AB{
  bool value;

  int d1; // 关于 & 断路情况

  int d2; // 关于 | 断路情况

  AB(){d1=d2=0;}
}

    第一种 & 断路

    第二种 | 断路

最后的 答案 的 d1 d2 就是 两种断路情况数

#include <iostream>
#include <stdio.h>
#include <stack>
#include <string.h>
using namespace std;
struct AB{
    int x;
    int d1,d2;
}ab;
string expr;
stack <AB> _st;
int d1,d2,tot;
char real[2000000];
// 计算
int calc()
{
    int ans;
    AB a,b;
    for(int i=1;i<=tot;i++)
    {
        if(real[i]>='0'&&real[i]<='9')
        {
            ab.x = real[i]-'0';
            ab.d1 = 0;
            ab.d2 = 0;
            _st.push(ab);
        }
        else
        {
            b = _st.top();
            _st.pop();
            a = _st.top();
            _st.pop();
            if(real[i]=='|')
            {
                if(a.x==1)
                {
                    ab.x = 1;
                    ab.d1 = a.d1+1;
                    ab.d2 = a.d2;
                    _st.push(ab);
                }
                else if(b.x==1)
                {
                    ab.x = 1;
                    ab.d1 = a.d1+b.d1;
                    ab.d2 = a.d2+b.d2;
                    _st.push(ab);
                }
                else
                {
                    ab.x = 0;
                    ab.d1 = a.d1+b.d1;
                    ab.d2 = a.d2+b.d2;
                    _st.push(ab);
                }
            }
            else
            {
                if(a.x==0)
                {
                    ab.x = 0;
                    ab.d1 = a.d1;
                    ab.d2 = a.d2+1;
                    _st.push(ab);
                }
                else if(b.x==0)
                {
                    ab.x = 0;
                    ab.d1 = a.d1+b.d1;
                    ab.d2 = a.d2+b.d2;
                    _st.push(ab);
                }
                else
                {
                    ab.x = 1;
                    ab.d1 = a.d1+b.d1;
                    ab.d2 = a.d2+b.d2;
                    _st.push(ab);
                }
            }
        }
    }
    d1 = _st.top().d1;
    d2 = _st.top().d2;
    ans = _st.top().x;
    return ans;
} 
stack <char> st;
// 转后缀表达式 
char ch[2000000];
void change()
{
    int i;
    for(i=0;i<expr.length();i++)
        ch[i+1] = expr[i];
    for(i=1;i<=expr.length();i++)
    {
        if(ch[i]>='0'&&ch[i]<='9')
        {
            real[++tot] = ch[i];
        }
        else
        {
            if(ch[i]=='|')
            {
                while(!st.empty()&&st.top()!='(')
                {
                    real[++tot] = st.top();
                    st.pop();
                }
                st.push(ch[i]);
            }
            else if(ch[i]=='&')
            {
                while(!st.empty()&&(st.top()!='('&&st.top()!='|'))
                {
                    real[++tot] = st.top();
                    st.pop();
                }
                st.push(ch[i]);
            }
            else
            {
                if(ch[i]=='(')
                {
                    st.push(ch[i]);
                }
                else
                {
                    while(!st.empty()&&st.top()!='(')
                    {
                        real[++tot] = st.top();
                        st.pop();
                    }
                    if(st.top()=='(')
                        st.pop();
                }
            }
        }
    }
    while(!st.empty())
    {
        real[++tot] = st.top();
        st.pop();
    }
    return ;
}

int main()
{
//  freopen("expr.in","r",stdin);
//  freopen("expr.out","w",stdout);
    cin >> expr;
    change();
    cout << calc()<<endl;
    cout << d2<<" "<< d1;

//  fclose(stdin);
//  fclose(stdout);
    return 0;
}