辛辛苦苦建树一晚上,T了六个点(雾),大佬帮我看看还有改的可能吗
#include<bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f; // 用来代指x
string s;
int m, q;
// 定义节点结构体
struct node{
int l, r; // 左右值
char symbol; // 节点符号
node* t, *f; // 指向真和假子树的指针
node(){
l = r = 0; // 初始化左右值为0
symbol = '0'; // 初始化符号为'0'
t = f = NULL; // 初始化子树指针为NULL
}
};
// 三目表达式,建树
int cnt = -1; // 计数器,用于遍历字符串
inline node* build(){
node* root = new node(); // 创建新节点
bool pass = false; // 标记是否已经读取到符号
for(cnt++; cnt<s.size(); cnt++){ // 遍历字符串
if(s[cnt]=='>'||s[cnt]=='<'){ // 如果是符号
root->symbol = s[cnt]; // 设置节点符号
pass = true; // 更新标记
}else if(s[cnt]>='0'&&s[cnt]<='9'){ // 如果是数字
if(pass){ // 如果已经读取到符号
root->r = root->r * 10 + s[cnt] - '0'; // 更新右值
}else{
root->l = root->l * 10 + s[cnt] - '0'; // 更新左值
}
}else if(s[cnt]=='x'){ // 如果是'x'
if(pass){
root->r = inf; // 设置右值为无穷大
}else{
root->l = inf; // 设置左值为无穷大
}
}else if(s[cnt]=='?'||s[cnt]==':'){ // 如果是三目运算符
if(s[cnt]=='?'){ // 如果是问号
root->t = build(); // 构建真子树
root->f = build(); // 构建假子树
return root; // 返回当前节点
}else{
return root; // 返回当前节点
}
}
}
return root; // 返回构建的树根节点
}
inline int check(node* root, int x){ // 检查给定值 x
if(root->symbol == '0'){ // 是叶子节点,返回值
return root->l;
}
if(root->l == inf){ // 如果左值为x
if(root->symbol == '>' && x>root->r || root->symbol == '<' && x<root->r){
return check(root->t, x); // 根据符号判断返回真子树的结果
}else{
return check(root->f, x); // 返回假子树的结果
}
}else if(root->r == inf){ // 如果右值为x
if(root->symbol == '<' && x>root->l || root->symbol == '>' && x<root->l){
return check(root->t, x); // 返回真子树的结果
}else{
return check(root->f, x); // 返回假子树的结果
}
}else{ // 如果左右值都有效
if(root->symbol == '>' && root->l>root->r || root->symbol == '<' && root->l<root->r){
return check(root->t, x); // 返回真子树的结果
}else{
return check(root->f, x); // 返回假子树的结果
}
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> m >> q;
cin >> s;
node* root = build(); // 构建树
while(q--){
int x;
cin >> x;
cout << check(root, x) << "\n";
}
return 0;
}