【栈】726. 原子的数量

本文涉及知识点

栈

LeetCode726. 原子的数量

给你一个字符串化学式 formula ，返回 每种原子的数量 。
原子总是以一个大写字母开始，接着跟随 0 个或任意个小写字母，表示原子的名字。
如果数量大于 1，原子后会跟着数字表示原子的数量。如果数量等于 1 则不会跟数字。
例如，“H2O” 和 “H2O2” 是可行的，但 “H1O2” 这个表达是不可行的。
两个化学式连在一起可以构成新的化学式。
例如 “H2O2He3Mg4” 也是化学式。
由括号括起的化学式并佐以数字（可选择性添加）也是化学式。
例如 “(H2O2)” 和 “(H2O2)3” 是化学式。
返回所有原子的数量，格式为：第一个（按字典序）原子的名字，跟着它的数量（如果数量大于 1），然后是第二个原子的名字（按字典序），跟着它的数量（如果数量大于 1），以此类推。

示例 1：

输入：formula = “H2O”
输出：“H2O”
解释：原子的数量是 {‘H’: 2, ‘O’: 1}。
示例 2：

输入：formula = “Mg(OH)2”
输出：“H2MgO2”
解释：原子的数量是 {‘H’: 2, ‘Mg’: 1, ‘O’: 2}。
示例 3：

输入：formula = “K4(ON(SO3)2)2”
输出：“K4N2O14S4”
解释：原子的数量是 {‘K’: 4, ‘N’: 2, ‘O’: 14, ‘S’: 4}。

提示：

1 <= formula.length <= 1000
formula 由英文字母、数字、‘(’ 和 ‘)’ 组成
formula 总是有效的化学式

本题本质是乘法、加法、括号

运算数：unorder_map m。 m[str] 表示原子str的数量。
解析到数字时，解析成乘法。
解析到原子时，如果前一个字符存在，且不是数字，则补上乘1。可以不补，因为乘以1，不影响结果。
否则，解析成加法。+ 入栈，操作数入栈。
两个栈初始为空。乘法马上运算，加法入栈。遇到右括号，或结束时，统一计算。
注意： 原子名称一定以大写字母开始，且后续字母不包括大写字母。也就是有多少大写字母，就有多少原子名称。

代码

核心代码

class Solution {
public:
	string countOfAtoms(string s) {
		for (int i = 0; i < s.length(); i++) {
			if ('(' == s[i]) {
				m_opeSta.emplace_back('+');
				m_opeSta.emplace_back(s[i]);
			}
			else if(')' == s[i]) {
				DoRange();
			}
			else if (isdigit(s[i])) {
				int num = 0;
				while (isdigit(s[i])) {
					num = num * 10 + (s[i] - '0');
					i++;
				}
				i--;
				Mul(num);
			}
			else {
				string strName;
				strName += s[i++];
				while (islower(s[i])) {
					strName += s[i++];
				}
				i--;
				m_opeSta.emplace_back('+');
				map<string, int> num;
				num[strName] = 1;
				m_numSta.emplace_back(num);
			}
		}
		DoRange();
		string str;
		for (const auto& [name, cnt] : m_numSta.back()) {
			str += name;
			if (cnt > 1) {
				str += std::to_string(cnt);
			}
		}
		return str;
	}
	void DoRange() {
		m_opeSta.pop_back();
		while (m_opeSta.size() && ('+' == m_opeSta.back())) {
			auto num2 = m_numSta.back();
			m_numSta.pop_back();			
			Add(m_numSta.back(),num2);
			m_opeSta.pop_back();
		}
		if (m_opeSta.size()) { m_opeSta.pop_back(); }		
	}
	void Mul(int num) {
		Mul(m_numSta.back(), num);
	}
	void Mul(map<string, int>& num1, int num2) {
		for (auto& [tmp, cnt] : num1) {
			cnt *= num2;
		}
	}
	void Add(map<string, int>& num1, map<string, int>& num2) {
		for (auto& [tmp, cnt] : num2) {
			num1[tmp] += cnt;
		}
	}
	vector<char> m_opeSta;
	vector<map<string, int>> m_numSta;
};

单元测试

template<class T1,class T2>
void AssertEx(const T1& t1, const T2& t2)
{
	Assert::AreEqual(t1 , t2);
}

template<class T>
void AssertEx(const vector<T>& v1, const vector<T>& v2)
{
	Assert::AreEqual(v1.size(), v2.size());	
	for (int i = 0; i < v1.size(); i++)
	{
		Assert::AreEqual(v1[i], v2[i]);
	}
}

template<class T>
void AssertV2(vector<vector<T>> vv1, vector<vector<T>> vv2)
{
	sort(vv1.begin(), vv1.end());
	sort(vv2.begin(), vv2.end());
	Assert::AreEqual(vv1.size(), vv2.size());
	for (int i = 0; i < vv1.size(); i++)
	{
		AssertEx(vv1[i], vv2[i]);
	}
}

namespace UnitTest
{
	string formula;
	TEST_CLASS(UnitTest)
	{
	public:
		TEST_METHOD(TestMethod0)
		{
			formula = "H2O";
			auto res = Solution().countOfAtoms(formula);
			AssertEx("H2O", res.c_str());
		}
		TEST_METHOD(TestMethod1)
		{
			formula = "Mg(OH)2";
			auto res = Solution().countOfAtoms(formula);
			AssertEx("H2MgO2", res.c_str());
		}
		TEST_METHOD(TestMethod2)
		{
			formula = "K4(ON(SO3)2)2";
			auto res = Solution().countOfAtoms(formula);
			AssertEx("K4N2O14S4", res.c_str());
		}
		TEST_METHOD(TestMethod3)
		{
			formula = "Mg((H2O)2Na)4(F)(H2SO4)N";
			auto res = Solution().countOfAtoms(formula);
			AssertEx("FH18MgNNa4O12S", res.c_str());
		}
	};
}

扩展阅读

视频课程

有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

相关下载

想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。