【算法】表达式求值

x33g5p2x  于2022-02-07 转载在 其他  
字(1.0k)|赞(0)|评价(0)|浏览(210)

表达式求值:一个只有+,-,*,/的表达式,没有括号

一种神奇的做法:使用数组存储数字和运算符,先把优先级别高的乘法和除法计算出来,再计算加法和减法

int GetVal(string s){
    int A[10000];
    int Num=0,Pos=0;
    for(int i=0;i<s.size();i++){                //字符串转数字
        if(s[i]>='0'&&s[i]<='9'){
            Num=Num*10+s[i]-'0';
        }
        else{
            A[Pos]=Num;A[Pos+1]=s[i];
            Pos+=2;
            Num=0;
        }
    }
    A[Pos]=Num;Pos++;
    /*for(int i=0;i<Pos;i++){
        if(i%2==0)printf("A[%d]=%d\n",i,A[i]);
        else printf("A[%d]='%c'\n",i,A[i]);
    }*/
    for(int i=0;i<Pos;i++){                              //乘除法
        if(i%2==1/*operator*/&&A[i]=='*'){
            A[i-1]=A[i-1]*A[i+1];
            for(int j=i;j<Pos;j++)A[j]=A[j+2];
            Pos-=2;
        }
        if(i%2==1/*operator*/&&A[i]=='/'){
            A[i-1]=A[i-1]/A[i+1];
            for(int j=i;j<Pos;j++)A[j]=A[j+2];
            Pos-=2;
        }
    }
    /*for(int i=0;i<Pos;i++){
        if(i%2==0)printf("A[%d]=%d\n",i,A[i]);
        else printf("A[%d]='%c'\n",i,A[i]);
    }*/
    int Ans=A[0];
    for(int i=0;i<Pos;i++){                            //加减法
        if(i%2==1&&A[i]=='-')Ans-=A[i+1];
        if(i%2==1&&A[i]=='+')Ans+=A[i+1];
    }
    return Ans;
}

使用一个数组A[],A[]的0,2,4...(偶数)位存储数字,1,3,5...(奇数)位存储符号。
然后先把符号是乘法,除法的东西计算出来,对奇数位进行操作,然后再移动。
同理,最后计算加减法。
结束。

相关文章

微信公众号

最新文章

更多