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;
    }
    
    

    信息

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