Next Topic

复赛3：逻辑表达式(expr)

信息学奥赛历年真题 2022年NOIP普及组真题复赛3：逻辑表达式(expr)

洛谷：P8815
OJ: P4976

代码解题思路分析：

题目理解：
- 给定一个逻辑表达式，包含与运算 &、或运算 |，以及可能的括号。
- 需要对该表达式进行求值，并统计在运算过程中发生的短路运算次数。
- 短路运算定义为，如果 a&b 中 a=0，则无需计算 b，直接返回 0。同样地，在 a|b 中如果 a=1，则无需计算 b，直接返回 1。
- 括号内的部分优先计算，& 运算优先于 | 运算。
代码结构：
- struct node：定义了一个节点结构体 node，用于存储当前节点的逻辑值 val，以及该节点中 & 和 | 短路运算的统计量 cntAnd 和 cntOr。
- getPriority：函数返回不同运算符的优先级，& 优先级高于 |，括号最低。
- inToPost：该函数将中缀表达式转化为后缀表达式，以便于后续使用栈进行计算。
- 主程序：
  1. 输入表达式并调用 inToPost 函数将其转化为后缀表达式。
  2. 使用栈逐步计算后缀表达式的结果，过程中处理 & 和 | 运算时，依据逻辑运算规则计算短路次数。

详细分析：

中缀转后缀：通过 inToPost 函数，将中缀表达式转换为后缀表达式，以方便后续栈操作。优先级规则使得括号、&、| 运算按照正确的顺序计算。
短路处理：每次处理 & 和 | 时，根据左操作数是否满足短路条件，统计相应的短路次数。& 运算遇到左边为 0 会短路，而 | 运算遇到左边为 1 会短路。
栈操作：通过栈逐步计算后缀表达式中的每一个操作，遇到操作符时弹出两个操作数，计算后将结果压回栈中。

输出结果：

逻辑表达式的最终计算结果。
两种短路操作发生的次数。

代码实现：

/**************************************************************** 
 * Description: 2022年普及组复赛第三题   逻辑表达式
 * Author: Alex Li
 * Date: 2023-09-18 19:50:03
 * LastEditTime: 2024-10-18 09:41:48
****************************************************************/
#include <iostream>
#include <string>
#include <stack>
using namespace std;

// 定义节点结构体，包含逻辑值、或运算短路计数、与运算短路计数
struct node {
    int val;     // 逻辑值，0 或 1
    int cntOr;   // 统计 | 运算的短路次数
    int cntAnd;  // 统计 & 运算的短路次数
};
string expr; // 输入的逻辑表达式
stack<node> s; // 用于计算后缀表达式的栈

// 获取运算符优先级的函数，括号最低，| 次之，& 最高
int getPriority(char op){
    if(op == '(') return 0;  // '(' 优先级最低
    if(op == '|') return 1;  // '|' 优先级次之
    return 2;  // '&' 和 ')' 优先级最高
}

// 将中缀表达式转换为后缀表达式
string inToPost(string expr){
    stack<char> st;  // 存储运算符的栈
    string ret;  // 用于存储后缀表达式的结果
    for (auto c : expr) {  // 遍历输入的中缀表达式
        if (c == '(') 
            st.push('(');  // 遇到左括号直接入栈
        else if (c == ')') {  // 遇到右括号时，将括号内的运算符全部弹出
            while (st.top() != '(') {
                ret.push_back(st.top());  // 将栈顶的运算符加入后缀表达式
                st.pop();
            }
            st.pop();  // 将 '(' 出栈
        }
        else if (c == '&' || c == '|') {  // 如果遇到 & 或 |
            // 优先级判断，将栈顶优先级不低于当前运算符的弹出
            while (!st.empty() && getPriority(c) <= getPriority(st.top())) {
                ret.push_back(st.top());  // 将运算符加入后缀表达式
                st.pop();
            }
            st.push(c);  // 当前运算符入栈
        }
        else 
            ret.push_back(c);  // 如果是数字，直接加入后缀表达式
    }
    while (!st.empty()) {  // 将栈中剩余的运算符弹出
        ret.push_back(st.top());
        st.pop();
    }
    return ret;  // 返回转换后的后缀表达式
}

int main() {
    cin >> expr;  // 读取输入表达式
    string post = inToPost(expr);  // 将中缀表达式转为后缀表达式
    for (auto c : post) {
        if (c == '|') {  // 遇到 | 运算符时
            node r = s.top(); s.pop();  // 弹出右操作数
            node l = s.top(); s.pop();  // 弹出左操作数
            // 处理短路的情况：如果左操作数为 1，则短路，不计算右操作数
            node temp = { l.val | r.val, l.cntOr + (l.val == 1 ? 1 : r.cntOr), l.cntAnd + (l.val == 1 ? 0 : r.cntAnd) };
            s.push(temp);  // 结果入栈
        }
        else if (c == '&') {  // 遇到 & 运算符时
            node r = s.top(); s.pop();  // 弹出右操作数
            node l = s.top(); s.pop();  // 弹出左操作数
            // 处理短路的情况：如果左操作数为 0，则短路，不计算右操作数
            node temp = { l.val & r.val, l.cntOr + (l.val == 0 ? 0 : r.cntOr), l.cntAnd + (l.val == 0 ? 1 : r.cntAnd) };
            s.push(temp);  // 结果入栈
        }
        else {
            // 如果是数字，转换为节点并入栈
            node temp = { c - '0', 0, 0 };
            s.push(temp);
        }
    }
    node ans = s.top();  // 最终结果在栈顶
    cout << ans.val << endl;  // 输出表达式的计算结果
    cout << ans.cntAnd << " " << ans.cntOr;  // 输出短路次数
}

Previous Topic

Back to Lesson

Next Topic