CSP-J2022逻辑表达式(expr)-526互联

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int MAXN = 1e6;
struct node
{
   char v;
   int l, r;
};
vector < node > g(MAXN);

int build_tree(string sl)
{
   int last=1;
   stack < int > st;
   for (int i = 0; i < sl.size(); i++)
   {
       if (sl[i] == '0' || sl[i] == '1' )
       {
           g[last].v = sl[i];
           st.push(last);
           last++;
       }
       if (sl[i] == '&' || sl[i] == '|')
       {
           int o2 = st.top();
           st.pop();
           int o1 = st.top();
           st.pop();
           g[last].l = o1;
           g[last].r = o2;
           g[last].v = sl[i];
           st.push(last);
           last++;
       }
   }
   return st.top();
}

int dfs(int root, int& a, int& b)
{
   if(g[root].l == 0 && g[root].r==0) return g[root].v - '0';
   int left = dfs(g[root].l, a, b);
   int result = -1;
   if (g[root].v == '&')
   {
       if (left == 0)
       {
           a++;
           result = 0;
       }
       else result = dfs(g[root].r, a, b);
   }
   else
   {
       if(g[root].v=='|')
       {
           if (left==1)
           {
               b++;
               result=1;
           }
           else result=dfs(g[root].r,a,b);
       }
   }
   return result;
}

string m2l(string s)
{
   string res;
   stack < char > st;
   for (int i = 0; i < s.size(); i++)
   {
       char c = s[i];
       switch (c)
       {
           case '0':
           case '1': res += c; break;
           case '(': st.push(c); break;
           case ')':
                   while(st.top() != '(')
                   {
                       res+=st.top();
                       st.pop();
                   }
                   st.pop();   break;
                   case '&':
                   while (st.size() > 0 && st.top() != '|' && st.top() != '(')
                   {
                       res += st.top();
                       st.pop();
                   }
                   st.push('&');   break;
           case '|':
                   while (st.size() > 0 && st.top() != '(')
                   {
                       res+=st.top();
                       st.pop();
                   }
                   st.push('|');   break;
           default: cout << "error1\n";
           }
   }
   while (st.size() > 0)
   {
       res+=st.top();
       st.pop();
   }
   return res;
}

int main()
{
   string s, sl;
   cin >> s;
   sl = m2l(s); //把中缀表达式转为后缀表达数
   int root = build_tree(sl); //把后缀表达数转化为二叉树
   int a = 0, b = 0; //a为与运算短路的次数 b为或运算短路的次数
   cout << dfs(root, a, b) << endl; //搜索二叉树求答案
   cout << a << " " << b << endl;
   return 0;
}