2 条题解

  • 0
    @ 2025-3-8 20:46:32
    #include <bits/stdc++.h>
    
    using u32 = unsigned;
    using i64 = long long;
    using u64 = unsigned long long;
    
    int main() {
    	std::ios::sync_with_stdio(false);
    	std::cin.tie(nullptr);
    
    	std::string s;
    	std::cin >> s;
    
    	std::vector<int> stk;
    	std::set<int> po;
    	for (int i = 0; i < s.size(); i ++) {
    		if (s[i] == '(') {
    			stk.push_back(i);
    		} else if (s[i] == ')') {
    			if (stk.size() == 0) {
    				po.insert(i);
    			} else {
    				stk.pop_back();
    			}
    		}
    	}
    
    	while (stk.size()) {
    		po.insert(stk.back());
    		stk.pop_back();
    	}
    
    
    	std::string t;
    	for (int i = 0; i < s.size(); i ++) {
    		if (!po.count(i)) {
    			t += s[i];
    		}
    	}
    	std::string p;
    	for (int i = 0; i < t.size(); i++) {
    		if (t[i] != '(') {
    			p += t[i];
    			continue;
    		}
    		if (t[i] == '(') {
    			int c = 0;
    			int j = i + 1;
    			while (j < t.size() && t[j] != ')') {
    				j++;
    				if (t[j] == '+' || t[j] == '-' || t[j] == '*' || t[j] == '/' || t[j] == '^') {
    					c++;
    				}
    			}
    			if (c < 1) {
    				for (int k = i + 1; k < j; k++) {
    					p += t[k];
    				}
    			} else {
    				for (int k = i; k <= j; k++) {
    					p += t[k];
    				}
    			}
    			i = j;
    		}
    	}
    	// std::cerr << t << " " << p << "\n";
    	std::stack<i64> dight;
    	std::stack<char> symbol;
    	auto calc = [&]() {
    		i64 a = dight.top();
    		dight.pop();
    		i64 b = dight.top();
    		dight.pop();
    		char c = symbol.top();
    		symbol.pop();
    		switch(c) {
    			case '+':dight.push(a + b); break;
    			case '-':dight.push(b - a); break;
    			case '*':dight.push(a * b); break;
    			case '/':dight.push(b / a); break;
    			case '^':dight.push(std::pow(a, b)); break;
    		}
    	};
    
    	auto level = [&](char c) -> int {
    		if (c == '+' || c == '-') return 1;
    		if (c == '*' || c == '/') return 2;
    		if (c == '^') return 3;
    		return 0;
    	};
    	i64 res = 0;
    	bool tag = false;
    	for (int i = 0; i < p.size(); i ++) {
    		if (p[i] >= '0' && p[i] <= '9') {
    			res = res * 10 + p[i] - '0';
    			tag = true;
    		} else {
    			//std::cerr << i << " " << tag << " " << symbol.size() << " " << dight.size() << "\n";
    			if (tag) {
    				dight.push(res);
    				res = 0;
    				tag = false;
    				// continue;
    			}
    			if (p[i] == '(') {
    				symbol.push(p[i]);
    				continue;
    			}
    			if (p[i] == ')') {
    				while (symbol.top() != '(') {
    					calc();
    				}
    				symbol.pop();
    				continue;
    			}
    			while (!symbol.empty() && level(p[i]) <= level(symbol.top())) {
    				calc();
    			}
    			symbol.push(p[i]);
    		}
    	}
    	//return 0;
    	if (tag) {
    		dight.push(res);	
    	}
    	while(!symbol.empty()) {
    		calc();
    	}
    	std::cout<< dight.top();
    
    	return 0;
    }
    
    
    • 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;
      }
      
      
      • 1

      信息

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