蓝桥杯表达式求解(详解)

问题描述
　　输入一个只包含加减乖除和括号的合法表达式，求表达式的值。其中除表示整除。
输入格式
　　输入一行，包含一个表达式。
输出格式
　　输出这个表达式的值。
样例输入
1-2+3*(4-5)
样例输出
-4
数据规模和约定
　　表达式长度不超过100，表达式运算合法且运算过程都在int内进行。

#include <stdio.h>
#include <string.h>
char a[101];
int b[101]={0};
int bj[100]={0};
int f(int ks,int js)//不含括号或剥去括号剩下的表达式计算 
{
    int x,t1;
    for(x=ks;x<=js;x++)           // a*b+c
       if(bj[x]==0&&(a[b[x]]=='*'||a[b[x]]=='/'))// 找到运算符优先级高的 + - 小于 * / 
       {  if(a[b[x]]=='*')     // 运算符前一位 和后一位 操作 运算符 a*b
           b[x-1]=b[x-1]*b[x+1]; // D=a*b 再把 a‘=D ; 擦除*b 剩下 a'+c
        else b[x-1]=b[x-1]/b[x+1];
            t1=0;              
           while((x+2+t1)<(js+1))//通过 移位 覆盖法 去除已计算过 的值 
           {b[x+t1]=b[x+2+t1];
            bj[x+t1]=bj[x+2+t1];
              t1++;
           } js=js-2;x--;

   <span class="token punctuation">}</span>
<span class="token keyword">for</span><span class="token punctuation">(</span>x<span class="token operator">=</span>ks<span class="token punctuation">;</span>x<span class="token operator">&lt;=</span>js<span class="token punctuation">;</span>x<span class="token operator">++</span><span class="token punctuation">)</span>
   <span class="token keyword">if</span><span class="token punctuation">(</span>bj<span class="token punctuation">[</span>x<span class="token punctuation">]</span><span class="token operator">==</span><span class="token number">0</span><span class="token operator">&amp;&amp;</span><span class="token punctuation">(</span>a<span class="token punctuation">[</span>b<span class="token punctuation">[</span>x<span class="token punctuation">]</span><span class="token punctuation">]</span><span class="token operator">==</span><span class="token string">&apos;+&apos;</span><span class="token operator">||</span>a<span class="token punctuation">[</span>b<span class="token punctuation">[</span>x<span class="token punctuation">]</span><span class="token punctuation">]</span><span class="token operator">==</span><span class="token string">&apos;-&apos;</span><span class="token punctuation">)</span><span class="token punctuation">)</span>
   <span class="token punctuation">{</span> <span class="token keyword">if</span><span class="token punctuation">(</span>a<span class="token punctuation">[</span>b<span class="token punctuation">[</span>x<span class="token punctuation">]</span><span class="token punctuation">]</span><span class="token operator">==</span><span class="token string">&apos;+&apos;</span><span class="token punctuation">)</span> 
      b<span class="token punctuation">[</span>x<span class="token number">-1</span><span class="token punctuation">]</span><span class="token operator">=</span>b<span class="token punctuation">[</span>x<span class="token number">-1</span><span class="token punctuation">]</span><span class="token operator">+</span>b<span class="token punctuation">[</span>x<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
      <span class="token keyword">else</span> b<span class="token punctuation">[</span>x<span class="token number">-1</span><span class="token punctuation">]</span><span class="token operator">=</span>b<span class="token punctuation">[</span>x<span class="token number">-1</span><span class="token punctuation">]</span><span class="token operator">-</span>b<span class="token punctuation">[</span>x<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
       t1<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>
       <span class="token keyword">while</span><span class="token punctuation">(</span><span class="token punctuation">(</span>x<span class="token operator">+</span><span class="token number">2</span><span class="token operator">+</span>t1<span class="token punctuation">)</span><span class="token operator">&lt;</span><span class="token punctuation">(</span>js<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">)</span>
       <span class="token punctuation">{</span>b<span class="token punctuation">[</span>x<span class="token operator">+</span>t1<span class="token punctuation">]</span><span class="token operator">=</span>b<span class="token punctuation">[</span>x<span class="token operator">+</span><span class="token number">2</span><span class="token operator">+</span>t1<span class="token punctuation">]</span><span class="token punctuation">;</span>
         bj<span class="token punctuation">[</span>x<span class="token operator">+</span>t1<span class="token punctuation">]</span><span class="token operator">=</span>bj<span class="token punctuation">[</span>x<span class="token operator">+</span><span class="token number">2</span><span class="token operator">+</span>t1<span class="token punctuation">]</span><span class="token punctuation">;</span>
          t1<span class="token operator">++</span><span class="token punctuation">;</span>
       <span class="token punctuation">}</span> js<span class="token operator">=</span>js<span class="token number">-2</span><span class="token punctuation">;</span>x<span class="token operator">--</span><span class="token punctuation">;</span>

   <span class="token punctuation">}</span>

<span class="token keyword">return</span> b<span class="token punctuation">[</span>ks<span class="token punctuation">]</span><span class="token punctuation">;</span>
}
int f2(int n)
{  if(n==0)return 1;
   else return f2(n-1)*10;
}
int main()
{int zh[100]={0};
int len,i,j,i1=0,s1=0,k,t,sum;
scanf("%s",&a);
len=strlen(a);
for(i=0;i<len;i++)//将所有运算符号的a[i]数组下标放入b[i1]中 只对 运算符号做判断 
if(a[i]<48)                 //a[i] 1 2 + 2 3 - 1
{if(s1!=0){                // 0 1 2 3 4 5 6
 for(j=s1-1;j>=0;j–)     // b[i1] 12 2 23 5 1
 b[i1]+=zh[j]*f2(s1-1-j);// 0 1 2 3 4 
 bj[i1]=1;i1++;}       // 相当于将 12 + 23 - 1 存入 b[i1] 
   b[i1++]=i;  s1=0;}    // bj[i1] 1 0 1 0 1 (0代表b[i1]存的是运算符号在a[i]中的下标 1代表存的数值） 
  else
   {zh[s1++]=a[i]-48; }
<span class="token keyword">if</span><span class="token punctuation">(</span>s1<span class="token operator">!=</span><span class="token number">0</span><span class="token punctuation">)</span>
 {for(j=s1-1;j>=0;j–)
 b[i1]+=zh[j]*f2(s1-1-j);bj[i1]=1;i1++;}//处理 末尾为数值 
while(1)
 {
   for(i=0;i<i1;i++)          //'(' ')'相当于把 （a+b）c 把 a+b从括号中截取出来
    if(bj[i]==0&&a[b[i]]=='(')// 先计算 D=a+b 然后将 （a+b）替换为D 然后算没括号的 Dc 
      {
        for(j=i+1;j<i1;j++)
          {
           if(bj[j]==0&&a[b[j]]=='(')break;//若先找到'(' 则当前'('优先级小于找到的'(';所以跳过从优先级最高的开始 
           if(bj[j]==0&&a[b[j]]==')')
           {
             b[i]=f(i+1,j-1);bj[i]=1;//找到当前高优先级 然后计算 括号里的 f(i+1,j-1) '('位替换为算出的数值 对应标记变为 1 
             k=1;
              while(j+k<i1)
              { b[i+k]=b[j+k];//移位覆盖法擦去 
                bj[i+k]=bj[j+k];
                 k++;
              }i1=i1-(j-i);break; 
        <span class="token punctuation">}</span> 
      <span class="token punctuation">}</span>
  <span class="token punctuation">}</span>    
  <span class="token keyword">for</span><span class="token punctuation">(</span>i<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>i<span class="token operator">&lt;</span>i1<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span>
<span class="token keyword">if</span><span class="token punctuation">(</span>bj<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">==</span><span class="token number">0</span><span class="token operator">&amp;&amp;</span>a<span class="token punctuation">[</span>b<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">]</span><span class="token operator">==</span><span class="token string">&apos;(&apos;</span><span class="token punctuation">)</span><span class="token keyword">break</span><span class="token punctuation">;</span>       
      <span class="token keyword">if</span><span class="token punctuation">(</span>i<span class="token operator">==</span>i1<span class="token punctuation">)</span><span class="token keyword">break</span><span class="token punctuation">;</span><span class="token comment" spellcheck="true">//&#x5269;&#x4E0B;&#x8868;&#x8FBE;&#x5F0F;&#x4E0D;&#x542B;&#x62EC;&#x53F7;&#x65F6; &#x8DF3;&#x51FA; </span>

 <span class="token punctuation">}</span> 
 sum<span class="token operator">=</span><span class="token function">f</span><span class="token punctuation">(</span><span class="token number">0</span><span class="token punctuation">,</span>i1<span class="token number">-1</span><span class="token punctuation">)</span><span class="token punctuation">;</span><span class="token comment" spellcheck="true">//&#x8BA1;&#x7B97;&#x4E0D;&#x542B;&#x62EC;&#x53F7;&#x7684;&#x8868;&#x8FBE;&#x5F0F; </span>
  <span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">&quot;%d\n&quot;</span><span class="token punctuation">,</span>sum<span class="token punctuation">)</span><span class="token punctuation">;</span>
return 0;
}