stacksequence.java

对确定的输入序列和一个给定的输出序列

import java.io.*;
class StackNode{
    int stackData = 0;
    StackNode prev = null;
    StackNode next = null;
    StackNode(int input) {stackData = input;}
}

class IntStack{
    StackNode tail = new StackNode(0);
    int length = 0;

    boolean isEmpty(){
        if (length == 0)
            return true;
        else
            return false;
    }

    void push(int input){
        StackNode create = new StackNode(input);
        create.next = null;
        create.prev = tail;
        tail.next = create;
        tail = create;
        length++;
    }
    int pop(){
        int data = tail.stackData;
        tail.prev.next = null;
        tail = tail.prev;
        length--;
        return data;
    }
    int top(){
        return tail.stackData;
    }    
}

public class StackSequence{
    public static boolean judgeSequence(int[] sequence){
        int[] workshop = new int[sequence.length];
        int amount = sequence.length;
        for (int i=0; i<amount; i++)
            workshop[i] = i+1;
        IntStack iStack = new IntStack();
        for (int i=0; i<sequence.length; i++){
            int target = sequence[i];
            if (iStack.isEmpty()){
                int pos = find(target, workshop, amount); //pos must be greater than -1
                for (int j=0; j<pos; j++)
                    iStack.push(workshop[j]);
                for (int j=0; j<amount-pos-1; j++)
                    workshop[j] = workshop[j+pos+1];
                amount -= (pos+1);
            }
            else{//iStack is not empty
                int topData = iStack.top();
                if (target == topData){
                    iStack.pop();
                    continue;
                }
                else{ // topData != iStack.top();
                    int pos = find(target, workshop, amount);
                    if (pos == -1) return false;
                    for (int j=0; j<pos; j++)
                        iStack.push(workshop[j]);
                    for (int j=0; j<amount-pos-1; j++)
                        workshop[j] = workshop[j+pos+1];
                    amount -= (pos+1);
                }
            }
        }
        return true;
    }
    public static int find(int target, int[] array, int amount){
        int pos = -1;
        for (int i=0; i<amount; i++){
            if (array[i] == target){
                pos = i;
                break;
            }
        }
        return pos;
    }

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line = "";
        while(true){
            System.out.println("请输入一个待判断的输出序列：");
            line = br.readLine();
            if (line.equals("finish"))
                return;
            String[] numbers = line.split(" ");
            int[] sequence = new int[numbers.length];
            for (int i=0; i<numbers.length; i++){
                sequence[i] = Integer.parseInt(numbers[i]);
            }
            boolean result = judgeSequence(sequence);
            if (result)
                System.out.println("你给出的是合法输出序列");
            else
                System.out.println("你给出的是非法输出序列");
            System.out.println();
        }
    }
}