首页 > 试题广场 > 计算原子的个数
[编程题]计算原子的个数
给出一个字符串格式的化学分子式,计算原子的个数
每个化学元素都是由一个大写字母,或者一个大写字母后跟着若干个小写字母组成,例如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 <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)

热门推荐

通过挑战的用户

查看代码