给定出栈序列和入栈序列，求出栈入栈顺序

亚马逊在线测评题：

大牛写的代码，学习一下编码风格

/* Enter your code here. Read input from STDIN. Print output to STDOUT */
import java.util.Scanner;
import java.util.StringTokenizer;

public class Solution 
{
	public String calculateOperationSequence(int[] originalArray, int[] resultArray) 
	{
		int[] numStackState = new int[originalArray.length];//0 have not pushed, 1 have pushed, 2 have poped
		for (int i = 0; i < numStackState.length; ++i) {
			numStackState[i] = 0;
		}
		StringBuffer result = new StringBuffer();
		for (int i = 0; i < resultArray.length; ++i) {
			int indexInOriginal = -1;
			for (int j = 0; j < originalArray.length; ++j) {
				if (originalArray[j] != resultArray[i]) {
					if (numStackState[j] == 0) {
						result.append("push");
						result.append(originalArray[j]);
						result.append("|");
						numStackState[j] = 1;
					}
				} else if (originalArray[j] == resultArray[i]) {
					if (numStackState[j] == 0) {
						result.append("push");
						result.append(originalArray[j]);
						result.append("|");
						numStackState[j] = 1;
					} else if (numStackState[j] == 2) {
						return "None";
					}
					indexInOriginal = j;
					break;
				}
			}
			if (indexInOriginal == -1) {
				return "None";
			}
			for (int j = indexInOriginal + 1; j < originalArray.length; ++j) {
				if (numStackState[j] == 1) {
					return "None";
				}
			}
			result.append("pop");
			result.append(resultArray[i]);
			result.append("|");
			numStackState[indexInOriginal] = 2;
		}
		return result.substring(0, result.length() - 1);
	}

	
	
	/**
	* StringTokenizer的用法（有点类似于split）
	 一、构造函数。
	1. StringTokenizer(String str) ：构造一个用来解析str的StringTokenizer对象。java默认的分隔符是“空格”、“制表符(‘\t’)”、“换行符(‘\n’)”、“回车符(‘\r’)”。
	2. StringTokenizer(String str, String delim) ：构造一个用来解析str的StringTokenizer对象，并提供一个指定的分隔符。
	3. StringTokenizer(String str, String delim, boolean returnDelims) ：构造一个用来解析str的StringTokenizer对象，并提供一个指定的分隔符，同时，指定是否返回分隔符。
	
	二、方法。
	说明：
	1. 所有方法均为public；
	2. 书写格式：［修饰符］　<返回类型> <方法名（［参数列表］）>
	如：static int parseInt(String s) 表示：此方法（parseInt）为类方法（static），返回类型为（int），方法所需参数为String类型。
	1. int countTokens() ：返回nextToken方法被调用的次数。如果采用构造函数1和2，返回的就是分隔符数量(例2)。
	2. boolean hasMoreTokens() ：返回是否还有分隔符。
	3. boolean hasMoreElements() ：结果同2。
	4. String nextToken() ：返回从当前位置到下一个分隔符的字符串。
	5. Object nextElement() ：结果同4。
	6. String nextToken(String delim) ：与4类似，以指定的分隔符返回结果。
	* @param args
	*/
	public static void main(String[] args) 
	{
		Solution solution = new Solution();
		Scanner scanner = new Scanner(System.in);  //当通过new Scanner(System.in)创建一个Scanner，控制台会一直等待输入，直到敲回车键结束，把所输入的内容传给Scanner，作为扫描对象。如果要获取输入的内容，则只需要调用Scanner的nextLine()方法即可。

		
		while (scanner.hasNextLine()) 
		{
			String strLine1 = scanner.nextLine();
			StringTokenizer stringTokenizer1 = new StringTokenizer(strLine1);
			
			//Initialize the original array
			int arrayLength = stringTokenizer1.countTokens();
			int[] originalArray = new int[arrayLength];
			for(int i = 0; i < arrayLength; i++)
			{
				originalArray[i] = Integer.parseInt(stringTokenizer1.nextToken());
			}
			
			//Initialize the result array
			String strLine2 = scanner.nextLine();
			StringTokenizer stringTokenizer2 = new StringTokenizer(strLine2);
			arrayLength = stringTokenizer2.countTokens();
			int[] resultArray = new int[arrayLength];
			for(int j = 0; j < arrayLength; j++)
			{
				resultArray[j] = Integer.parseInt(stringTokenizer2.nextToken());
			}
			
			String operationSequence = solution.calculateOperationSequence(originalArray, resultArray);
			System.out.println(operationSequence);
		}
	}
}

 

 

自己写的一个实现函数：

	private String calculateOperationSequence(int[] originalArray, int[] resultArray){
		StringBuffer rs = new StringBuffer();
		
		int[] numStackState = new int[originalArray.length];
		for(int i=0 ; i<numStackState.length ; i++){
			numStackState[i] = 0;
		}
		
		for(int i=0 ; i<resultArray.length ; ++i){
			for(int j=0 ; j<originalArray.length ; ++j){
				if(resultArray[i] != originalArray[j]){
					if(numStackState[j] == 0){
						numStackState[j]=1;
						rs.append("Push:"+originalArray[j]+";");
					}
				}else if(resultArray[i] == originalArray[j]){
					if(numStackState[j] == 0){
						rs.append("Push:"+originalArray[j]+";");
						rs.append("Pop:"+originalArray[j]+";");
						numStackState[j]=2;
						break;
					}else if(numStackState[j] == 1){
						if(numStackState[j+1] == 1){
							rs.append("出栈顺序不合法");
							return rs.toString();
						}else{
							rs.append("Pop:"+originalArray[j]+";");
							numStackState[j]=2;
							break;
						}
					}else{
						rs.append("出栈顺序不合法");
						return rs.toString();
					}
				}
			}	
		}
		
		return rs.toString();
	}