讨论/《春招冲刺班 - 7 天刷题挑战》 - 化学公式解析/
《春招冲刺班 - 7 天刷题挑战》 - 化学公式解析
共 17 个回复

思路:模拟题,主要是分情况处理和递归,每遇到一个左括号就进入递归,每一种元素用map进行统计,最后遍历map即可,注意处理每种情况时要防止出界。

#include <iostream>
#include <map>
#include <string>

using namespace std;
string s;
map<string, int> count;

void process(int l, int r, int cnt)
{
    int n = r + 1;
    for(int i = l; i < n; i++)
    {
        string t{s[i]};
        if(s[i] >= 'A' && s[i] <= 'Z')
            if(i + 1 < n && (s[i + 1] >= '0' && s[i + 1] <= '9'))
                count[t] += cnt * (s[i + 1] - '0');
            else if(i + 1 < n && (s[i + 1] >= 'a' && s[i + 1] <= 'z'))
            {
                t += s[i + 1];
                if(i + 2 < n && (s[i + 2] >= '0' && s[i + 2] <= '9'))
                    count[t] += cnt * (s[i + 2] - '0');
                else count[t] += cnt;
                i++;
            }
            else count[t] += cnt;
        else if(s[i] == '[' || s[i] == '(')
        {
            char c;
            if(s[i] == '[') c = ']';
            else c = ')';
            int l = i + 1, k = 1;
            while(s[i + 1] != c) i++;
            if(i + 2 < n && (s[i + 2] >= '0' && s[i + 2] <= '9')) k = s[i + 2] - '0';
            process(l, i, k * cnt);
        }
        
    }
}

int main()
{
    cin >> s;

    int n = s.size();
    process(0, n - 1, 1);

    for(auto &[k, v] : count)
        cout << k << v;
    return 0;
}
5

这个题就是坑有点多。。。
踩过的几个坑:

  1. 元素和数字都可能不止一位字符,比如Mg,Cu;
  2. 不一定每一个数字都是跟在括号后面的,比如SO4中的4;
  3. 输出要求有序。

大概思路:(本文中所有“元素”均特“化学元素”)

  1. 对输入的字符串进行划分,将元素,数字,括号这些都一个个独立出来,放进字符串线性表里,方便后续操作,划分时注意补括号,保证每个数字前面都有括号。我是逆向存储的;
    比如如果输入的是硫酸氢钙的化学式"Ca(HSO4)2",那么线性表中的元素就将是["2",")","4",")","O","(","S","H","(","Ca"]
  2. 创建一个字符串堆栈 strStack 存储元素和括号,创建一个数字堆栈 numStack 存储数字;
  3. 对划分好的线性表进行遍历,由于我第一步是逆向存储的所以这一步直接顺序遍历。遍历过程中将元素和右括号都直接入 strStack 栈,数字入 numStack 栈。如果遇到左括号就从数字堆栈中取出一个数字num,如果数字堆栈为空就取1,那么 strStack 中上一个左括号到栈顶的所有元素都需要重复num次,将这些元素重复送入strStack 栈。
  4. 遍历完成后 strStack 栈中就只剩下元素,并且元素在化学式中有多少个就在 strStack 中出现几次,进行统计并输出即可。
    如"Ca(HSO4)2"在这一步得到的 strStack 就是["H","S","O","O","O","O","H","S","O","O","O","O","Ca"]。

时间复杂度:

第一次遍历的时间复杂度是O(len),len是输入字符串的长度。
第二次遍历的时间复杂度是O(m+n),m是输入字符串完成划分后的长度,不考虑括号的话是介于len和len/2之间的;n是所有元素的个数之和。
所以总的时间复杂度应该是O(len+n)。

我觉得写到最后就是在不停地加东西修bug所以代码越来越长,可能我一开始思路就不太合适。。。
我这啰里啰嗦的代码就抛砖引玉了,希望能看到其他同学的分享!

import java.util.*;

public class Solution {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String str = in.next();
        char[] strArr = str.toCharArray();
        Map<String, Integer> mymap = new TreeMap<>();//mymap中存储出现的元素与其数量的映射关系
        //将输入数据完成划分并逆序存储到线性表arr中,并且在数字前补充上括号,确保每个数字前面都有括号
        ArrayList<String> arr = new ArrayList<>();
        StringBuilder numSB = new StringBuilder(), elementSB = new StringBuilder();//numSB和elementSB分别临时记录数字和元素
        //flag作为是否要补充括号的标志位
        boolean flag = false;
        //逆向遍历字符串,方便整理出不止一个字符的元素
        for (int i = strArr.length - 1; i >= 0; i--) {
            //如果当前遍历的字符是数字
            if (Character.isDigit(strArr[i])) {
                numSB.insert(0, strArr[i]);
                //如果逆向遍历时下一个字符不是数字,那么将numSB转成字符串送入arr
                //因为合法的化学式输入不可能以数字开头,所以不需要考虑i==0的情况
                if (i > 0 && !Character.isDigit(strArr[i - 1])) {
                    arr.add(numSB.toString());
                    numSB = new StringBuilder();
                    //如果当前遍历的字符是数字但是前一个字符不是括号,那么需要将前一个字符(一定是元素)用括号括起来
                    if (strArr[i - 1] != ')' && strArr[i - 1] != ']') {
                        arr.add(")");
                        flag = true;
                    }
                }
            }
            //如果当前遍历的字符是字母
            else if (Character.isLetter(strArr[i])) {
                elementSB.insert(0, strArr[i]);
                //如果当前遍历的字符是大写字母,那么将elementSB转成字符串送入arr
                if (Character.isUpperCase(strArr[i])) {
                    arr.add(elementSB.toString());
                    elementSB = new StringBuilder();
                    //如果需要补充括号,补充上
                    if (flag) {
                        arr.add("(");
                        flag = false;
                    }
                }
            }
            //如果当前遍历的字符是括号,直接送入arr
            else arr.add(strArr[i] + "");
        }
        Stack<String> strStack = new Stack<>();//元素和括号堆栈
        Stack<Integer> numStack = new Stack<>();//数字堆栈
        for (String s : arr) {
            //当遍历到一个"("或者"[",就从numStack取出一个数字(如果数字堆栈为空就取一个1)赋值给num
            if (s.equals("(")) {
                int num = numStack.isEmpty() ? 1 : numStack.pop();
                //temp临时记录strStack中最近的两个括号之间的元素
                ArrayList<String> temp = new ArrayList<>();
                while (!strStack.peek().equals(")"))
                    temp.add(strStack.pop());
                strStack.pop();
                //把temp中的元素重新装回strStack中,并且装num次
                while (num > 0) {
                    for (String t : temp)
                        strStack.push(t);
                    num--;
                }
            } else if (s.equals("[")) {
                int num = numStack.isEmpty() ? 1 : numStack.pop();
                ArrayList<String> temp = new ArrayList<>();
                while (!strStack.peek().equals("]"))
                    temp.add(strStack.pop());
                strStack.pop();
                while (num > 0) {
                    for (String t : temp)
                        strStack.push(t);
                    num--;
                }
            }
            //数字送入数字堆栈
            else if (Character.isDigit(s.charAt(0)))
                numStack.push(new Integer(s));
                //元素和"]"以及")"直接送入strStack堆栈
            else {
                strStack.push(s);
            }
        }
        //至此strStack中存储了所有元素,并且元素在化学式中有几个就在strStack中出现了几次
        //遍历strStack统计每个元素出现的次数
        for (String s : strStack) {
            int count = mymap.getOrDefault(s, 0);
            mymap.put(s, count + 1);
        }
        //TreeMap自动排序,直接输出即可
        for (String key : mymap.keySet())
            System.out.print(key + mymap.get(key));
    }
}
4

对于类似MgO2这样的化学式,很轻易的得到结果,难点在于增加了括号后的情况,但是括号内的实际上也是类似的相同化学式,所以可以递归处理括号内的内容,需要注意的是括号外有可能有值,也能没值,所以需要进行额外的统计

import java.util.*;
public class Solution {
    int i=0;
    public static void main(String [] args) {
        Scanner sc = new Scanner(System.in);
        String input = sc.nextLine();
        StringBuilder ans = new StringBuilder();
        char[] str = input.toCharArray();
        Map<String, Integer> map = new HashMap<>();
        map = new Solution().countOfAtoms(str);
        String[] set =  map.keySet().toArray(new String[map.size()]);
        Arrays.sort(set);
        for (String name: set) {
            ans.append(name);
            int multiplicity = map.get(name);
            if (multiplicity > 1) ans.append("" + multiplicity);
            else ans.append("1");
        }
        System.out.print(ans.toString());
    }
    private Map<String, Integer> countOfAtoms(char [] str){
        Map<String, Integer> count = new HashMap<>();
        for(;i<str.length&&str[i]!=')'&&str[i]!=']';){//处理主体,不是右括号就开始处理
            if(str[i] == '('||str[i] == '['){//如果是左括号就递归处理
                i++;
                Map<String, Integer> temp = new HashMap<>();
                for (Map.Entry<String, Integer> entry: countOfAtoms(str).entrySet()) {
                    count.put(entry.getKey(), count.getOrDefault(entry.getKey(), 0) + entry.getValue());
                }
            }else{//常规处理
                int start = i++;
                while(i<str.length&&Character.isLowerCase(str[i]))   i++;
                String name = String.valueOf(str, start, i-start);
                start = i;
                while(i<str.length&&Character.isDigit(str[i]))   i++;
                int c = start==i?1:Integer.parseInt(String.valueOf(str, start, i-start));
                count.put(name, count.getOrDefault(name, 0)+c);
            }
        }
        int start = ++i;//针对括号情况的特判,如果有括号那么判断外面是否有值,有的话对之前括号内的处理元素同乘一个倍数
        while(i<str.length&&Character.isDigit(str[i]))   i++;
        if(start<i){
            int c = Integer.parseInt(String.valueOf(str, start, i-start));
            for(String name:count.keySet()){
                count.put(name, count.get(name)*c);
            }
        }
        return count;
    }
}

3

注意:该题需要考虑无意义括号的情况,即右括号后面不一定会有数字。
例如:

  • Na(OH) -> H1Na1O1
  • Cu(SO4) -> Cu1O4S1
3

模拟题, 不要着急慢慢思考就可以了.

思路

元素名以大写字母开始, 可能跟随一个或多个小写字母, 元素名后可能跟随一个数字表示个数, 缺省为1. 这是最基础的情况.
遇到左括号时, 可以这样考虑, 在直到这个括号结束之前, 应单独计算这个括号内的元素个数, 括号结束后, 将括号后跟随的数与括号内的各元素对应数量相乘, 这样即可得到整个括号结构中的元素及对应数量.
操作上体现为:
遇到左括号->保留外部现场->记录括号内元素及其个数->遇到右括号->读取右括号后跟随的数并更正括号内所有元素的数量->取回上一个外部现场并将括号内的元素个数添加进去.
其中"外部现场"指的是遇到括号前已经记录的元素名-元素个数的映射. 外部现场的保存与取回可使用栈来实现.
如此操作, 在保证输入合法的情况下, 最后一定获得了全部元素的映射, 输出即可.

代码

C++实现:
需要注意的是代码编写时因为思路不是特别清晰, 使用了vector容器来暂存现场. 替换为stack容器可在逻辑上更加易于理解.

#include <iostream>
#include <vector>
#include <map>
#include <string>

using namespace std;

int main() {
    // 认为输入小于256个字符.
    char pszInput[256];
    cin.getline(pszInput, 256);
    vector<map<string, int>> vecLevels;
    map<string, int> mapElementCount;
    map<string, int>::iterator it;  // 后面需要多次遍历map, 先在这里声明iterator.
    char *pchParsing = pszInput;    // 指向将要解析的下一个字符.
    string strCurElement;
    while (*pchParsing != '\0') {
        // 遇到括号开始, 记为新的Level.
        if (*pchParsing == '(' || *pchParsing == '[') {
            vecLevels.push_back(mapElementCount);   // "备份"上一层的数据.
            mapElementCount.clear();
            pchParsing++;
            continue;
        }
        // 当前Level结束, 计算乘积后向上合并.
        else if (*pchParsing == ')' || *pchParsing == ']') {
            pchParsing++;
            int nCurLevelCount = 0;
            while (*pchParsing >= '0' && *pchParsing <= '9') {
                nCurLevelCount = nCurLevelCount * 10 + (*pchParsing - '0');
                pchParsing++;
            }
            if (nCurLevelCount == 0) nCurLevelCount = 1;    // 括号后无数字的情况.
            for (it = mapElementCount.begin(); it != mapElementCount.end(); ++it) it->second *= nCurLevelCount;
            map<string, int> mapLastLevel = vecLevels.back();   // 取出上一层的"备份"数据.
            vecLevels.pop_back();
            for (it = mapLastLevel.begin(); it != mapLastLevel.end(); ++it) mapElementCount[it->first] += it->second;
            continue;
        }
        // 获取当前元素.
        strCurElement.clear();
        strCurElement.push_back(*pchParsing);
        pchParsing++;
        while (*pchParsing >= 'a' && *pchParsing <= 'z') {
            strCurElement.push_back(*pchParsing);
            pchParsing++;
        }
        // 若元素后跟随数字, 获取数量.
        int nCurElementCount = 0;
        while (*pchParsing >= '0' && *pchParsing <= '9') {
            nCurElementCount = nCurElementCount * 10 + (*pchParsing - '0');
            pchParsing++;
        }
        if (nCurElementCount == 0) nCurElementCount = 1;    // 元素后无数字的情况.
        mapElementCount[strCurElement] += nCurElementCount;
    }
    // C++ STL的map默认按key(这里即为元素名)升序排序, 已符合题意, 直接输出即可.
    for (it = mapElementCount.begin(); it != mapElementCount.end(); ++it) cout << it->first << it->second;
    cout << endl;
    return 0;
}

时间复杂度

O(n)级, 此算法的极端输入样例形如
(I(Dont(Like(Chemistry()))))
复杂度为O(2n) = O(n)

不正之处恳请大佬们批评指正~

2

有三种搜索 :
A 正常单个元素
B 小括号内
C 中括号内

可以在C中嵌套AB,在B中嵌套A
在使用BC时会去找到括号外面的数字k
这样A在加B中加数量的时候就直接可以乘上k,
如果是C中有B再有A只需要将C的k传给B,再用B的k乘上C的k去对A进行加数操作。

用HashMap来存数据,最后需要有序,直接Collections.sort()对key排序后输出

主要是index的加减和越界问题比较恶心,其他思路还是比较清晰的

PS:没有考虑后面数字有可能是十位数的情况,但是实现起来应该也不难

时间复杂度:

由于需要找括号后面的数字,但是不知道有多少个括号,这边就假设有m个括号,那么最坏情况下就是O(m*n);最好情况的话就是没有括号O(n)

空间复杂度:

元素的种类的数量,O(n)

import java.util.*;
public class Solution{
    public static int index=0;
    public static int n=0;
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        String s="";
        if(sc.hasNext())   s=sc.nextLine();
        sc.close();
        HashMap<String,Integer> map=new HashMap<>();
        n=s.length();
        while(index<n){
            if(s.charAt(index)=='['){
                addC(map,s);
            }
            if(index>=n) break;
            if(s.charAt(index)=='('){
                addB(1,map,s);
            }else{
                addA(1,map,s);
            }
        }
        ArrayList<String> ar=new ArrayList<>();
        ar.addAll(map.keySet());
        Collections.sort(ar);
        for(String str:ar){
            System.out.print(str+""+map.get(str));
        }
    }
//寻找元素全名
    public static String find(String s){
        if(index<n-1&&s.charAt(index+1)<='z'&&s.charAt(index+1)>='a'){
            index++;
            return s.substring(index-1,index+1);
        }
        return s.substring(index,1+index);
    }
//单个元素计数
    public static void addA(int k,HashMap<String,Integer> map,String s){
        String f=find(s);
        if(index>=n||s.charAt(index+1)>'9'||s.charAt(index+1)<'1'){
            map.put(f,map.getOrDefault(f,0)+k);
            index++;
        }else{
            map.put(f,map.getOrDefault(f,0)+k*(int)(s.charAt(index+1)-'0'));
            index+=2;
        }
    }
//小括号计数
    public static void addB(int k,HashMap<String,Integer> map,String s){
        index++;
        int i=index;
        int add=1;
        while(s.charAt(i)!=')'){
            i++;
        }
        if(s.charAt(i+1)<='9'&&s.charAt(i+1)>='0'){
            k*=s.charAt(i+1)-'0';
            add++;
        }
        while(s.charAt(index)!=')'){
            addA(k,map,s);
        }
        index+=add;
    }
//中括号计数
    public static void addC(HashMap<String,Integer> map,String s){
        index++;
        int i=index;
        int add=1;
        int k=1;
        while(s.charAt(i)!=']'){
            i++;
        }
        if(i<n-1&&s.charAt(i+1)<='9'&&s.charAt(i+1)>='0'){
            k*=s.charAt(i+1)-'0';
            add++;
        }
        while(s.charAt(index)!=']'){
            if(s.charAt(index)=='(') addB(k,map,s);
            else addA(k,map,s);
        }
        index+=add;
    }
}
1

好久没做模拟题了,贴一下自己的代码留作纪念。
思路:题目中有两种括号,所以可以想到括号匹配->所以想到使用栈来处理,这个题和表达式求值的不同之处是表达式求值可以算出一个值,而这个是一堆元素,不好存,首先要整个结构体表示元素名和数量。
但是相比表达式求值也有简单之处,这个题不需要优先级,[]和()其实可以看作一种括号(虽然有'['和'(',但是()和[]必须成对出现,不能交叉),处理完括号,再把栈扫一遍排序即可。

代码:

#include <bits/stdc++.h>

using namespace std;

struct node {
    string w;
    int d;
    node(string a , int b):w(a) , d(b){}
    bool operator < (const node b) {
    	return w < b.w;
	}
};

int main() {
    string s;
    ios::sync_with_stdio(0);
    cin >> s;
    //cout << s << endl;
	stack < node > st;
	//cout << "???" << endl;
	for(int i = 0 ; i < s.length() ; i++) {
		if(isupper(s[i])) {
			string t = "";
			t += s[i];
			if(i < s.length() - 1 && islower(s[i + 1])) {
				i++;
				t += s[i];
			}
			int tmp = 0;
			while(i < s.length() - 1 && isdigit(s[i + 1])) {
				i++;
				tmp = tmp * 10 + s[i] - '0';		
			}
			if(!tmp)tmp = 1;
			//cout << "t = " << t << endl; 
			st.push(node(t , tmp));
		}
		else {
			if(s[i] == '(') {
				st.push(node("(" , 1));
			}
			else if(s[i] == '[') {
				st.push(node("[" , 1));
			}
			else if(s[i] == ')' || s[i] == ']') {
				int tmp = 0;
				while(i < s.length() - 1 && isdigit(s[i + 1])) {
					i++;
					tmp = tmp * 10 + s[i] - '0';		
				}
				
				if(!tmp)tmp = 1;
				stack < node >st1;
				while(!st.empty()) {
					node u = st.top();st.pop();
					if(u.w == "(" || u.w == "[") {
						break;
					}
					else {
						st1.push(node(u.w , tmp * u.d));
					}
				}
				//cout << "???" << endl;
				while(!st1.empty()) {
					st.push(st1.top()); st1.pop();
				}
				//K4[ON(SO3)2]2
			}
		}
	}
	
	vector < string > ans;
	map < string , int >mp;
	while(!st.empty()) {
		node u = st.top(); st.pop();
		if(!mp.count(u.w)) {
			ans.push_back(u.w);
		}
		mp[u.w] += u.d;
	}
	sort(ans.begin() , ans.end());
	for(int i = 0 ; i < ans.size() ; i++) {
		cout << ans[i] << mp[ans[i]];
	}
	cout << "\n";
    return 0;
}
1

遇到字符串处理,果断还是用了py,c/c++大佬们tql
统一括号为圆括号,会有多重括号,所以用递归的话会简单很多,用递归的时候注意层数,感觉本题数据不严,数据方括号和圆括号在本地应该各自最多只有一对,建议做完微调交下leetcode类似的题目

def parse(s):
    n = len(s)
    # print(s)
    now = dict()
    i = 0
    while i < n:
        # print("while", i, s[i:])
        # handle yuansu
        if s[i] >= 'A' and s[i] <= 'Z':
            name = [s[i]]
            i += 1
            while (i < n and s[i] >= 'a' and s[i] <= 'z'):
                name.append(s[i])
                i += 1
            name = ''.join(name)

            c = []
            while (i < n and s[i] >= '0' and s[i] <= '9'):
                c.append(s[i])
                i += 1
            if (not c):
                c = 1
            else:
                c = int(''.join(c))

            if name in now:
                now[name] += c
            else:
                now[name] = c
        elif s[i] == '(':
            need = 1
            ed = i+1
            while (need > 0):
                if (s[ed] == '('):
                    need += 1
                elif (s[ed] == ')'):
                    need -= 1
                ed += 1
            tmp = parse(s[i+1:ed-1])
            c = []
            while (ed < n and s[ed] >= '0' and s[ed] <= '9'):
                c.append(s[ed])
                ed += 1
            if (not c):
                c = 1
            else:
                c = int(''.join(c))
            # update to now
            for k, v in tmp.items():
                if k in now:
                    now[k] += v*c
                else:
                    now[k] = v*c
             
            i = ed
    return now

ip = input()
ip = ip.replace('[', '(')
ip = ip.replace(']', ')')
out = parse(ip)
out = sorted(out.items())
for (key, val) in out:
    print("%s%d" %(key, val), end='')
print()
1

自动机解析字符串

#include <bits/stdc++.h>
using namespace std;

void analyse(map<string, int>& element, const string& input, int& i) {
    int state = 0;
    int len = input.size();
    while (i < len) {
        switch (state) {
        //初始态:扫描
        case 0: {
            if (i < len && input[i] >= 'A' && input[i] <= 'Z') {
                state = 1;
            }
            else if (i < len && input[i] == '[' || input[i] == '(') {
                state = 2;
            }
            else if (i < len && input[i] == ']' || input[i] == ')') {
                i++;
                return;
            }
            else {
                i++;
            }
            break;
        }
        //处理单个原子
        case 1: {
            string name = "";
            string number_str = "";
            name += input[i++];
            while (i < len && input[i] >= 'a' && input[i] <= 'z') {
                name += input[i++];
            }
            while (i < len && input[i] >= '0' && input[i] <= '9') {
                number_str += input[i++];
            }
            if(!element.count(name)){
                element[name] = number_str == ""? 1 : stoi(number_str); 
            }
            else{
                element[name] += number_str == ""? 1 : stoi(number_str); 
            }
            state = 0;
            break;
        }
        //遇到括号就递归
        case 2: {
            map<string, int> temp;
            i++;
            analyse(temp, input, i);
            string number_str = "";
            while (i < len && input[i] >= '0' && input[i] <= '9') {
                number_str += input[i++];
            }
            int number = number_str == "" ? 1 : stoi(number_str);
            for (auto& [k, v] : temp) {
                element[k] += v * number;
            }
            state = 0;
            break;
        }
        }
    }
}
int main() {
    string input;
    cin >> input;
    map<string, int> element;
    int i = 0;
    analyse(element, input, i);
    for (auto& [v, k] : element) {
        cout << v << k;
    }
    return 0;
}

python3击败100%
思路:
1.定义结构体描述化学元素,符号+个数
2.定义一个栈,遇到左括号和化学元素时压入,遇到右括号时弹出,并向后访问一个数字计算括号内的元素个数
3.将stack中重复的元素合并
4.按照字典序排序
注意:
1.括号后面可能没有数字
2.加入元素时的往后取一位,如果是大写字母,括号,数字都表示元素符号已经取到;

测试用例:


if __name__ == "__main__":
    string = "K4[ON(SO3)2]2"
    string2 = "Ca(HSO4)2"
    string3 = "Na(OH)"
    string4 = "Cu(SO4)"
    string5 = "MgO4"
    parse(string5)
# 模拟题
# 化学符号解析
'''
给定一个用字符串展示的化学公式,计算每种元素的个数。
规则如下:

元素命名采用驼峰命名,例如 Mg
() 代表内部的基团,代表阴离子团
[] 代表模内部链节通过化学键的连接,并聚合
例如:H2O => H2O1 Mg(OH)2 => H2Mg1O2

输入描述:
化学公式的字符串表达式,例如:K4[ON(SO3)2]2

输出描述:
元素名称及个数:K4N2O14S4,并且按照元素名称升序排列

测试用例
输入
K4[ON(SO3)2]2
输出
K4N2O14S4
'''
class elem(object):
    def __init__(self, c, n):
        self.nums = n
        self.char = c


def parse(string):
    stack = []
    i = 0
    while i < len(string):
        c = string[i]
        if c == "(" or c == "[":
            stack.append(c)
        elif c == ")" or c == "]":
            tmp = []
            i += 1
            if i >= len(string):
                c = '1'
            else:
                c = string[i]
            if not c.isdigit():
                i -= 1
                c = 1
            else:
                c = int(c)
            while 1 :
                # print(stack)
                em = stack.pop()
                if em == "(" or em == "[":
                    break
                em.nums = em.nums * c
                tmp.append(em)
            if tmp:
                stack.extend(tmp)
        else:
            s = "" + c
            nums = 1
            while 1:
                i += 1
                if i >= len(string):
                    break
                c = string[i]
                if c.isupper():
                    i-=1
                    break
                elif c.isdigit():
                    nums = int(c)
                    break
                elif c in ["(", "[", ")", "]"]:
                    i -= 1
                    break
                else:
                    s += c
            em = elem(s, nums)
            stack.append(em)
        i += 1
    i, j = 0, 0
    while i < len(stack):
        j = i+1
        while j < len(stack):
            if stack[i].char == stack[j].char:
                stack[i].nums += stack[j].nums
                stack.pop(j)
            j += 1
        i+=1
    stack.sort(key=lambda em : em.char[0])
    string = ''
    for em in stack:
        string += em.char + str(em.nums)
    print(string)
string = input()
parse(string)