复赛3:逻辑表达式

代码实现:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
/**************************************************************** 
 * Description: 2022_CSP_J_R3
 * Author: Alex Li
 * Date: 2023-09-18 19:50:03
 * LastEditTime: 2023-10-01 21:56:17
****************************************************************/
#include <iostream>
#include <string>
#include <stack>
using namespace std;

struct node {
    //val存0或1,当逻辑值用,cntOr统计或运算的短路数,cntAnd统计与运算的短路数
    int val,cntOr,cntAnd;
};
string expr;
stack<node> s;
 
 //定义符号优先级,'('是0,'|'是1,'&'和')'是2
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);//如果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(); 
            /*cntOr和cntAnd分别统计|和&的短路次数
            如果某处“短路”包含在更外层被“短路”的部分内则不被统计,如表达式 1|(0&1) 中,
            尽管 0&1 是一处“短路”,但由于外层的 1|(0&1) 本身就是一处“短路”,
            无需再计算 0&1 部分的值,因此不应当把这里的 0&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();
            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;
}
  
Scroll to Top