为什么这道题用分治会MLE三个点啊
查看原帖
为什么这道题用分治会MLE三个点啊
367782
414sboy楼主2021/7/16 16:56
#include <iostream>
#include <string>
using namespace std;
char ar[200];
string str;
int stack[200];
int iter=0;
inline void fun(int l,int r){
    while(str[l]=='(' && str[r]==')') l++,r--;
    if(l==r){
        iter++;
        ar[iter]=str[l];
        return;
    }
    int num=0;
    int t=-1;
    for(int i=l;i<=r;i++){
        if(str[i]=='(') num++;
        if(str[i]==')') num--;
        if(num!=0) continue;
        if((str[i]>='0' && str[i]<='9') || str[i]==')') continue;
        if(t==-1 || (str[i]=='^' && str[t]=='^')) t=i;
        if(t==-1 || ((str[i]=='*' || str[i]=='/') && (str[t]!='+' && str[t]!='-'))) t=i;
        if(str[i]=='+' || str[i]=='-') t=i;
        //if(str[i]=='+' || str[i]=='-' || str[i]=='*' || str[i]=='/' || str[i]=='^') t=i;
    }
    //if(t==-1) while(true) int n=0;
    fun(l,t-1);
    fun(t+1,r);
    iter++;
    ar[iter]=str[t];
}
int main(){
    cin >> str;
    fun(0,str.size()-1);
    for(int i=1;i<=iter;i++) cout << ar[i] << ' ';
    cout << endl;
    int top=0;
    for(int i=1;i<=iter;i++){
    	if(ar[i]>='0' && ar[i]<='9'){
    		top++;
    		stack[top]=ar[i]-'0';
		}else{
			int num=1;
			int f=stack[top-1],b=stack[top];
			if(ar[i]=='+') num=f+b;
			if(ar[i]=='-') num=f-b;
			if(ar[i]=='*') num=f*b;
			if(ar[i]=='/') num=f/b;
			if(ar[i]=='^') for(int i=1;i<=b;i++) num*=f;
			top--;stack[top]=num;
			for(int j=1;j<=top;j++) cout << stack[j] << ' ';
			for(int j=i+1;j<=iter;j++) cout << ar[j] << ' ';
			cout << endl;
		}
	}
    return 0;
}
2021/7/16 16:56
加载中...