2 条题解

  • 0
    @ 2025-3-8 20:46:12
    #include <bits/stdc++.h>
    #define ll long long
    #define endl '\n'
    using namespace std;
    
    const int N = 1e5 + 5;
    string s;
    
    int nums(int l, int r) {
    	int cnt = 0;
    	for (int i = l; i <= r; i++) 
    		cnt = cnt * 10 + (s[i] - '0');		
    	return cnt;
    }
    
    int calc(int l, int r) {
    	
    	if (l > r) return 0;
    	
    	int pos1 = -1, pos2 = -1, pos3 = -1;  // ops1 : +-   ;    pos2 : */    ;    pos3 : ^
    	int cnt = 0;  // 标记左右括号
    	
    	for (int i = l; i <= r; i++) {
    		// 统计当前范围内的括号个数
    		if (s[i] == '(') cnt++;
    		if (s[i] == ')') cnt--;
    		// 定位这个范围内相应运算符号最后一次出现的地点(越早被定位,递归深度越浅,越晚被执行运算)   
    		// 这里是从递归角度出发确定相同优先级的运算符的执行顺序
    		if ((s[i] == '+' || s[i] == '-') && cnt == 0) pos1 = i;
    		if ((s[i] == '*' || s[i] == '/') && cnt == 0) pos2 = i;
    		if (s[i] == '^' && cnt == 0) pos3 = i;	
    	}
    	
    	// 在当前范围内没有符号的情况下,进行条件判断
    	if (pos1 == -1 && pos2 == -1 && pos3 == -1) {
    		//// 多余括号情况
    		// 左括号多余
    		if (cnt > 0 && s[l] == '(') return calc(l+1, r); 
    		// 右括号多余
    		else if (cnt < 0 && s[r] == ')') return calc(l, r-1);
    		
    		//// cnt == 0, 说明要么是数字,要么有一对括号括住它
    		else if (cnt == 0 && s[l] == '(' && s[r] == ')') return calc(l+1, r-1);
    		else return nums(l, r);	
    	}
    	
    	// 按优先级递归
     	if (pos1 != -1) {  //  + - 优先级最低
    		if (s[pos1] == '+') return calc(l, pos1-1) + calc(pos1+1, r);
    		if (s[pos1] == '-') return calc(l, pos1-1) - calc(pos1+1, r);
    	}
    	else if (pos2 != -1) {   // * / 优先级中等
    		if (s[pos2] == '*') return calc(l, pos2-1) * calc(pos2+1, r);
    		if (s[pos2] == '/') return calc(l, pos2-1) / calc(pos2+1, r);
    	}
    	else if (pos3 != -1) {   // ^ 优先级最高
    		return (int)pow(calc(l, pos3-1), calc(pos3+1, r));
    	}
    	
    	return 0;
    }
    
    int main () {
    	cin >> s;	
    	cout << calc(0, s.length()-1);
    
    	return 0;
    }
    
    

    信息

    ID
    188
    时间
    1000ms
    内存
    256MiB
    难度
    9
    标签
    递交数
    16
    已通过
    3
    上传者