2
\$\begingroup\$

I'm currently working through "Algorithms in java" by Robert Sedgewick (3rd edition, in german) on my own and am trying to solve one of the exercises there.

The exercise asks to develop and implement an Algorithm for Pushdown-Stacks. The algorithm receives a character sequence A and a character sequence B. It should be capable to determine if there is any order in which pop operations could be used on A, so that you create a pop-order that is identical to B.

E.g. can E A S Y Y be pop'ed in a way that the pop-Order is Y Y S E A (pop-order illegal/impossible) or Y Y S A E (pop-order legal/possible).

Elements on the stack are not unique and identical elements can not be distinguished.

I looked for an answer on stackoverflow found this, in which the following algorithm is proposed:

For each number X in the pop order:

  • If this number is not the same as the top of the stack (or the stack is empty), push numbers from the push order until you pushed X. If you pushed all numbers and didn't find X, there's no way to get the pop order.
  • Pop X

I could not come up with any scenarios in which the above algorithm would not deliver the desired results, so I wrote an implementation which for my current tests returns the correct results.

public class Aufgabe4_7 {

    /*
     * Implement Stack as the following: A stack is an integer called "index"
     * and an array with the length of the maximum length the stack can have
     * based on the String input. "index" is always +1 above the position of the
     * top element and therefore always the index of an empty cell. All cells in
     * charStack are initially char's equivalent of null.
     */
    static class Stack {
        char[] charStack;
        int index;

        Stack(int charStackLength) {
            this.index = 0;
            this.charStack = new char[charStackLength];
        }

        public void push(char c) {
            charStack[this.index] = c;
            this.index++;
        }

        public char pop() {
            if (this.index == 0) {
                return Character.MIN_VALUE;
            } else {
                this.index--;
                char c = charStack[this.index];
                charStack[this.index] = Character.MIN_VALUE;
                return c;
            }
        }

        public char viewTopElement() {
            if (this.index > 0) {
                return charStack[this.index - 1];
            } else {
                return Character.MIN_VALUE;
            }
        }
    }

    /*
     * pushIndex tracks the index the first cell of charAr that has not been
     * pushed from charAr onto the current Stack yet. charAr contains the
     * character array of the String for which we test if a given pop order is
     * legal or not.
     */
    static int pushIndex;
    static char[] charAr;

    public static void main(String[] args) {

        charAr = args[0].toUpperCase().toCharArray();
        char[] popOrder = args[1].toUpperCase().toCharArray();

        /*
         * For each popOrder[i] check if the current top element of charStack is
         * equal to popOrder[i]. If not, push() elements from charAr onto
         * charStack until the top element == popOrder[i]. If there is no such
         * element (pushingPossible = false while charStack top element !=
         * popOrder[i]) escape the loop. If there is such an element, pop() it
         * and go to the next loop iteration.
         */
        Stack charStack = new Stack(charAr.length);
        int i;
        for (i = 0; i < popOrder.length; i++) {
            while (pushingPossible() && (charStack.viewTopElement() != popOrder[i])) {
                pushNext(charStack);
            }

            if (!pushingPossible() && (charStack.viewTopElement() != popOrder[i])) {
                break;
            }
            charStack.pop();
        }

        /*
         * i == popOrder.length only under the condition that the forLoop was
         * finished without triggering the if-condition. This is only possible
         * if the popOrder is legal for the given character sequence
         */
        if (i == popOrder.length) {
            System.out.println("The given popOrder is legal for the given character sequence.");
            printPopAndCharAr(popOrder);
        } else {
            System.out.println("The given popOrder is not legal for the given character sequence.");
            printPopAndCharAr(popOrder);
        }
    }

    /** Further Methods of "Aufgabe4_7" **/
    /*
     * Pushes the first cell from charAr that has not been pushed onto the
     * charStack yet, onto the charStack
     */
    private static void pushNext(Stack st) {
        if (pushIndex < charAr.length) {
            st.push(charAr[pushIndex]);
            pushIndex++;
        }
    }

    /*
     * Tests if there are still cells in charAr that can be pushed onto the
     * charStack
     */
    private static boolean pushingPossible() {
        if (pushIndex < charAr.length) {
            return true;
        } else {
            return false;
        }
    }

    /* 
     *Print out the contents of popOrder and charAr. Only for checking purposes. 
     */
    private static void printPopAndCharAr(char[] popOrder) {
        System.out.print("Character Sequence: ");
        for (int j = 0; j < charAr.length; j++) {
            System.out.print(charAr[j] + " ");
        }
        System.out.println();
        System.out.print("popOrder: ");
        for (int j = 0; j < popOrder.length; j++) {
            System.out.print(popOrder[j] + " ");
        }
        System.out.println();
    }
}

My main questions are:

  1. Was it acceptable style to track the index of the next Element to be pushed onto charStack (pushIndex) "externally" by using a static reference? It "feels" correct since it allowed me to simplify the code and not keep track of pushIndex in the main method, but I'm uncertain about it.
  2. As indicated, I am not convinced that the algorithm always returns the correct answer. I am currently of the opinion I might have just not found the cases for which this algorithm does not return the correct answer.
  3. What could I have done to improve performance or readability of the code?
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.