CSP-202309-2 坐标变换（其二）(模拟，c++，vector建二叉树)

计算机软件能力认证考试系统

问题描述

解析：

参考来源：第31次CCF计算机软件能力认证 - ~Lanly~ - 博客园 (cnblogs.com)

从题目中可以看逆波兰式就是表达树的后序遍历，所以我们可以利用二叉树的递归遍历进行求解。

同时，我们可以利用vector向量建立二叉树，用链表也行，但是会比较麻烦。

具体请看代码：

#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<math.h>
#include<map>
#include<sstream>
using namespace std;
typedef long long LL;
#define CH 1
#define CONST 2
#define OP 3
const int mod = 1e9 + 7;
int n, m;
vector<int>lc;
vector<int>rc;
vector<int>info;
vector<int>kind;
stack<int>stk;
vector<int>a(200);
// 定义递归函数 solve，计算表达式树节点的值和导数
pair<int, int> solve(int u, int x) {
	if (kind[u] == CH) {
		return pair<int, int>{a[info[u]], (info[u] == x)};
	}
	else if (kind[u] == CONST) {
		return pair<int, int>{info[u], 0};
	}
	else {
		auto lans = solve(lc[u], x), rans = solve(rc[u], x);
		int sum = 0, dsum = 0;
		if (info[u] == '+') {
			sum = lans.first + rans.first;
			dsum = lans.second + rans.second;
		}
		else if (info[u] == '-') {
			sum = lans.first - rans.first;
			dsum = lans.second - rans.second;
		}
		else {
			sum = 1ll*lans.first * rans.first % mod;
			dsum = (1ll*lans.first * rans.second%mod + 1ll*lans.second * rans.first%mod);//1ll 是一种常见的编码技巧，用于将数字字面量转换为长长整型（long long）类型。
		}
		sum = (sum % mod + mod) % mod;
		dsum = (dsum % mod + mod) % mod;
		return pair<int, int>{sum, dsum};
	}
}
int main() {
	cin >> n >> m;
	string s;
	getline(cin, s);
	getline(cin, s);
	int cnt = 0;
	istringstream q(s);
	//q 是一个 istringstream 对象，用于从字符串中读取数据。

	//getline(qwq, s, ' ') 是 C++ 中的输入流操作，
	//用于从输入流 qwq 中读取一行（以换行符 '\n' 结束的一行）并存储到字符串 s 中，
	//直到遇到指定的分隔符（在这里是空格 ' '）为止。

	while (getline(q, s, ' ')) {
		if (s.size() == 1 && (s[0] == '+' || s[0] == '*' || s[0] == '-')) {
			int rson = stk.top();
			stk.pop();
			int lson = stk.top();
			stk.pop();
			lc.push_back(lson);
			rc.push_back(rson);
			info.push_back(s[0]);
			kind.push_back(OP);
			stk.push(cnt);
			cnt++;
		}
		else if (s[0] == 'x') {
			int x = stoi(s.substr(1));//subStr 是从第二个字符开始的子串,stoi 将其转换为整数。
			x--;
			lc.push_back(-1);
			rc.push_back(-1);
			info.push_back(x);
			kind.push_back(CH);
			stk.push(cnt);
			cnt++;
		}
		else {
			int x = stoi(s);
			lc.push_back(-1);
			rc.push_back(-1);
			info.push_back(x);
			kind.push_back(CONST);
			stk.push(cnt);
			cnt++;
		}
	}
	int root = stk.top();
	// 处理每个查询
	for (int i = 1; i <= m; i++) {
		int x;
		cin >> x;
		x--;//由于我们是从0开始记录，所以这里要-1
		for (int j = 0; j < n; j++) {
			cin >> a[j];
		}
		cout << solve(root, x).second << endl;
	}
	return 0;
}