codeforces gym 100357 K (表达式模拟）

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题目大意

将一个含有+，-，^，（）的表达式按照运算顺序转换成树状的形式。

解题分析

用递归的方式来处理表达式，首先直接去掉两边的括号（如果不止一对全部去光），然后找出不在括号内且优先级最低的符号。如果优先级相同，则如果是左结合性（+，-，*，/）则选择最右边的一个，如果是右结合性（^）则选择最最左边的一个。

主要恶心的地方在于输出上。主要是记录一下每个点和符号的位置，在递归和返回时传递一些参数。

ps：虽然输出比较恶心，但最终实现出来后还是感到十分地身心愉悦。

参考程序

 #include <bits/stdc++.h>

 using namespace std;

 typedef pair<int,int> pii;

 string s;

 int a[];

 int level(char ch)

 {

     switch (ch)

     {

         case '+':;

         case '-':return ;

         case '*':;

         case '/':return ;

         case '^':return ;

         default:return ;

     }

 }

 int r,c,tmp=;

 struct node{

     int l,mid,r,len;

     char ch;

 }w[];

 pii solve(int x,int y,int heap,int op)

 {

     //cout<<s.substr(x,y-x+1)<<endl;

     if (heap>r) r=heap;

     if (op>c) c=op;

     while (s[x]=='(' && s[y]==')')

     {

         int t=,flag=;

         for (int i=x+;i<=y-;i++)

         {

             if (s[i]=='(') t++; else if (s[i]==')') t--;

             if (t<) flag=;

         }

         if (flag)

         {

             x++;

             y--;

         }

         else break;

     }

     int len=y-x+;

     if (len==)

     {

         w[++tmp]=(node){op,op,op,heap,s[x]};

         return pii(,);

     }

     for (int i=x;i<=y;i++) a[i]=;

     if (s[x]=='(') a[x]=; else a[x]=;

     for (int i=x+;i<=y;i++)

         if (s[i]=='(') a[i]=a[i-]+; else

         if (s[i]==')') a[i]=a[i-]-; else

         a[i]=a[i-];

     int p=,mx=;

     for (int i=x;i<=y;i++)

     {

         if (a[i]==)

             if (s[i]=='^' && level(s[i])<mx || s[i]!='^' && level(s[i])<=mx )

             {

                 p=i;

                 mx=level(s[i]);

             }

     }

     pii left=solve(x,p-,heap+,op);

     int now=op+left.second+;

     pii right=solve(p+,y,heap+,now+);

     w[++tmp]=(node){op+left.first-,op+left.second+,now+right.first+-,heap,s[p]};

     return pii(left.second+,left.second++right.second);

 }

 int cmp(const node &a,const node &b)

 {

     return a.len<b.len || a.len==b.len && a.mid<b.mid;

 }

 int main()

 {

     freopen("tree.in","r",stdin);

     freopen("tree.out","w",stdout);

     cin>>s;

     pii p=solve(,s.length()-,,);

     sort(w+,w+tmp+,cmp);

     for (int h=;h<=w[tmp].len;h++)

     {

         int i,j;

         for (i=;w[i].len!=h;i++);

         for (j=i;w[j+].len==h;j++);

         if (h!=)

         {

             for (int t=;t<=w[i].mid-;t++) printf(" ");

             printf("|");

             for (int k=i+;k<=j;k++)

             {

                 for (int t=w[k-].mid+;t<=w[k].mid-;t++) printf(" ");

                 printf("|");

             }

             printf("\n");

         }

         for (int t=;t<=w[i].l-;t++) printf(" ");

         if (level(w[i].ch)!=) printf(".");

         for (int t=w[i].l+;t<=w[i].mid-;t++) printf("-");

         if (level(w[i].ch)!=) printf("[");

         printf("%c",w[i].ch);

         if (level(w[i].ch)!=) printf("]");

         for (int t=w[i].mid+;t<=w[i].r-;t++) printf("-");

         if (level(w[i].ch)!=) printf(".");

         for (int k=i+;k<=j;k++)

         {

             for (int t=w[k-].r+;t<=w[k].l-;t++) printf(" ");

             if (level(w[k].ch)!=) printf(".");

             for (int t=w[k].l+;t<=w[k].mid-;t++) printf("-");

             if (level(w[k].ch)!=) printf("[");

             printf("%c",w[k].ch);

             if (level(w[k].ch)!=) printf("]");

             for (int t=w[k].mid+;t<=w[k].r-;t++) printf("-");

             if (level(w[k].ch)!=) printf(".");

         }

         printf("\n");

     }

 }