P10473

#include<bits/stdc++.h>
using namespace std;
struct tree {
	long long ls;
	long long rs;
	char op='A';
	long long num=pow(2,50)+1;
} node[50];
struct Nxt {
	char op;
	long long id;
} nxt[50];
long long qaq[50];
long long poo[50];
long long top=1;
string s;
bool check(long long id){
	if(s[id]=='('||s[id]==')')return true;
	else return false;
}
long long find(long long l,long long r){
	long long k=0;
	for(long long i=l;i<=r;i++){
		if(s[i]=='('){i=qaq[i];continue;}
		if(s[i]=='-'&&!(s[i-1]<='9'&&s[i-1]>='0'))continue;
		if(s[i]=='+'||s[i]=='-')k=i;
	}
	if(k)return k;
	for(long long i=l;i<=r;i++){
		if(s[i]=='('){i=qaq[i];continue;}
		if(s[i]=='*'||s[i]=='/')k=i;
	}
	if(k)return k;
	for(long long i=l;i<=r;i++){
		if(s[i]=='('){i=qaq[i];continue;}
		if(s[i]=='^')k=i;
	}
	return k;
}
long long getnum(long long l,long long r){
	long long num=0;
	for(long long i=l;i<=r;i++){
		num=num*10+s[i]-'0';
	}
	return num;
}
void buildtree(long long fa,long long l,long long r,long long id) {
	long long k,l1=l,r1=r;
	while(s[l1]=='('&&qaq[l1]==r1)l1++,r1--;
	k=find(l1,r1);
	if(s[l1]=='-'){
		node[id].num=0-getnum(l1+1,r1);
		return ;
	}
//	cout<<l1<<" "<<r1<<endl<<k<<endl;
	if(k==0){
//		cout<<l1<<" "<<r1<<endl;
		node[id].num=getnum(l1,r1);
		return ; 
	}
	node[id].op=s[k];
	node[id].ls=++top;
	buildtree(id,l1,k-1,top);
	node[id].rs=++top;
	buildtree(id,k+1,r1,top);
}
void del() {
	long long l=0,r=s.size()-1;
	stack<Nxt> st;
	for(long long i=l; i<=r; i++) {
		if(!check(i))continue;
		if(!st.empty()) {
			char op1=s[i];
			Nxt op2=st.top();
			qaq[op2.id]=i;
			if(int(op1)-int(op2.op)!=0) {
				st.pop();
				if(s[op2.id+1]=='('&&s[i-1]==')')poo[op2.id]=1,poo[i]=1;
			}
			else st.push({s[i],i});
		}
		else st.push({s[i],i});
	}
	string s2="";
	for(long long i=l; i<=r; i++) {
		if(!poo[i])s2+=s[i];
	}
	s=s2;
}
long long cal(long long a,long long b,char op){
	if(op=='+')return a+b;
	if(op=='-')return a-b;
	if(op=='*')return a*b;
	if(op=='/')return a/b;
	if(op=='^')return pow(a,b);
}
long long bfstree(long long root){
	if(root==0)return 0;
	if(node[root].ls==0&&node[root].rs==0)return node[root].num;
	return cal(bfstree(node[root].ls),bfstree(node[root].rs),node[root].op);
}
bool kong(tree A){
	if(A.num==pow(2,50)+1&&A.op=='A'&&A.ls==0&&A.rs==0)return true;
	else return false;
}
signed main() {
	cin>>s;
	del();
	buildtree(0,0,s.size()-1,1);
//	for(int i=1;!kong(node[i]);i++){
//		cout<<i<<":"<<node[i].op<<" "<<node[i].num<<" "<<node[i].ls<<" "<<node[i].rs<<endl;
//	}
	long long ans=bfstree(1);
	cout<<ans;
	return 0;
}

思路

建表达式树

采用特判处理负数

递归求解数值