对于处理中缀表达式（含括号嵌套）的方法

几天前我在我空间里写过，这里，我觉得需要完善一下：

这里以NOIP2011普及组第四题为例：为什么选择这题呢，因为我在NOIP2011惜败！至今都忘不了我这题爆0！

http://www.rqnoj.cn/Problem_663.html

还有一题计算练习：

http://www.rqnoj.cn/Problem_307.html

话说写错一个数字才导致有两点进入死循环。。

其实，我觉得难度最大的在于模拟，它考察选手的编程实现功底，模拟最难的在于字符串处理。像这样的题目其实就是处理我们平常书写的计算式，如“3+8*(4-2)”。而处理的难点在于优先级的运算和层层括号嵌套的麻烦。

因此，我们必须利用递归来解决这些烦人的问题。可以让递归的程序返回一个值，表示处理x到y这段字符所得到的结果，并把它作为一个整体，代入计算到调用它的程序中去。

下面简述下方法：

0.首先确定在一个范围[x,y]内进行计算。

1.找到所有括号外的“+”号。并把它们一一分段，递归求解每一分段，然后将所有的值相加。

2.经过1处理过后的一段或找不到“+”号，这时我们再找到所有括号外的“*”号。同1操作分段相乘。

3.如果2操作中找不到“*”号，说明这个范围内要么只剩下一个数，要么是在一个括号内，这时递归求解compute(x+1,y-1)，并当做compute(x,y)的返回值。

4.然后把括号内的数当做新的表达式递归求解。

完毕。

其实处理就这么简单，但是却非常不容易想清楚处理的步骤和方法。大家还是要靠自己啊。

参考代码：

  1 #include"stdio.h"
  2 #include"string.h"
  3 char s[8010];
  4 long bk[8010];
  5 long n,ans;
  6 void _Bracket(long x)
  7 {
  8     long i;
  9     for(i=x+1;i<=n;i++)
 10     {
 11         if(s[i]=='(')
 12         {
 13             _Bracket(i);
 14             i=bk[i];
 15         }
 16         else if(s[i]==')')
 17         {
 18             bk[x]=i;
 19             return ;
 20         }
 21     }
 22 }
 23 long _find_1(long x,long y)
 24 {
 25     long i;
 26     for(i=x;i<=y;i++)
 27         if(s[i]=='(')
 28             i=bk[i];
 29         else if(s[i]=='+'||s[i]=='-')
 30             return i;
 31     return y+1;
 32 }
 33 long _find_2(long x,long y)
 34 {
 35     long i;
 36     for(i=x;i<=y;i++)
 37         if(s[i]=='(')
 38             i=bk[i];
 39         else if(s[i]=='*')
 40             return i;
 41     return y+1;
 42 }
 43 long dfs(long x,long y)
 44 {
 45     long f,r,p;
 46     f=_find_1(x,y);
 47     if(f>y)// if without '+'/'-' which is not in brackets.
 48     {
 49         f=_find_2(x,y);
 50         if(f>y)//if without '*' which is not in brackets.
 51             if(s[x]=='(')//if it is in brackets.
 52                 return dfs(x+1,y-1);
 53             else
 54             {
 55                 sscanf(&s[x],"%ld",&p);
 56                 return p;
 57             }
 58         else// there is '*‘ 
 59         {
 60             p=dfs(x,f-1);
 61             while(f<=y)
 62             {
 63                 r=_find_2(f+1,y);
 64                 p*=dfs(f+1,r-1);
 65                 f=r;
 66             }
 67             return p;
 68         }
 69     }
 70     else//there is '+'/'-'
 71     {
 72         p=dfs(x,f-1);
 73         while(f<=y)
 74         {
 75             r=_find_1(f+1,y);
 76             if(s[f]=='-')
 77                 p-=dfs(f+1,r-1);
 78             else p+=dfs(f+1,r-1);
 79             f=r;
 80         }
 81         return p;
 82     }
 83 }
 84 void init()
 85 {
 86     gets(&s[1]);
 87     n=strlen(&s[1]);
 88     _Bracket(0);
 89 }
 90 void use_nature()
 91 {
 92     ans=dfs(1,n);
 93 }
 94 void print()
 95 {
 96     printf("%ld\n",ans);
 97 }
 98 int main()
 99 {
100     init();
101     use_nature();
102     print();
103     getchar(),getchar();
104     return 0;
105 }

Rqnoj---307

  1 #include"stdio.h"
  2 typedef struct{
  3     long _0,_1;
  4 }_ct;
  5 char s[100010];
  6 long bk[100010];
  7 long l,ans;
  8 long bracket(long x)
  9 {
 10     long i;
 11     for(i=x+1;i<=l;i++)
 12     {
 13         if(s[i]=='(')
 14         {
 15             bracket(i);
 16             i=bk[i];
 17         }
 18         else if(s[i]==')')
 19         {
 20             bk[x]=i;
 21             return bk[x];
 22         }
 23     }
 24     return 0;
 25 }
 26 void init()
 27 {
 28     long i;
 29     scanf("%ld",&l);
 30     scanf(" %s",&s[1]);
 31     bracket(0);
 32 }
 33 _ct unit_high(_ct x,_ct y)
 34 {
 35     _ct ret={0,0};
 36     ret._0=x._1*y._0+x._0*y._1+x._0*y._0;
 37     ret._1=x._1*y._1;
 38     ret._0%=10007;
 39     ret._1%=10007;
 40     return ret;
 41 }
 42 _ct unit_low(_ct x,_ct y)
 43 {
 44     _ct ret={0,0};
 45     ret._0=x._0*y._0;
 46     ret._1=x._1*y._0+x._0*y._1+x._1*y._1;
 47     ret._0%=10007;
 48     ret._1%=10007;
 49     return ret;
 50 }
 51 long _find_low(long x,long y)
 52 {
 53     long i;
 54     for(i=x;i<=y;i++)
 55         if(s[i]=='+')
 56             return i;
 57         else if(s[i]=='(')
 58             i=bk[i];
 59     return y+1;
 60 }
 61 long _find_high(long x,long y)
 62 {
 63     long i;
 64     for(i=x;i<=y;i++)
 65         if(s[i]=='*')
 66             return i;
 67         else if(s[i]=='(')
 68             i=bk[i];
 69     return y+1;
 70 }
 71 _ct dp(long x,long y)
 72 {
 73     _ct p={1,1},ans;
 74     long i,f,r;
 75     if(x>y) return p;//1_tion
 76     
 77     f=_find_low(x,y);
 78     if(f>y)
 79     {
 80         f=_find_high(x,y);
 81         if(f>y) return dp(x+1,y-1);//there are brackets but nothing.
 82         else
 83         {
 84             ans=dp(x,f-1);
 85             while(f<=y)
 86             {
 87                 r=_find_high(f+1,y);
 88                 ans=unit_high(ans,dp(f+1,r-1));
 89                 f=r;
 90             }
 91         }//divide '*';
 92     }//2_tion   without '+' which is not in brackets.
 93     else
 94     {
 95         ans=dp(x,f-1);
 96         while(f<=y)
 97         {
 98             r=_find_low(f+1,y);
 99             ans=unit_low(ans,dp(f+1,r-1));
100             f=r;
101         }
102     }//divide '+'
103     return ans;
104 }
105 void use_nature()
106 {
107     ans=dp(1,l)._0;
108 }
109 void print()
110 {
111     printf("%ld\n",ans);
112 }
113 int main()
114 {
115      init();
116      use_nature();
117      print();
118      getchar(),getchar();
119      return 0;
120 }

Rqnoj---663

这里我们再深入思考一下：我们平常所书写的，成为中缀表达式，它是需要括号来控制优先级的。事实上，还是称之为前缀表达式和后缀表达式的东西，而且他们不需要括号！（有关他们的问题，请自行百度）如果仔细想想，处理表达式，实际上是一种树的合并过程！

父节点为符号+-*/，其左子树的权值为符号的左元，右子树的权值为符号的右元。叶子节点为一个数值，代表他的权值。这样，我们就可以把一个表达式完整地用树表达出来，并且它的后序遍历就是这个表达式的一个后缀表达式。

那么，如果我们现在要如何建一个表达式的树呢？递归。

事实上，建树可比上述方法简单的多。

很巧，就有一个这样的题目：http://www.rqnoj.cn/Problem_348.html

处理方法：我们只需要倒着搜一个优先级最低的符号，然后把表达式分成两段，递归建树即可。注意，跳过括号。至于细节，就交给读者来完善了。

参考代码：

  1 #include"stdio.h"
  2 #include"string.h"
  3 typedef struct{
  4     long num;//+ <=> 10 | - <=> 11 | * <=> 12 | / <=>13 | ^ <=> 14 |
  5     long l,r,f;
  6 }type;
  7 type q[100010]={0};
  8 char s[100010];
  9 char _put[15]="0123456789+-*/^";
 10 long bk[100010];
 11 long n,m=0,head;
 12 void _Bracket_down(long x)
 13 {
 14     long i;
 15     for(i=x-1;i>=1;i--)
 16     {
 17         if(s[i]==')')
 18         {
 19             _Bracket_down(i);
 20             i=bk[i];
 21         }
 22         else if(s[i]=='(')
 23         {
 24             bk[x]=i;
 25             return;
 26         }
 27     }
 28 }
 29 long _find(long x,long y,char p,char q)
 30 {
 31     long i;
 32     for(i=y;i>=x;i--)
 33         if(s[i]==')')
 34             i=bk[i];
 35         else if(s[i]==p||s[i]==q)
 36             return i;
 37     return x-1;
 38 }
 39 long _Build_Tree(long x,long y)
 40 {
 41     long k,e;
 42     e=++m;
 43     if(x==y)
 44     {
 45         q[e].num=s[x]-'0';
 46         q[e].f=1;
 47         return e;
 48     }
 49     else
 50     {
 51         k=_find(x,y,'+','-');
 52         if(k<x)
 53         {
 54             k=_find(x,y,'*','/');
 55             if(k<x)
 56             {
 57                 k=_find(x,y,'^',' ');
 58                 if(k<x)
 59                 {
 60                     m--;
 61                     return _Build_Tree(x+1,y-1);
 62                 }
 63                 else q[e].num=14;
 64             }
 65             else q[e].num=12+(s[k]=='/');
 66         }
 67         else q[e].num=10+(s[k]=='-');
 68     }
 69     q[e].l=_Build_Tree(x,k-1);
 70     q[e].r=_Build_Tree(k+1,y);
 71     return e;
 72 }    
 73 void init()
 74 {
 75     gets(&s[1]);
 76     n=strlen(&s[1]);
 77     _Bracket_down(n+1);
 78     head=_Build_Tree(1,n);
 79 }
 80 void Behind(long x)
 81 {
 82     if(!q[x].f)
 83     {
 84         Behind(q[x].l);
 85         Behind(q[x].r);
 86         printf("%c",_put[q[x].num]);
 87     }
 88     else printf("%ld",q[x].num);
 89     if(x!=head) printf(" ");
 90     else printf("\n");
 91 }
 92 long _exp(long x,long y)
 93 {
 94     long i,sum=1;
 95     for(i=1;i<=y;i++)
 96         sum*=x;
 97     return sum;
 98 }
 99 void dfs(long x)
100 {
101     if(q[x].f) return;
102     dfs(q[x].l);
103     dfs(q[x].r);
104     switch(q[x].num){
105         case 10: q[x].num=q[q[x].l].num+q[q[x].r].num;break;
106         case 11: q[x].num=q[q[x].l].num-q[q[x].r].num;break;
107         case 12: q[x].num=q[q[x].l].num*q[q[x].r].num;break;
108         case 13: q[x].num=q[q[x].l].num/q[q[x].r].num;break;
109         case 14: q[x].num=_exp(q[q[x].l].num,q[q[x].r].num);break;
110     }
111     q[x].f=1;
112     Behind(head);
113 }
114 void use_nature()
115 {
116     Behind(head);
117     dfs(head);
118 }
119 int main()
120 {
121     init();
122     use_nature();
123     getchar(),getchar();
124     return 0;
125 }
126 /*
127 8-((3+2*6)/5+4)+8-((3+2*6)/5+4)+8-((3+2*6)/5+4)+8-((3+2*6)/5+4)
128 */

Rqnoj---348

那么，如果我们需要将一个树转化为中缀表达式，又该如何呢？就交给读者思考了。

秒客网

对于处理中缀表达式（含括号嵌套）的方法

相关文章