化学方程式解析算法

package test 
{
	import flash.display.Sprite;
	/**
	 * 群里某个公司的编程题，我觉得挺难，花了半个小时完成，需要词法分析。语法分析。虚拟机计算结果。简直是一个是需要写一个小型的编译器加虚拟机。
	 * 二、编程题
输入任意一种物质，要求输出其每种元素的数量。
比如
输入 CaCO3，其组成分别为 Ca：1，C：1，O：3，输出 Ca1C1O3
输入 Fe2(SO4)3，其组成分别为 Fe：2，S：3，O：12，输出 Fe2S3O12
（注意：元素名称首字母大写，剩余字母都小写；括号括起来表示括号中的结构作
为整体出现多少次
	 * @author lizhi
	 */
	public class Test extends Sprite  
	{
		public function Test()  
		{
			exe("Fe2(SO4)3");
			exe("Fe2(SO12)3");
			exe("Fe2(S((B3)2)3O12)3");
			/**
			 * ----------------------
----------------------
Fe2(SO4)3
Fe,2,(,S,O,4,),3
Fe2S3O12
----------------------
Fe2(SO12)3
Fe,2,(,S,O,12,),3
Fe2S3O36
----------------------
Fe2(S((B3)2)3O12)3
Fe,2,(,S,(,(,B,3,),2,),3,O,12,),3
Fe2S3B54O36
*/
		}
		
		private function exe(str:String):void{
			trace("----------------------\n"+str);
			//lex 词法分析
			var tks:Array = [];
			var tk:Tok;
			for (var i:int = 0; i < str.length; i++ ){
				var c:String = str.charAt(i);
				if (c>="A"&&c<="Z"){
					tk = new Tok();
					tk.type = 0;
					tk.char = c;
					tks.push(tk);
				}else if (c>="a"&&c<="z"){
					tk.char += c;
				}else if (c=="("){
					tk = new Tok();
					tk.char = c;
					tk.type = 1;
					tks.push(tk);
				}else if (c==")"){
					tk = new Tok();
					tk.char = c;
					tk.type = 2;
					tks.push(tk);
				}else {
					if (tk&&tk.type==3){
						tk.char += c;
					}else{
						tk = new Tok();
						tk.type = 3;
						tk.char = c;
						tks.push(tk);
					}
				}
			}
			trace(tks);//Fe,2,null,S,O,45,null,3
			
			//语法分析，生成语法树
			var rootNode:Node = new Node;
			var lastRootNode:Node = rootNode;
			var node:Node;
			for (var i:int = 0; i < tks.length;i++ ){
				var tk:Tok = tks[i];
				if (tk.type==0){//word
					node = new Node;
					node.char = tk.char;
					lastRootNode.child.push(node);
					node.parent = lastRootNode;
				}else if (tk.type==1){//(
					node = new Node;
					lastRootNode.child.push(node);
					node.parent = lastRootNode;
					lastRootNode = node;
				}else if (tk.type == 2){//)
					node = lastRootNode;
					lastRootNode = lastRootNode.parent;
				}else{//num
					node.num = parseInt(tk.char);
				}
			}
			
			//虚拟机 vm计算结果
			var out:String = count(rootNode, 1);
			trace(out);
		}
		
		private function count(n:Node, mul:int):String{
			var num:int = n.num * mul;
			if(n.char){
				var out:String = n.char + num;
			}else{
				out = "";
			}
			for (var i:int = 0; i < n.child.length;i++ ){
				out += count(n.child[i],num);
			}
			return out;
		}
	}
}

class Tok{
	public var char:String;
	public var type:int;
	
	public function toString():String{
		return char;
	}
}
class Node{
	public var char:String;
	public var child:Array = [];
	public var num:int = 1;
	public var parent:Node;
}