CCF/CSP 化学方程式

题目版权归来源方所有 题目版权归来源方所有
判题结果

题目来源：CCF 化学方程式

【解题思路】： 【栈】

1.分割等号 ‘=’ ，左右两边是一致的解题方式

2.再分割加号 ‘+’ ，对每一个化学式进行统计

3.对于存在括号嵌套的情况下，使用栈进行匹配

【示例】：以 4Al(Cu(OH)2)3 为例（瞎写的，我的化学已经还给老师了）

1.先获得化学式最前面的系数，在这里是 4，如果没有就设为 1；

2.有两个栈，一个num存放数字，一个fu（随便起的）存放符号（包括括号和化学式的项）

一开始：

        num    1           1           1     1

        fu     Al   (     Cu    (    O    H

如果化学式后面没有系数，那么就设为1，在这里需要判断是O这种只有一个大写字母项的形式还是Al这种两个字母的项的形式。遇到左括号直接入符号栈。

遇到 ‘)’：

        num    1           1       2     2

        fu     Al   (     Cu     O    H

一直出栈到遇到左括号，用辅助栈把因为括号出栈的数字和符号暂时存储，把左括号出栈。记得获得右括号后边的数字。如果没有就为1。在这里数字是2，把辅助栈里的信息push回去的时候需要乘上这个数字2。

再遇到 ‘)’ ：

        num    1       3       6     6

        fu     Al     Cu     O    H

最后，此时字符串遍历结束，把这些化学式存进 Map<String, Integer> 里面，记得乘上最开始时的系数 4.

存进Map的结果：

        String    Al    Cu    O    H

        Integer  4      12    24   24

对每一个化学式进行这样的统计，最后判断等号两边的两个 Map 是否相同就是答案。

【附上垃圾代码】：代码难免有冗余的地方，需要大家改进咯

import java.util.*;

public class Main {
    public static void main(String[] args) {
        new Main().solve();
    }

    public void solve() {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        sc.nextLine();
        for (int i=0; i<n; i++) {
            String str = sc.nextLine();
            String [] arr = str.split("=");
            if (createMap(arr[0]).equals(createMap(arr[1]))) {
                System.out.println("Y");
            }
            else {
                System.out.println("N");
            }
        }
    }

    public Map<String, Integer> createMap(String str) {
        String [] arr = str.split("\\+");

        Map<String, Integer> map = new HashMap<>(arr.length);
        Deque<Integer> num = new ArrayDeque<>();
        Deque<String> fu = new ArrayDeque<>();
        // 两个辅助栈，不知道有没有更好的方法，不用这两个栈
        Deque<Integer> f_num = new ArrayDeque<>();
        Deque<String> f_fu = new ArrayDeque<>();

        for (String a : arr) {

            int n = 0,i=0;
            boolean flag = false;

            // 获得最前面的系数
            for (; i<a.length(); i++) {
                char c = a.charAt(i);
                if (judge(c)==2) {
                    n = n*10 + c-'0';
                }
                else {
                    break;
                }
            }
            n = (n==0)?1:n;

            int m = 0,len = a.length();
            for (; i<len; i++) {
                char c = a.charAt(i);
                // 获得数字
                if (judge(c)==2) {
                    m = m*10 + c-'0';
                    flag = true;
                }
                else {
                    if (flag) {
                        num.push(m);
                        m = 0;
                        flag = false;
                    }
                    if (judge(c)==1) {
                        // 单个字母的项如：H
                        if (i+1 == len || judge(a.charAt(i+1))!=0) {
                            fu.push(a.substring(i,i+1));
                            // 如果后面没数字，就直接设为1
                            if (i+1==len || judge(a.charAt(i+1))!=2)
                                num.push(1);
                            continue;
                        }
                        // 两个字母的项：Al
                        else if (i+1 != len && judge(a.charAt(i+1))==0) {
                            fu.push(a.substring(i,i+2));
                            // 如果后面没数字，就直接设为1
                            if (i+2 == len || judge(a.charAt(i+2))==3 || judge(a.charAt(i+2))==1) {
                                num.push(1);
                            }
                            i++;
                            continue;
                        }
                    }
                    if (c == '(') {
                        fu.push("(");
                        continue;
                    }
                    if (c == ')') {
                        int k = 0,j=i+1;
                        // 获得右括号后边的数字
                        for (; j<len; j++) {
                            if (judge(a.charAt(j))==2)
                                k = k*10 + a.charAt(j)-'0';
                            else break;
                        }
                        if (k==0) {
                            k=1;
                        }
                        else {
                            i = j-1;
                        }
                        while ( !fu.isEmpty() && !fu.peek().equals("(")) {
                            f_fu.push(fu.pop());
                            f_num.push(num.pop()*k);
                        }
                        fu.pop();
                        while ( !f_fu.isEmpty() ) {
                            num.push(f_num.pop());
                            fu.push(f_fu.pop());
                        }
                    }
                }
            }
            if (m!=0) num.push(m);
            while (!fu.isEmpty()) {
                String q = fu.pop();
                map.put(q, map.getOrDefault(q, 0) + num.pop()*n);
            }
        }
        return map;
    }

    public int judge(char a)  {
        if (a == '(' || a == ')') {
            return 3;
        }
        if (a >= '0' && a <= '9') {
            return 2;
        }
        if (a >= 'A' && a <= 'Z') {
            return 1;
        }
        return 0;
    }

}