Exercises - Using Stacks II

  1. Below is a method which uses a stack of integers with typical push and pop operations:

    public static int foo(int x, int y) {
       if (x <= 0 || y <= 0)
          return 0;
       stack.push(y);
       return foo(x - 1, y-1) + stack.pop();
    }
    

    Assuming the stack is initially empty, draw a snapshot of the stack after every push and pop statement for each recursive call for foo(3,4). Label each stack snapshot with the recursive call, and the push or pop statement. For example, the following shows the first two snapshots of the stack after the push statement for the call foo(3,4) and after the push statement for the call foo(2,3).

     4
    ---
    foo(3,4) - push
    
     3
     4
    ---
    foo(2,3) - push
    

    To what integer value does foo(3,4) evaluate when invoked?

    
                           2
                  3        3        3
       4          4        4        4       4
    ========  ========  ======== ======= ======= =======
    foo(3,4)  foo(2,3)  foo(1,2)   pop     pop     pop
      push     push       push
    
    foo(3,4) = foo(2,3) + pop
    foo(2,3) = foo(1,2) + pop
    foo(1,2) = foo(0,1) + pop
    foo(0,1) = 0
    
    So,
    
    foo(1,2) = 0 + 2 = 2
    foo(2,3) = 2 + 3 = 5
    foo(3,4) = 5 + 4 = 9  <-- final answer = 9
    

  2. In using the shunting yard algorithm to convert A - (B ^ C ^ D * E) + F / G from partially parenthesized infix form to postfix form, list the elements that are popped from the operator stack in the order they are popped.

    ^ ^ * ( - / +

  3. Write a class ShuntingYard that prompts the user to enter an expression in infix form (possibly only partially parenthesized), and then prints an equivalent expression in fully parenthesized postfix form -- where operators come after their operands.

    You may assume that the user input will separate operands, operators, and parentheses with spaces, and the operators include only "+", "-", "*", "/", and "^".

    $ java ShuntingYard↵
    Enter an infix expression to convert to postfix form:
    ( A ^ B ^ C * ( D - E ) )↵
    A B C ^ ^ D E - *
    
  4. Expand the class ShuntingYard by adding a method named toPreFix(String s) and changing the main(String[] args) method so that it prompts the user to enter an expression in infix form (possibly only partially parenthesized), and then prints an equivalent expression in fully parenthesized prefix form -- where operators come before their operands, and every operator and its operands appear in parentheses. A sample run is shown below.

    You may assume that the user input will separate operand and operator tokens with spaces, and the operators include only "+", "-", "*", "/", and "^".

    $ java ShuntingYard↵
    Enter an infix expression to convert to prefix form:
    A + B * C ^ D - E↵
    ( - ( + A ( * B ( ^ C D ) ) ) E )
    
  5. One can solve the N-Queens problem by implementing a backtracking algorithm using a stack. Show the values of such a stack after each push or pop operation for 4-Queens problem until the first solution is found.

                                                 2
                     1                       0   0
         2       3   3   3               3   3   3
     0   0   0   0   0   0   0       1   1   1   1
    === === === === === === === === === === === ===
    

  6. Complete the implementation of the class NQueensSolver that prompts the user for a board size, and then finds and prints all solutions to the NQueens problem (i.e., placing $n$ queens on an $n \times n$ board so that no queen can attack any other) for that size board, as the sample run below suggests.

    Use an explicit stack and backtracking instead of recursion to keep track of the positions of the queens placed so far.

    Hint: an $8 \times 8$ board has 92 solutions.

    $ java NQueens↵
    Enter board size to solve:
    4↵
     *  Q  *  * 
     *  *  *  Q 
     Q  *  *  * 
     *  *  Q  * 
    
     *  *  Q  * 
     Q  *  *  * 
     *  *  *  Q 
     *  Q  *  * 
    
    Solutions Found: 2
    
  7. In a Sudoku puzzle, one is given a partially filled $9 \times 9$ grid. The goal is to assign digits (from 1 to 9) to the empty cells so that every row, column, and $3 \times 3$ subgrid contains exactly one instance of the digits from 1 to 9.

    Complete the implementation of the class SudokuSolver whose constructor accepts a 2d-array of ints representing a sudoku puzzle (where entries of $0$ in the array signify empty cells), and whose solve() and printGrid() methods can be used to calculate and print the solution to the puzzle, as the sample run below suggests.

    Use an explicit stack and backtracking instead of recursion to keep track of the numbers filled in the blanks during the solution process.

    Hint: use the stack to store the positions of the filled blanks, while storing the numbers filling these blanks in an array. The Point class provides a convenient way to represent the positions, as it wraps two integers (row and col) into a single object.

    $ java SudokuSolver↵
    Testing solvable puzzle...
    
    1 3 9 6 2 4 7 8 5 
    2 4 8 7 5 9 1 6 3 
    6 7 5 3 8 1 2 9 4 
    8 1 4 9 3 7 5 2 6 
    9 6 2 8 1 5 4 3 7 
    3 5 7 2 4 6 8 1 9 
    4 9 1 5 6 2 3 7 8 
    5 8 6 1 7 3 9 4 2 
    7 2 3 4 9 8 6 5 1 
    
    =================
    
    Testing unsolvable puzzle...
    
    No solution exists
    
  8. In the game of chess, a knight is a piece often shaped in the form of a horse's head and neck, that in one move can travel to any other space on the board that is either up/down 2 spaces and left/right 1 space from its current location, or left/right 2 spaces then up/down 1 space from its current location. In the course of doing so, knights may "jump" over any other pieces in their paths. This means that a knight may move in up to 8 different ways from a given square it occupies, as shown below.

    A knight's tour is a sequence of moves of a knight on a chessboard whereby the knight visits every square exactly once.

    Complete the class KnightsTourSolver which imagines a $n \times n$ chessboard as an array and finds all knight's tours of that board starting with the position in the upper left corner, which is presumed to be the position in row $0$ and column $0$ of the corresponding array.

    Finding these tours should be accomplished using a stack-based backtracking algorithm (do not use recursion), where legal moves are explored in the order enumerated in the image above. Solutions found should be numbered and displayed as two-dimensional arrays showing the order in which each cell is visited, in a manner consistent with the portion of the sample run shown below.

    $ java KnightsTourSolver↵
    Enter board size to solve: 
    5
    Solution 1
    1     12    3     18    21    
    4     17    20    13    8    
    11    2     7     22    19    
    16    5     24    9     14    
    25    10    15    6     23    
    
    Solution 2
    1     14    3     8     21    
    4     9     20    13    18    
    15    2     17    22    7    
    10    5     24    19    12    
    25    16    11    6     23    
    
    ...
    
    Solution 304
    1     14    19    8     25    
    6     9     2     13    18    
    15    20    7     24    3    
    10    5     22    17    12    
    21    16    11    4     23