首页 > 代码库 > 表达式解析[笛卡尔树]
表达式解析[笛卡尔树]
2178 表达式运算Cuties
时间限制: 1 s
空间限制: 32000 KB
题目等级 : 大师 Master
题目描述 Description
给出一个表达式,其中运算符仅包含+,-,*,/,^要求求出表达式的最终值
数据可能会出现括号情况 还有可能出现多余括号情况
数据保证不会出现>maxlongint的数据
数据可能回出现负数情况
输入描述 Input Description
仅一行，即为表达式
输出描述 Output Description
仅一行，既为表达式算出的结果
样例输入 Sample Input
(2+2)^(1+1)
样例输出 Sample Output
16
数据范围及提示 Data Size & Hint
表达式总长度<=30
就是练习一下笛卡尔树
多余括号太坑了，这个程序还没有处理()-1
负数我在前面加了一个0
#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>#include <cmath>using namespace std;const int N=35,MOD=10007;typedef long long ll;int n;char s[N];struct node{ int lc,rc; char op; ll num; node():lc(0),rc(0),num(0){}}t[N];int w[N],root,cnt=0;void build(){ int p=0; for(int i=1;i<=n;i++){//printf("i %d %c\n",i,s[i]); if(s[i]==‘(‘) {p++;continue;} if(s[i]==‘)‘) {p--;continue;} if(s[i]==‘+‘|| (s[i]==‘-‘&&i!=1&&s[i-1]!=‘(‘) ) w[++cnt]=p*4+1,t[cnt].op=s[i]; else if(s[i]==‘*‘||s[i]==‘/‘) w[++cnt]=p*4+2,t[cnt].op=s[i]; else if(s[i]==‘^‘) w[++cnt]=p*4+3,t[cnt].op=s[i]; else{ if(s[i]==‘-‘){//cout<<"p"; w[++cnt]=p*4+4; t[cnt].op=‘a‘;t[cnt].num=0; w[++cnt]=p*4+1,t[cnt].op=‘-‘; if(s[i+1]<‘0‘||s[i+1]>‘9‘) continue; i++; } //printf("num %d %c\n",i,s[i]); w[++cnt]=p*4+4; ll x=0; while(s[i]>=‘0‘&&s[i]<=‘9‘) x=x*10+s[i]-‘0‘,i++; i--; t[cnt].num=x; t[cnt].op=‘a‘; } //printf("build %d %d %c %d\n",cnt,w[cnt],t[cnt].op,t[cnt].num); } int st[N],top=0; for(int i=1;i<=cnt;i++){ int k=top; while(k>0&&w[st[k]]>=w[i]) k--; if(k) t[st[k]].rc=i; if(k<top) t[i].lc=st[k+1]; st[++k]=i; top=k;//printf("st %d %c %d\n",top,t[st[top]].op,w[st[top]]); } root=st[1];}inline ll fpow(ll a,ll b){ ll ans=1; for(;b;b>>=1,a*=a) if(b&1) ans*=a; return ans;}ll cal(int u){ char c=t[u].op; if(c==‘a‘) return t[u].num; ll t1=cal(t[u].lc),t2=cal(t[u].rc);//printf("cal %d %d %c %d\n",u,t1,c,t2); if(c==‘+‘) return t1+t2; if(c==‘-‘) return t1-t2; if(c==‘*‘) return t1*t2; if(c==‘/‘) return t1/t2; if(c==‘^‘) return fpow(t1,t2);}int main(){ scanf("%s",s+1); n=strlen(s+1); build(); printf("%lld",cal(root));}
表达式解析[笛卡尔树]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。