返回顶部

收藏

两种方法计算“算术表达式”

更多

一种是转化为后缀表达式(边转化边计算,对于括号、优先级都要进行处理,也就是利用堆栈才行);一种则是结合递归(有括号时,括号内的就是子表达式)和排序(无括号时 ,循环计算到结果,每次都计算最高优先级(多个则取最左端)的运算符)计算

优先级判定函数

namespace My_Usual_Space{

    inline char _OprRgt_(char o)
    {
        switch(o)
        {
            case '('://左括号
                return 1;
            case '&'://按位并 
            case '|'://按位或 
            case '^'://按位异或 
                return 2;
            case '+'://加 
            case '-'://减 
                return 3;
            case '*'://乘 
            case '/'://整除 
            case '%'://取余 
                return 4;
            case '~'://按位取反
            case '$'://取绝对值
            case '!'://除零皆零
            case '@'://非零皆一
                return 5;
            case ')'://右括号 
                return 6;
            default ://不是运算符 
                return 0; 
        }
    }
}

后缀表达式堆栈版

long Calc(char s[])
{

    long ans[16];
    char opr[16];
    char c,i,j,k;
    long d;

    if(!s || !*s)return 0;
    (i=-1,j=0,opr[0]='(');
    while(c=*s)
    {
        while(IsSpace(c))(s++,c=*s);
        if(IsDigit(c))
        {
            i++;
            s+=StoL(d,s);
            ans[i]=d;
        }
        else
        {
            if(s[-1]=='(')
            {
                if(c=='-')
                {
                    (s++,c=*s);
                    if(IsDigit(c))
                    {
                        i++;
                        s+=StoL(d,s);
                        ans[i]=-d;
                        continue;
                    }
                    else return 0;
                }
                else if(c=='+')
                {
                    (s++,c=*s);
                    if(IsDigit(c))
                    {
                        i++;
                        s+=StoL(d,s);
                        ans[i]=d;
                        continue;
                    }
                    else return 0;
                }
            }
            if(k=My_Usual_Space::_OprRgt_(c))
            {
                if(k==1)
                {
                    j++;
                    opr[j]=c;
                }
                else if(k==6)
                {
                    while(j && opr[j]!='(')
                    {
                        d=ans[i];
                        switch(opr[j])
                        {
                            case '&':ans[i-1]&=d;i--;
                            break;
                            case '|':ans[i-1]|=d;i--;
                            break;
                            case '^':ans[i-1]^=d;i--;
                            break;
                            case '+':ans[i-1]+=d;i--;
                            break;
                            case '-':ans[i-1]-=d;i--;
                            break;
                            case '*':ans[i-1]*=d;i--;
                            break;
                            case '/':ans[i-1]/=d;i--;
                            break;
                            case '%':ans[i-1]%=d;i--;
                            break;
                            case '~':ans[i]=~d;
                            break;
                            case '$':if(d<0)ans[i]=-d;
                            break;
                            case '!':ans[i]=d?0:1;
                            break;
                            case '@':ans[i]=d?1:0;
                            break;
                        }
                        j--;
                    }
                    if(j)j--;else return 0;
                }
                else
                {
                    while(k<=My_Usual_Space::_OprRgt_(opr[j]))
                    {
                        d=ans[i];
                        switch(opr[j])
                        {
                            case '&':ans[i-1]&=d;i--;
                            break;
                            case '|':ans[i-1]|=d;i--;
                            break;
                            case '^':ans[i-1]^=d;i--;
                            break;
                            case '+':ans[i-1]+=d;i--;
                            break;
                            case '-':ans[i-1]-=d;i--;
                            break;
                            case '*':ans[i-1]*=d;i--;
                            break;
                            case '/':ans[i-1]/=d;i--;
                            break;
                            case '%':ans[i-1]%=d;i--;
                            break;
                            case '~':ans[i]=~d;
                            break;
                            case '$':if(d<0)ans[i]=-d;
                            break;
                            case '!':ans[i]=d?0:1;
                            break;
                            case '@':ans[i]=d?1:0;
                            break;
                        }
                        j--;
                    }
                    (j++,opr[j]=c);
                }
                s++;
            }
            else return 0;
        }
    }
    while(j>0)
    {
        d=ans[i];
        switch(opr[j])
        {
            case '&':ans[i-1]&=d;i--;
            break;
            case '|':ans[i-1]|=d;i--;
            break;
            case '^':ans[i-1]^=d;i--;
            break;
            case '+':ans[i-1]+=d;i--;
            break;
            case '-':ans[i-1]-=d;i--;
            break;
            case '*':ans[i-1]*=d;i--;
            break;
            case '/':ans[i-1]/=d;i--;
            break;
            case '%':ans[i-1]%=d;i--;
            break;
            case '~':ans[i]=~d;
            break;
            case '$':if(d<0)ans[i]=-d;
            break;
            case '!':ans[i]=d?0:1;
            break;
            case '@':ans[i]=d?1:0;
            break;
        }
        j--;
    }
    return ans[0];
}

递归循环计算版(已经整理成了非递归)

long Exec(char *s)
{
    struct List
    {
        char  typ;
        union
        {
            long vlu;
            char opr;
        };
        List *lst;
        List *nxt;
    };
    struct
    {
        long  ans;
        List *lft;
        List *equ;
        List *rgt;
    }stk[2];
    List *sp,*sl,*so,*sr;
    char p,t,v;

    if(!s || !*s)return 0;
    //以下将字符串分割成一连串的元素(括号、运算符、数字) 
    sp=stk->equ=new List;
    while(p=*s)
    {
        if(IsDigit(p))
        {
            sp->nxt=new List;
            sp->nxt->lst=sp;
            sp=sp->nxt;
            sp->typ=0;
            s+=StoL(sp->vlu,s);//和Calc里面的那个同一个函数
        }
        else if(My_Usual_Space::_OprRgt_(p))
        {
            sp->nxt=new List;
            sp->nxt->lst=sp;
            sp=sp->nxt;
            sp->opr=p;
            sp->typ=1;
            s++;
        }
        else
        {
            (sp->nxt=NULL,sp=stk->equ);
            while(sp)(sr=sp->nxt,delete sp,sp=sr);
            return 0;
        }
    }
    sp->nxt=NULL;
    (sp=stk->equ,stk->equ=sp->nxt);
    (delete sp,stk->equ->lst=NULL);
    //以下进行计算,采用递归的方式 
    p=0;
    while(1)
    {
        sp=stk[p].equ;
        //如果母算式存在括号,则进入递归途径,求值括号内的子算式(必然无括号) 
        if(!p)
        {
            for(sr=sp->nxt;sr && !(sr->typ && sr->opr==')');sr=sr->nxt);
            if(sr)
            {
                for(sl=sr->lst;sl && !(sl->typ && sl->opr=='(');sl=sl->lst);
                if(sl)
                {
                    sl->nxt->lst=NULL;
                    sr->lst->nxt=NULL;
                    (p++,stk[p].equ=sl->nxt,stk[p].lft=sl);
                    if(sr->nxt)
                    {
                        stk[p].rgt=sr->nxt;
                        sl->nxt=sr->nxt;
                        sr->nxt->lst=sl;
                    }
                    else
                    {
                        stk[p].rgt=NULL;
                        sl->nxt=NULL;
                    }
                    delete sr;
                    sl->typ=0;
                    continue;
                }
                else
                {
                    sp=stk->equ;
                    while(sp)(sr=sp->nxt,delete sp,sp=sr);
                    return 0;
                }
            }
        }
        //此处是为了去除正负号 
        if(sp->typ)
        {
            if(sp->nxt->typ==0)
            {
                if(sp->opr=='+')
                {
                    (stk[p].equ=sp->nxt,delete sp,sp=stk[p].equ,sp->lst=NULL);
                }
                else if(stk[p].equ->opr=='-')
                {
                    (stk[p].equ=sp->nxt,delete sp,sp=stk[p].equ,sp->lst=NULL);
                    sp->vlu=-(sp->vlu);
                }
            }
            else
            {
                while(p>=0)
                {
                    sp=stk[p].equ;
                    while(sp)(sr=sp->nxt,delete sp,sp=sr);
                    p--;
                }
                return 0;
            }
        }
        //进入循环解算式过程 
        do
        {
            (t=0,so=NULL,sl=sp->nxt);
            while(sl)//根据优先级、左结合确定计算顺序 
            {

                if(sl->typ)
                {
                    v=My_Usual_Space::_OprRgt_(sl->opr);
                    if(t<v)(t=v,so=sl);
                }
                sl=sl->nxt;
            }
            if(t)
            {
                sr=so->nxt;
                if(sr && sr->typ==0)
                {
                    if(t<5)//二元运算符 
                    {
                        sl=so->lst;
                        if(sl && sl->typ==0)
                        {
                            switch(so->opr)
                            {
                                case '&':sl->vlu &= sr->vlu;
                                break;
                                case '|':sl->vlu |= sr->vlu;
                                break;
                                case '^':sl->vlu ^= sr->vlu;
                                break;
                                case '+':sl->vlu += sr->vlu;
                                break;
                                case '-':sl->vlu -= sr->vlu;
                                break;
                                case '*':sl->vlu *= sr->vlu;
                                break;
                                case '/':sl->vlu /= sr->vlu;
                                break;
                                case '%':sl->vlu %= sr->vlu;
                                break;
                            }
                            sl->nxt=sr->nxt;
                            if(sr->nxt)sr->nxt->lst=sl;
                            delete so;
                            delete sr;
                        }
                        else
                        {
                            while(p>=0)
                            {
                                sp=stk[p].equ;
                                while(sp)(sr=sp->nxt,delete sp,sp=sr);
                                p--;
                            }
                            return 0;
                        }
                    }
                    else//一元运算符 
                    {
                        switch(so->opr)
                        {
                            case '~':so->vlu=~(sr->vlu);
                            break;
                            case '$':so->vlu=sr->vlu < 0 ? - sr->vlu : sr->vlu;
                            break;
                            case '!':so->vlu=sr->vlu?0:1;
                            break;
                            case '@':so->vlu=sr->vlu?1:0;
                            break;
                        }
                        so->typ=1;
                        so->nxt=sr->nxt;
                        if(sr->nxt)sr->nxt->lst=so;
                        delete sr;
                    }
                }
                else
                {
                    while(p>=0)
                    {
                        sp=stk[p].equ;
                        while(sp)(sr=sp->nxt,delete sp,sp=sr);
                        p--;
                    }
                    return 0;
                }
            }
        }
        while(t);
        stk[p].ans=sp->vlu;
        delete sp;
        if(p)
        {
            stk[p].lft->vlu=stk[p].ans;
            p--;
        }
        else return stk->ans;
    }
}

标签:c++

收藏

0人收藏

支持

0

反对

0

»更多 您可能感兴趣的代码
  1. 2017-07-23 12:42:20奇数魔方阵 by Kevin.
  2. 2015-09-09 16:29:06将jpg转换为bmp格式的文件 by qqmmcc
  3. 2015-09-09 09:29:49可执行文件加密 by walker30
  4. 2015-09-08 18:42:46TCP端口占用查询 by 灵剑子
  5. 2015-09-08 14:16:34Luffar schack五子棋 by 蟋蟀哥
  6. 2015-09-08 10:39:34wav转mp3的程序 by 灵剑子
  7. 2015-09-05 16:54:59逐行搜索目录中的文件内容并输出到Excel by 蟋蟀哥
  8. 2015-09-03 20:10:15LZW+AES+Base64编码解码剪贴板文本 by 童学芬
  9. 2015-09-01 17:47:21猫里奥 by aiheng1988
  10. 2015-08-31 15:33:59模拟键盘操作发送字符串 by 千万不要郁闷
  11. 2018-11-08 19:35:43Python实现截屏的函数 by 司马

发表评论