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);
}
}