求调玄关!感激不尽
查看原帖
求调玄关!感激不尽
1173402
yfhshtk楼主2024/8/22 15:15
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
string s;
stack<int> a;
stack<char> b;
int num;
bool flag;
int qp(int a, int n) {
	int ans = 1;
	while(n) {
		if(n & 1) ans *= a;
		n = (n >> 1), a *= a;
	}
	return ans;
}
int check(char ch) {
	if(ch == '+' || ch == '-') return 0;
	else if(ch == '*' || ch == '/') return 1;
	else if(ch == '^') return 2;
}
bool is_num(char ch) {
	return (ch >= '0' && ch <= '9');
}
int solve(char ch, int x, int y) {
	if(ch == '+') return x + y;
	else if(ch == '-') return x - y;
	else if(ch == '*') return x * y;
	else if(ch == '/') return x / y;
	else if(ch == '^') return qp(x, y);//x的y次方 
}
void Clean() {
	stack<int> left;
	s = '(' + s + ')';
	for(int i = 0; i < s.size(); ++i) {
		if(s[i] == '-' && s[i - 1] == '(') s.insert(i, "0");
	}
	s.erase(0, 1);
	s.erase(s.size() - 1, 1);	
	for(int i = 0; i < s.size(); ++i) {
		if(s[i] == '(') left.push(i);
		else if(s[i] == ')') {
			if(left.empty()) s.erase(i, 1),  --i;
			else left.pop();
		}
	}
	while(!left.empty()) {
		s.erase(left.top(), 1);
		left.pop();
	}
	return ;
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> s;
	Clean();
	for(int i = 0; i < s.size(); ++i) {
		if(is_num(s[i])) {
			num = num * 10 + s[i] - '0';
			flag = 1;
		}
		else {
			a.push(num);
			num = 0;
			flag = 0;
			if(s[i] == '(') {
				b.push(s[i]);
			}
			else if(s[i] == ')') {
				while(b.top() != '(') {
					int y = a.top();
					a.pop();
					int x = a.top();
					a.pop();
					a.push(solve(b.top(), x, y));
					b.pop();
				}
				b.pop();
			}
			else {
				if(b.empty() || (b.top() == '(') || (!b.empty() && s[i] == '^' && b.top() == '^') || (!b.empty() && check(s[i]) > check(b.top()))) {
					b.push(s[i]);
				}
				else {
					while(!b.empty() && b.top() != '(' && (check(s[i]) <= check(b.top()))) {
						int y = a.top();
						a.pop();
						int x = a.top();
						a.pop();
						a.push(solve(b.top(), x, y));
						b.pop();
					}
					b.push(s[i]);
				}
			}
		}
	}
	if(flag) {
		a.push(num);
	}
	while(!b.empty()) {
		int y = a.top();
		a.pop();
		int x = a.top();
		a.pop();
		a.push(solve(b.top(), x, y));
		b.pop();
	}
	cout << a.top();
	return 0;
}
2024/8/22 15:15
加载中...