欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

表达式树

程序员文章站 2022-05-19 21:33:13
...

1. 笔记
表达式树是一种存储和计算表达式的方式。表达式树的叶子结点均为数,非叶子结点均为运算符。我自己摸索了一下用表达式树处理表达式,确实很直观方便。下面的代码可以处理+,-,*,/,%,^六种左结合的二元运算,优先级为:

运算符 优先级
+,- 3
*,/,% 2
^ 1
其它 0

2. 代码

/*
备注:
未严格测试,可能有bug
2018/09/09
*/
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define ms(arr,a) memset(arr,a,sizeof arr)
#define debug(x) cout<<"< "#x" = "<<x<<" >"<<endl
int pri[300];
void init_pri()
{
    pri['+']=pri['-']=3;
    pri['*']=pri['/']=pri['%']=2;
    pri['^']=1;
}
struct node
{
    double v;
    char c;
    node *fa,*l,*r;
    node(){c=v=0;fa=l=r=NULL;}
    node(double x){v=x;c=0;fa=l=r=NULL;}
    node(char x){v=0;c=x;fa=l=r=NULL;}
};
void recycle(node *root)
{
    if(root==NULL)return;
    recycle(root->l);recycle(root->r);
    delete root;
}

const int maxn=1e3;
char s[maxn];
const double eps=1e-10;
inline bool is_num(char *i)
{
    return ((*i)>='0'&&(*i)<='9')||(*i)=='.';
}
double get_num(char *&i)
{
    bool is_f=false;double it=0.1;
    double ret=0;
    for(;is_num(i);++i)
    {
        if((*i)=='.'){is_f=true;continue;}
        if(is_f)
        {
            ret=ret+((*i)-'0')*it;
            it=it/10;
        }else ret=ret*10+(*i)-'0';
    }
    i--;
    return ret;
}
double calc(node *root)
{
    if(root->c==0)return root->v;
    double lft=calc(root->l),rgt=calc(root->r);
    switch(root->c)
    {
    case '+':
        return lft+rgt;
        break;
    case '-':
        return lft-rgt;
        break;
    case '*':
        return lft*rgt;
        break;
    case '/':
        return lft/rgt;
        break;
    case '%':
        return int(lft)%int(rgt);
        break;
    case '^':
        return pow(lft,rgt);
        break;
    }
}
node* construct(char *l,char *r)
{
    node *pos=NULL,*nxt,*root;
    for(char *i=l;i<=r;++i)
    {
        //构造新结点
        if((*i)=='(')
        {
            char *lft=i+1;
            int cnt=1;
            while(cnt)
            {
                i++;
                if((*i)=='(')cnt++;
                if((*i)==')')cnt--;
            }
            nxt=construct(lft,i-1);
            double tmp=calc(nxt);
            recycle(nxt);
            nxt=new node(tmp);
        }
        else if(is_num(i))nxt=new node(get_num(i));
        else nxt=new node((*i));
        //插入新结点
        node *a=pos,*b=NULL;
        pos=nxt;
        if(a==NULL){root=nxt;continue;}
        while(a&&pri[a->c]<=pri[nxt->c]){b=a;a=a->fa;}
        if(a==NULL){root=nxt;nxt->l=b;b->fa=nxt;continue;}
        if(b==NULL){a->r=nxt;nxt->fa=a;continue;}
        if(b==a->l)a->l=nxt;
        else a->r=nxt;
        nxt->fa=a;nxt->l=b;b->fa=nxt;
    }
    return root;
}
int main()
{
    init_pri();
    printf(">");
    while(~scanf("%s",s))
    {
        node *root=construct(s,s+strlen(s)-1);
        double ans=calc(root);
        long long nans=(long long)ans;
        if((ans-nans<eps)&&(ans-nans>-eps))printf("%lld",nans);
        else printf("%.6f",ans);
        printf("\n\n>");
        recycle(root);
    }
}