CSP2022-T3（逻辑表达式）

【题目来源】http://oj.tfls.net/d/lnzt/p/15

【题目分析】需要先将题目中的中缀表达式转成后缀表达式计算，计算时使用一个三元结构体（v,a,b)，分别为值，&运算短路的次数，|运算短路的次数，计算时可以分为四种情况：(0,a1,b1)&(v,a2,b2)=(0,a1+1,b1);(1,a1,b1)&(v,a2,b2)=(v,a1+a2,b1+b2); (0,a1,b1)|(v,a2,b2)=(1,a1+a2,b1+b2);(1,a1,b1)|(v,a2,b2)=(1,a1,b1+1);

【中缀转后缀规则】

创建字符栈，扫描中缀表达式。

1.如果是数字，直接成为后缀表达式的一部分；

2.如果是 “(”，进栈；

3.如果是“)”，则从栈顶起，依次将栈中运算符出栈成为后缀表达式的一部分，直到碰到“(”。将栈中“(”出栈，直接消失。

4.如果是运算符，则判断其与栈顶运算符的优先级，若优先级大于栈顶运算符，则进栈；若优先级小于等于栈顶运算符，依次退出栈顶运算符成为后缀表达式的一部分，直到当前运算任优先级大于栈顶运算符，然后将当前运算符放入栈中；

5.扫描结束后，如果栈不为空，将栈中元素依次出栈成为后缀表达式的一部分。

原文链接：https://blog.csdn.net/qq_43290883/article/details/125633103

【后缀表达式计算规则】

创建操作数栈，扫描后缀表达式。

1.如果是数字，入栈。

2.如果是运算符，则从栈顶弹出两个元素，依次为右操作数和左操作数，按照运算规则进行计算，将计算结果入栈。

3.扫描结束后栈顶元素即为表达式结果。

【代码】

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 //获取优先级 
 4 int getyxj(char c) {
 5     if(c=='(') return 0;
 6     if(c=='|') return 1;
 7     if(c=='&') return 2;
 8 }
 9 //中缀转后缀 
10 string zztohz(string str) {
11     stack<char> st;   
12     string hz;
13     for(int i=0; i<str.size(); i++) {
14         if(str[i]=='0'||str[i]=='1')  //规则1 
15             hz+=str[i];
16         else if(str[i]=='(')  //规则2
17             st.push(str[i]);
18         else if(str[i]==')') {  //规则3
19             while(st.top()!='(') {
20                 hz+=st.top();
21                 st.pop();
22             }
23             st.pop();
24         } else {  //规则4
25             while(!st.empty()&&getyxj(str[i])<=getyxj(st.top())) { 
26                 hz+=st.top();
27                 st.pop();
28             }
29             st.push(str[i]);
30         }
31     }
32     while(!st.empty()) {  //规则5
33         hz+=st.top();
34         st.pop();
35     }
36     return hz;
37 }
38 struct node {
39     int v; //value
40     int a; //短路次数 &
41     int b; //短路次数 |
42 };
43 //计算后缀表达式 
44 node js(string str) {
45     stack<node> st;
46     node zuo,you,now,jg;
47     for(int i=0; i<str.size(); i++) {
48         if(str[i]=='0'||str[i]=='1') {  //规则1
49             now.v=str[i]-'0';
50             now.a=0;
51             now.b=0;
52             st.push(now);
53         } else { //规则2
54             you=st.top();
55             st.pop();
56             zuo=st.top();
57             st.pop();
58             if(str[i]=='&'&&zuo.v==0) {
59                 jg.v=0;
60                 jg.a=zuo.a+1;
61                 jg.b=zuo.b;
62             }
63             if(str[i]=='&'&&zuo.v==1) {
64                 jg.v=you.v;
65                 jg.a=zuo.a+you.a;
66                 jg.b=zuo.b+you.b;
67             }
68             if(str[i]=='|'&&zuo.v==0) {
69                 jg.v=you.v;
70                 jg.a=zuo.a+you.a;
71                 jg.b=zuo.b+you.b;
72             }
73             if(str[i]=='|'&&zuo.v==1) {
74                 jg.v=1;
75                 jg.a=zuo.a;
76                 jg.b=zuo.b+1;
77             }
78             st.push(jg);
79         }
80     }
81     return jg;
82 }
83 int main() {
84     string s;
85     getline(cin,s);
86     node jg=js(zztohz(s));
87     cout<<jg.v<<endl;
88     cout<<jg.a<<" "<<jg.b;
89     return 0;
90 }