首页 > 试题广场 >

计算原子的个数

[编程题]计算原子的个数
  • 热度指数:826 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 64M,其他语言128M
  • 算法知识视频讲解
给出一个字符串格式的化学分子式,计算原子的个数
每个化学元素都是由一个大写字母,或者一个大写字母后跟着若干个小写字母组成,例如H是一个化学元素,Mg也是一个化学元素。
每个分子式中,原子的个数写在元素后面,如果原子个数是1,那么原子个数省略。例如H2O和H2O2都是有效的分子式,但H1O2不是有效分子式。
每个分子式中包含若干括号,为简单起见,分子式中只有小括号。
每次输入一个分子式,对每个给定的分子式,求出每个原子的个数,按照原子字母表的顺序排列,并输出。

输入描述:
一行,一个字符串表示输入的分子式


输出描述:
按要求输出答案
示例1

输入

H2O

输出

H2O
示例2

输入

Mg(OH)2

输出

H2MgO2
示例3

输入

K4(ON(SO3)2)2

输出

K4N2O14S4
"""
若为元素名加个数,则直接求解元素名及其原子个数,更新到字典中;
若包含括号,对括号内表达式递归求解。
"""


def get_digit(s):  # 求从s[0]开始的数字,若没有数字返回1,并返回数字的位数
    k = 0
    while k < len(s) and s[k].isdigit():
        k += 1
    num = 1 if k == 0 else int(s[:k])
    return num, k


def fun(s, dic, buff):  # buff为化学分子式s括号外的加成
    t, n = 0, len(s)  # t从0到n对s遍历
    while t < n:
        if s[t].isupper():  # 若为大写字母,则求元素名对应的个数
            j = t + 1
            while j < n and s[j].islower():
                j += 1
            num, tmp = get_digit(s[j:])  # 得到表达式所示的个数
            if s[t:j] not in dic:
                dic[s[t:j]] = 0
            dic[s[t:j]] += num * buff  # num*buff
            t = j + tmp
        elif s[t] == '(':  # 括号情况,对括号内表达式递归
            stack = ['(']
            j = t + 1
            while stack:  # 找到与外层括号配对的右括号下标j-1
                if s[j] == '(':
                    stack.append('(')
                elif s[j] == ')':
                    stack.pop()
                j += 1
            num, tmp = get_digit(s[j:])
            fun(s[t + 1:j - 1], dic, num * buff)  # 对括号内s[t + 1:j - 1]表达式递归求解
            t = j + tmp


if __name__ == "__main__":
    s = input().strip()  # 化学分子式
    dic = {}  # 存储化学原子及其个数
    fun(s, dic, 1)  # 构造dic
    ans = ""  # 排序并按要求输出
    for i in sorted(list(dic.keys())):
        ans += i
        if dic[i] > 1:
            ans += str(dic[i])
    print(ans)

发表于 2019-07-15 22:11:09 回复(0)
#include <bits/stdc++.h>
using namespace std;

int main(){
    string s, t="", r="";
    cin>>s;
    deque<int> Q;
    vector<string> S;
    vector<int> v;
    int l=s.length(), m=1, cnt=0, k=0;
    for(int i=l-1;i>=0;i--){
        if(isdigit(s[i]))
            t = s[i] + t;
        else{
            if(t!=""){
                Q.push_front(stoi(t));
                m *= stoi(t);
                cnt++;
                t = "";
            }
            if(islower(s[i]))
                r = s[i] + r;
            else if(isupper(s[i])){
                S.push_back(s[i]+r);
                v.push_back(m);
                if(cnt>k){
                    if(m!=1){
                        m /= Q.front();
                        Q.pop_front();
                    }
                    cnt--;
                }
                r = "";
            }else{
                if(s[i]==')')
                    k++;
                else if(s[i]=='('){
                    if(m!=1){
                        m /= Q.front();
                        Q.pop_front();
                    }
                    cnt--;
                    k--;
                }
            }
        }
    }
    map<string, int> M;
    for(int i=0;i<S.size();i++)
        M[S[i]] += v[i];
    for(map<string,int>::iterator it=M.begin();it!=M.end();it++){
        if(it->second==1)
            cout<<it->first;
        else
            cout<<it->first<<it->second;
    }
    cout<<endl;
    return 0;
}

发表于 2020-01-12 16:58:58 回复(0)
#include <iostream>
#include  <stack>
#include <string>
#include <map>
using namespace std;


string countOfAtoms(string formula)
{
	string res = "";
	stack<map<string, int> > st;
	map<string, int> cur;

	int n = formula.size(), pos = 0;

	while (pos < n)
	{
		if (formula[pos] == '(')  //遇到“(”压栈,  清空当前cur
		{
			++pos;
			st.push(cur);
			cur.clear();
		}
		else if(formula[pos] == ')')  //出栈“)”出栈,  
		{
			int i = ++pos;
			while (pos < n && isdigit(formula[pos]))    //统计“)”后的数字
			{
				++pos;
			}
			int multiple = stoi(formula.substr(i, pos - i));
		
			//for (auto a : cur)
			//{  
			//	st.top()[a.first] += a.second * multiple;   //在当前栈顶,添加新元素
			//}
			//cur = st.top();                    
			//st.pop();

			map<string, int> preCur = st.top();        //此时preCur保存了上一时刻的元素
			st.pop();
			for (auto a : cur)                         //合并当前cur的元素到preCur
			{
				preCur[a.first] += a.second*multiple;
			}
			cur = preCur;                               

		}
		else
		{	
			int i = pos++;
			while (pos < n && islower(formula[pos]))   //识别元素
			{
				pos++;
			}
			string elem = formula.substr(i, pos - i);
			i = pos;
			while (pos < n && isdigit(formula[pos]))    //识别元素后面的数字
			{
				++pos;
			}
			string cnt = formula.substr(i, pos - i);  
			cur[elem] += cnt.empty() ? 1 : stoi(cnt);   //当前元素存入cur

		}

		
	}

	for (auto a : cur)
	{
		res += a.first + (a.second == 1 ? "" : to_string(a.second));
	}


	return res;
}


int main()
{
	string formula, result;
	cin >> formula;
	result = countOfAtoms(formula);
	cout << result << endl;

}


编辑于 2020-09-04 17:33:32 回复(0)
#include<bits/stdc++.h>
using namespace std;
int main()
{
    // 原子格式 大写的单个字符
    // 或者双字符 第一个大写  第二个小写
    string s;
    vector<char>v;
    string tmp = "";
    while(cin>>s)
    {
        for(int i=0;i<s.size();++i)
        {
            if(s[i]=='(') v.push_back('#');
            else if(s[i]==')'){

                while(v.back()!='#')
                {
                    tmp = v.back()+tmp;
                    v.pop_back();
                }
                v.pop_back();

            }
            else if((s[i]<='Z'&&s[i]>='A')||(s[i]>='a'&&s[i]<='z'))
                v.push_back(s[i]);
            else{
                int cnt = 0;
                string last = "";
                if(s[i-1]>='A'&&s[i-1]<='Z') last += s[i-1];
                else {
                    last = last + s[i-1];
                    last = s[i-2] + last;
                }
                while(i<s.size()&&s[i]>='0'&&s[i]<='9')
                {
                    cnt = cnt*10 + (s[i]-'0');
                    ++i;
                }
                if(tmp!=""){
                    while(cnt--)
                    {
                        for(char c:tmp)
                          v.push_back(c);
                    }
                }
                else{
                    cnt-=1;
                    while(cnt--)
                    {
                        for(char c:last)
                            v.push_back(c);
                    }
                }
                //for(char t:v)
                 //   cout<<t;
                //cout<<endl;
                tmp.clear();
                --i;
            }
        }
    }
    map<string,int>mp;
    while(!v.empty())
    {
       string tmp = "";
        char c = v.back();
        v.pop_back();
        if(c>='A'&&c<='Z') tmp += c;
        else {
            tmp+=c;
            tmp  = v.back()+tmp;
            v.pop_back();
        }
        mp[tmp] += 1;
    }
    for(auto it=mp.begin();it!=mp.end();++it)
    {
        if(it->second>1)
            cout<<it->first<<it->second;
        else cout<<it->first;
    }

    return 0;
}

编辑于 2020-05-24 16:41:13 回复(1)
#include <bits/stdc++.h>

using namespace std;

struct node{
    string s;
    int num;
    node (string s, int num){
        this->s = s;
        this->num = num;
    }
};

string int_to_string(int i){
    string res;
    stringstream ss;
    ss << i;
    ss >> res;
    return res;
}

int main() {
    string s;
    map<string, int> mp;
    map<string, string> decode;
    vector <string> st;
    vector <string> tu;
    vector <node> ret;
    cin >> s;
    for (int i = 0; i < s.length(); i++){
        string ans = "";
        string str = "";
        if(s[i] >= 'A' && s[i] <= 'Z'){
            ans += (int_to_string(i));
            str.push_back(s[i]);
            while((i + 1) < s.length() && s[i + 1] >= 'a' && s[i + 1] <= 'z'){
                i++;
                str.push_back(s[i]);
            }
            if((i + 1) < s.length()){
                if(s[i + 1] >= '0' && s[i + 1] <= '9'){
                    int bar = 0;
                    while((i + 1) < s.length() && s[i + 1] >= '0' && s[i + 1] <= '9'){
                        i++;
                        bar = bar * 10 + (s[i] - '0');
                    }
                    mp[ans] = bar;
                } else {
                    mp[ans] = 1;
                }
            } else {
                mp[ans] = 1;
            }
            decode[ans] = str;
            st.push_back(ans);
            //cerr << "ans == " << ans << endl;
            //cerr << "str == " << str << endl;
        } else if(s[i] == '('){
            string cur = "(";
            st.push_back(cur);
        } else if(s[i] == ')'){
            int foo;
            if((i + 1) < s.length() && s[i + 1] >= '0' && s[i + 1] <= '9'){
                foo = 0;
                while((i + 1) < s.length() && s[i + 1] >= '0' && s[i + 1] <= '9'){
                    i++;
                    foo = 10 * foo + (s[i] - '0');
                }
            } else {
                foo = 1;
            }
            //cerr << "foo == " << foo << endl;
            while(!st.empty()){
                string use = st.back();
               // cerr << "use == " << use << endl;
               // cerr << "str == " << decode[use] << endl;
                if(use == "("){
                    st.pop_back();
                    break;
                }
                mp[use] *= foo;
                tu.push_back(use);
                st.pop_back();
            }
            while(!tu.empty()){
                st.push_back(tu.back());
                tu.pop_back();
            }
        }
    }

    for (int i = 0; i < st.size(); i++){
        //cerr << decode[st[i]] << endl;
        ret.push_back(node(decode[st[i]], mp[st[i]]));
    }
    sort(ret.begin(), ret.end(), [&](node a, node b){return a.s < b.s;});
    for (int i = 0; i < (int)ret.size(); i++){
        int num = ret[i].num;
        if((i + 1) < (int)ret.size() && ret[i].s == ret[i + 1].s){
            while((i + 1) < ret.size() && ret[i].s == ret[i + 1].s){
                i++;
                num += ret[i].num;
            }
        }
        cout << ret[i].s;
        if(num > 1){
            cout << num;
        }
    }
    cout << "\n";
    return 0;
}

发表于 2019-11-01 08:56:01 回复(0)
leetcode 上的原题,由于原子最多两个字母,用哈希数组存储每段原子的个数,括号匹配,递归求解。
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * @Auther:srd-czk
 * @Date:2019/9/7
 * @Description:a2019
 * @version:1.0
 */
public class Main {

    private static String toString(int i) {
        StringBuilder sb = new StringBuilder();
        sb.append((char)('A' + i / 27));
        if (i % 27 != 0) sb.append((char)('a' + i % 27 - 1));
        return sb.toString();
    }

    private static int[] process(char[] chs, int i, int j) {
        int[] res = new int[26 * 27];
        while (i < j + 1) {
            if (chs[i] >= 'A' && chs[i] <= 'Z') {
                char c = chs[i];
                if (i + 1 < j + 1 && chs[i + 1] >= 'a' && chs[i + 1] <= 'z') {
                    i++;
                    int k = (c - 'A') * 27 + 1 + (chs[i] - 'a');
                    if (i + 1 < j + 1 && Character.isDigit(chs[i + 1])) {
                        int p = 0;
                        i++;
                        while (i < j + 1 && Character.isDigit(chs[i])) {
                            p = p * 10 + chs[i++] - '0';
                        }
                        res[k] += p;
                    } else {
                        res[k]++;
                        i++;
                    }
                } else if (i + 1 < j + 1 && Character.isDigit(chs[i + 1])) {
                    int p = 0;
                    i++;
                    while (i < j + 1 && Character.isDigit(chs[i])) {
                        p = p * 10 + chs[i++] - '0';
                    }
                    res[27 * (c - 'A')] += p;
                } else {
                    res[27 * (c - 'A')]++;
                    i++;
                }
            } else {
                int cnt = 1;
                int start = ++i;
                while (i < j + 1 && cnt != 0) {
                    if (chs[i] == '(') cnt++;
                    else if (chs[i] == ')') cnt--;
                    i++;
                }
                int[] sub = process(chs, start, i - 2);
                int p = chs[i++] - '0';
                while (i < j + 1 && Character.isDigit(chs[i])) {
                    p = p * 10 + chs[i++] - '0';
                }
                for (int k = 0; k < sub.length; k++) {
                    res[k] += sub[k] * p;
                }
            }
        }
        return res;
    }
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

        String s = bf.readLine();
        int[] res = process(s.toCharArray(), 0, s.length() - 1);
        for (int i = 0; i < res.length; i++) {
            if (res[i] > 0) {
                System.out.print(toString(i));
                if (res[i] > 1) System.out.print(res[i]);
            }
        }
        System.out.println();
        bf.close();
    }
}


发表于 2019-09-07 12:27:53 回复(0)
遇到这种问题,我最先想到的,还是用栈来进行括号匹配,策略就是,每次遇到左括号,就把当前的位置压栈,遇到右括号就将当前的位置出栈,然后从出栈的位置开始,把每一个原子数都乘一个值,最后在进行排序和合并。
#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;

/*

10 60 76 66 76 85 55 61 71 84 62
20

 */

string countAtom(string &s){
    istringstream iss(s);
    char c;
    vector<pair<string,int>> v;
    stack<int> st;
    int i =0 ;
    string tmp;
    int num;
    while(iss>>c){
        tmp.clear();
        if(c == '('){
            st.push(i);
        }
        else if(c >= 'A' && c <= 'Z'){
            tmp += c;
            if(!iss.eof()){
                c = iss.peek();
                if(c >= 'a' && c <= 'z'){
                    iss>>c;
                    tmp += c;
                }
            }
            v.push_back(make_pair(tmp,1));
            i++;
        }
        else if(c >= '0' && c <= '9'){
            iss.putback(c);
            iss>>num;
            v[i-1].second = num;
        }
        else if(c == ')'){
            iss>>num;
            int start = st.top();
            st.pop();
            for(int j=start;j<v.size();j++){
                v[j].second *= num;
            }
        }
    }
    sort(v.begin(),v.end(),[](pair<string,int> p1,pair<string,int> p2)->bool{
        return p1.first < p2.first;
    });
    pair<string,int> pre = v[0];
    ostringstream oss;
    for(int j=1;j<v.size();j++){
        if(v[j].first == pre.first){
            pre.second += v[j].second;
        }else{
            oss<<pre.first;
            if(pre.second > 1){
                oss<<pre.second;
            }
            pre = v[j];
        }
    }
    oss<<pre.first;
    if(pre.second > 1){
         oss<<pre.second;
    }
    return oss.str();
}

int main(int argc, char const *argv[])
{
    string s;
    while(getline(cin,s)){
        string res = countAtom(s);
        cout<<res<<endl;
    }
    system("pause");
    return 0;
}


发表于 2019-07-23 09:01:33 回复(0)