化学方程式-ccf

题目：

分析：类似于计算运算表达式。

　　1、辅助数据结构：

　　　　（1）数组：使用52位整型数组表示52个字母。检索左部分所有表达式时，记录字母出现的次数；检索右部分所有表达式时，减去字母出现的次数。当左右表达式匹配时，数组的所有元素应该为0.

　　　　（2）字符栈：存取字符。

　　2、化学表达式预处理：

　　　　（1）通过"="，将方程式分割为左右两部分。

　　　　（2）通过"+"，将左右子串分别分割为更小的子表达式。

　　3、子表达式处理：

　　　　（1）设置前导值：左部分表达式，如果首位为数字，则前导值为首位的数字，否则默认为1；右部分同理，但是需要将值取反。

　　　　（2）表达式遍历：顺序遍历过程中穿插有递归操作。当遇到前括号时，首先判断紧跟后括号的值是否为数组（此处对后括号的判断导致无法处理平行括号，如果存在平行括号，表达式计算将出现错误），然后更新前导值，将括号内的字符串进行递归操作。

　　4、问题中的规律：

　　　　（1）前导值作用于每个字母。

　　　　（2）其他数字：如果是紧跟随后括号，将作用于括号中的所有值，效果等效于前导值；如果是跟随在大写字母后，只作用与前面一个字母；如果是跟随在小写字母后，作用范围为当前位置到前序位置的第一个大写字母。

code：结果只有60分，还需要继续改进。我的代码只处理了嵌套括号，没有处理平行括号。

  1 package yrc1;
  2 import java.util.*;
  3 
  4 /**
  5  * 只获得60分，还需要完善
  6  * 算法思想：
  7  * 
  8  * 2、使用52位长度的整型数组作为辅助。检索左字符串时，记录字母在字符串中出现的次数；
  9  * 检索右字符串时，减去字母在字符串中出现的次数。
 10  *
 11  *      (1)通过"+"将字符串分割为多个表达式
 12  */
 13 public class Main4 {
 14     public static  void main(String args[]) {
 15         Scanner in = new Scanner(System.in);
 16         int n = in.nextInt();
 17         in.nextLine();
 18 
 19         while(n>0){
 20             String str = in.nextLine();
 21             String[] one = str.split("=");
 22             String left  = one[0];
 23             String right = one[1];
 24             int[] dp = new int[52];
 25             String[] leftson;
 26 
 27             if(left.contains("+")){
 28                 leftson = left.split("\+");
 29             }else{
 30                 leftson = new String[1];
 31                 leftson[0] = left;
 32             }
 33             for(int i=0;i<leftson.length;i++){
 34                 int bs = 1;
 35 
 36                 if(Character.isDigit(leftson[i].charAt(0))){
 37                     bs = leftson[i].charAt(0)-'0';
 38                     int j=1;
 39                     for(;j<leftson[i].length() && Character.isDigit(leftson[i].charAt(j));j++){
 40                         bs = bs*10+leftson[i].charAt(j)-'0';
 41                     }
 42                     leftson[i] = leftson[i].substring(j);
 43                 }
 44                 fun1(dp,bs,leftson[i]);
 45             }
 46 
 47             String[] rightson;
 48             if(right.contains("+")){
 49                 rightson = right.split("\+");
 50             }else{
 51                 rightson = new String[1];
 52                 rightson[0] = right;
 53             }
 54             for(int i=0;i<rightson.length;i++){
 55                 int bs = 1;
 56                 if(Character.isDigit(rightson[i].charAt(0))){
 57                     bs = rightson[i].charAt(0)-'0';
 58                     int j=1;
 59                     for(;j<rightson[i].length() && Character.isDigit(rightson[i].charAt(j));j++){
 60                         bs = bs*10+rightson[i].charAt(j)-'0';
 61                     }
 62                     rightson[i] = rightson[i].substring(j);
 63                 }
 64                 fun1(dp,-bs,rightson[i]);
 65             }
 66 
 67 
 68             //a-z:97-122,A-Z:65-90,0-9:48-57
 69             boolean flag = true;
 70             for(int i=0;i<dp.length;i++){
 71                 if(dp[i]!=0){
 72                     flag = false;
 73                     break;
 74                 }
 75             }
 76 
 77             if(flag){
 78                 System.out.println("Y");
 79             }else{
 80                 System.out.println("N");
 81             }
 82             n--;
 83         }
 84     }
 85     //只处理了嵌套括号，没有处理平行括号
 86     public static void fun1(int[] dp,int bs,String str){
 87         Stack<Character> charStack = new Stack<>();
 88         for(int i=0;i<str.length();i++){
 89             char c = str.charAt(i);
 90             if(Character.isDigit(c)){      //处理非个位数
 91                 int res = c-'0';
 92                 int j=i+1;
 93                 for(;j<str.length() && Character.isDigit(str.charAt(j));j++){
 94                     res = res*10+(str.charAt(j)-'0');
 95                 }
 96                 i = j-1;
 97                 while (!charStack.empty() && charStack.peek()>=97){
 98                     dp[charStack.peek()-71] = dp[charStack.pop()-71]+res*bs;
 99 
100                 }
101                 if(!charStack.empty() && charStack.peek()<=90){
102                     dp[charStack.peek()-65] = dp[charStack.pop()-65]+res*bs;
103                 }
104             }else if(c=='('){
105                 int index = str.lastIndexOf(")");
106                 int newbs=bs;
107                 int curdigit=0;
108                 int j = index+1;
109                 for(;j<str.length() && Character.isDigit(str.charAt(j));j++){
110                     curdigit = curdigit*10+(str.charAt(j)-'0');
111                 }
112                 newbs = curdigit==0?bs:curdigit*bs;
113                 fun1(dp,newbs,str.substring(i+1,index));
114                 i = j-1;
115             }
116             else{
117                 charStack.push(c);
118             }
119         }
120         while(!charStack.empty()){
121             char c = charStack.pop();
122             int index = 0;
123             if(c>=97){
124                 index = c-71;
125             }else{
126                 index = c-65;
127             }
128             dp[index] = dp[index]+bs;
129         }
130     }
131 }