首页 > 其他分享 >括号转树的模板

括号转树的模板

时间:2024-05-04 17:11:06浏览次数:28  
标签:lchild ans rx 括号 depth 转树 rchild include 模板

电子书板子:






希冀平台:

#include<iostream>
#include<vector>
#include<algorithm>
#include<math.h>
#include<sstream>
#include<string>
#include<string.h>
#include<iomanip>
#include<stdlib.h>
#include<map>
#include<queue>
#include<limits.h>
#include<climits>
#include<fstream>
#include<stack>
#include<set>
typedef long long ll;
using namespace std;


//int ans = 0;
//struct BTNode
//{
//	int data;
//	int depth;
//	BTNode* lchild;
//	BTNode* rchild;
//	BTNode() { lchild = rchild = NULL; depth = 0; }
//	BTNode(int s)
//	{
//		lchild = rchild = NULL;
//		depth = 0;
//		data = s;
//	}
//};
//class Btree
//{
//public:
//	BTNode* r;
//	Btree() { r = NULL; }
//	void CreateBtree(string str)
//	{
//		stack<BTNode*>st;
//		BTNode* p;
//		bool flag = 0;
//		int i = 0;
//		int his = 0;
//		int ans = 0;
//		while (i < str.length())
//		{
//			switch (str[i])
//			{
//			case'(':
//				st.push(p);
//				flag = true;
//				break;
//			case')':
//				st.pop();
//				break;
//			case',':
//				flag = false;
//				break;
//			default:
//				ans = ans * 10 + str[i] - '0';
//				if(i+1<str.length() and (str[i+1]>'9' or str[i+1]<'0'))
//				{
//					p = new BTNode(ans);
//					ans = 0;
//					if (r == NULL)r = p;
//					else
//					{
//						if (flag and !st.empty())
//							st.top()->lchild = p;
//						else if (!st.empty())
//							st.top()->rchild = p;
//					}
//				}
//				break;
//			}
//			i++;
//		}
//		return;
//	}
//	void init(BTNode *s)
//	{
//		if (s->lchild and s->rchild)
//		{
//			init(s->lchild); init(s->rchild);
//			s->depth = max(s->lchild->depth, s->rchild->depth) + 1;
//
//		}
//		else if (s->lchild)
//		{
//			init(s->lchild);
//			s->depth = s->lchild->depth + 1;
//		}
//		else if (s->rchild)
//		{
//			init(s->rchild);
//			s->depth = s->rchild->depth + 1;
//		}
//		else s->depth = 0;
//		return;
//	}
//	void findans(BTNode* rx)
//	{
//		if (rx->lchild and rx->rchild)
//		{
//			ans = max(ans, rx->lchild->depth + rx->rchild->depth + 2);
//			findans(rx->lchild); findans(rx->rchild);
//		}
//		else if (rx->lchild)
//		{
//			ans = max(ans, rx->lchild->depth + 1);
//			findans(rx->lchild);
//		}
//		else if (rx->rchild)
//		{
//			ans = max(ans, rx->rchild->depth + 1);
//			findans(rx->rchild);
//		}
//		return ;
//	}
//};
//
//int main()
//{
//	freopen("in.txt", "r", stdin);
//	string s;
//	cin >> s;
//	Btree B;
//	B.CreateBtree(s);
//	B.init(B.r);
//	B.findans(B.r);
//	cout << ans;
//	return 0;
//}




/*t1:record*/
struct BTNode
{
	int data;
	BTNode* lchild;
	BTNode* rchild;
	BTNode() { lchild = rchild = NULL; }
	BTNode(int d)
	{
		data = d;
		lchild = rchild = NULL;
	}
};
class BTree
{
public:
	BTNode* r; queue<int>q1; stack<int>s2;
	BTree() { r = NULL; }
	void CreateBTree(string str)
	{
		stack<BTNode*>st;
		BTNode* p;
		int ans = 0;
		bool flag;
		int i = 0;
		while (i < str.length())
		{
			switch (str[i])
			{
			case '(':
				st.push(p);
				flag = true;
				break;
			case ')':
				st.pop();
				break;
			case ',':
				flag = false;
				break;
			default:
				ans = ans * 10 + str[i] - '0';
				if(i+1<str.length() and (str[i+1]>'9' or str[i+1]<'0'))
				{
					p = new BTNode(ans);
					ans = 0;
					if (r == NULL)r = p;
					else
					{
						if (flag and !st.empty())
							st.top()->lchild = p;
						else if (!st.empty())
							st.top()->rchild = p;
					}
				}
				break;
			}
			i++;
		}
	}
	void bljd(BTNode *now)
	{
		if (now->lchild != NULL)bljd(now->lchild);
		if (now->rchild != NULL)bljd(now->rchild);
		if (now->lchild == NULL and now->rchild == NULL)q1.push(now->data);
		return;
	}
	void ques1and2()
	{
		BTNode* now = r;
		bljd(now);
		while (q1.size() > 1)
		{
			cout << q1.front() << ' ';
			s2.push(q1.front());
			q1.pop();
		}
		cout << q1.front() << endl << q1.front() << ' ';
		while (s2.size() > 1)
		{
			cout << s2.top() << ' ';
			s2.pop();
		}
		cout << s2.top() << endl;

	}
	void ques3()
	{
		queue<int>ansq;
		queue<BTNode*>tmp;
		tmp.push(r);
		while (!tmp.empty())
		{
			BTNode* rx = tmp.front();
			tmp.pop();
			ansq.push(rx->data);
			if (rx->rchild)tmp.push(rx->rchild);
			if (rx->lchild)tmp.push(rx->lchild);
			
		}
		while (!ansq.empty())
		{
			cout << ansq.front() << ' ';
			ansq.pop();
		}
		return;
	}

};
int main()
{
	freopen("in.txt", "r", stdin);
	string s;
	cin >> s;
	BTree a;
	a.CreateBTree(s);
	a.ques1and2();
	a.ques3();
	return 0;
}

标签:lchild,ans,rx,括号,depth,转树,rchild,include,模板
From: https://www.cnblogs.com/zzzsacmblog/p/18172476

相关文章

  • 个人算法竞赛模板(2024.5.4)
    精简版:#include<algorithm>#include<cmath>#include<cstring>#include<iostream>#include<map>#include<queue>#include<set>#include<stack>#include<string>#include<vector>#include<......
  • 多项式模板学习笔记
    多项式乘法存在多项式\(F(z)=\sum_{i=0}^na_iz^i,G(z)=\sum_{i=0}^mb_iz^i\),我们定义多项式乘法:\[F(z)*G(z)=\sum_i\sum_ja_ib_jz^{i+j}\]多项式的点值表达一个\(n\)次函数可以用平面上的\(n+1\)个点来表达。所以我们可以把一个\(n\)次多项式从系数表达转化成\(n+......
  • python批量get pikachu的shell脚本模板
    声明:工具仅用于技术交流,请勿运行该脚本!!若造成损失,一切后果由使用者承担'''EXP:getshellusepikachu'''importrequests###############......
  • 【模板】生成函数 I
    多项式与形式幂级数多项式:\(A(x)=\sum\limits_{i=0}^{n}a_ix^i\)。形式幂级数:\(A(x)=\sum\limits_{i\ge0}a_ix^i\)。形式幂级数不用考虑其收敛域。形式幂级数(多项式)的运算设\(A(x)=\sum\limits_{i\ge0}a_ix^i,B(x)=\sum\limits_{i\ge0}b_ix^i\)。\(A(x)+B(x)=\sum\limits......
  • 响应式动漫音乐/个人博客杂志主题国漫FM模板
    国漫FM主题V1.8是以Ajax加以CSS动画的方式,很好的将优雅的设计感和极度精简的代码同时表现了出来,进而缔造出这样一款十分经典的名为Alwaysforyou的WordPress博客主题。正如作者自己所言:如果你想让你的WordPress博客看起来个性十足。FM主题为响应式格子布局(瀑布流),是一款......
  • 类模板的简单应用(用于存储不同类型数据的类容器)
    类模板应用explicitexplicit是一个关键字,用于指定该构造函数是显式构造函数。在C++中,当一个类的构造函数只有一个参数时,它可以被用于隐式类型转换,这可能会导致意想不到的行为和潜在的错误。为了避免这种情况,可以使用explicit关键字来声明该构造函数,表示禁止隐式类型转换,只能......
  • 使用这 7 个绩效评估模板简化您的员工评估
    绩效评估受到了不好的评价;员工发现它们压力很大,而管理者则发现它们很耗时。但随着绩效管理成为2024年人力资源的首要任务,也许是时候重新思考了。绩效评估模板可以帮助减轻评估过程的麻烦。通过为管理者提供一种简单、标准化的方法来评估团队的绩效,模板可以使绩效评估过程变得不......
  • 理解正则表达式中的括号 (),方括号 [] 和大括号 {}
    括号():括号在正则表达式中用于捕获匹配的内容,可以将匹配的部分分组,以便后续引用或提取。通过括号,我们可以创建子表达式,实现更复杂的匹配逻辑。例如,可以使用括号来捕获电话号码中的区号和号码部分,或者提取网址中的域名部分。示例:正则表达式:(ab)+,匹配"ababab"中连续重复的"ab"......
  • 智乃的括号匹配
    智乃的括号匹配题目描述智乃现在有一个仅由"("和")"组成长度大小为$N$的字符串,字符串的每一个位置的字符都有自己的权值$v_i$​和代价$c_i$​。智乃定义一对在该字符串中配对的括号对,假设左括号的坐标为$i$,右括号为$j$,该括号对的价值为两个括号权值的乘积$v_i\cdo......
  • 一个简洁、干净的中后台管理模板
    大家好,我是Java陈序员。今天,给大家介绍一个简洁、开源的中后台管理模板项目。关注微信公众号:【Java陈序员】,获取开源项目分享、AI副业分享、超200本经典计算机电子书籍等。项目介绍nova-admin——一个基于Vue3、Vite5、Typescript、NaiveUI,简洁干净后台管理模板。no......