《算法》第四版答案（一）习题1.3及环境配置

在大二快过完两个月的时候我终于开始想刻苦学习了。。。（尴尬啊~）
所以希望在这剩下的两个月的时候能够刷完《算法》第四版，然后把题海刷完作为新年礼物送给自己。求围观，好让我坚持下去！！！哈哈哈~

这些答案有我自己写的，也有官网上的，也有参照网上别人的答案，所以
如果有错误或者是更好的解法或者是代码风格，欢迎指出，欢迎一起学习。

先贴出官网地址：http://algs4.cs.princeton.edu
（学习的时候多上官网多查官网文档是一个很好的习惯哦~
附：官网上也有习题答案）

在CSDN上发现一个良心博主，习题答案很不错，
贴出网址，欢迎大家去学习~
http://blog.csdn.net/furzoom/article/details/52692580

环境包下载

官网教程：http://algs4.cs.princeton.edu/windows/

由于《算法》中StdIn/StdOut 是作者自己写的库，Java中是没有这些库的，所以要运行书中的代码的话就要在网上下载这些库的实现。

实现方法：在官网下载algs4.jar和stdlib.jar两个包，将其导入eclipse中即可。下载地址如下：
http://algs4.cs.princeton.edu/code/algs4.jar
http://introcs.cs.princeton.edu/java/stdlib/stdlib.jar

导入步骤的图片如下：

image.png

第一章 1.3 背包，队列和栈

1.3.1
答案

  public boolean isFull()          
   {  return N == a.length;   }

整个程序


import java.util.Iterator;
import java.util.NoSuchElementException;

public class FixedCapacityStackOfStrings implements Iterable<String> {
    private String[] a;  // holds the items
    private int N;       // number of items in stack

    // create an empty stack with given capacity
    public FixedCapacityStackOfStrings(int capacity) {
        a = new String[capacity];
        N = 0;
    }

    public boolean isEmpty()            {  return N == 0;                    }
    public boolean isFull()             {  return N == a.length;             }
    public void push(String item)       {  a[N++] = item;                    }
    public String pop()                 {  return a[--N];                    }
    public String peek()                {  return a[N-1];                    }
    public Iterator<String> iterator()  { return new ReverseArrayIterator(); }


    public class ReverseArrayIterator implements Iterator<String> {
        private int i = N-1;

        public boolean hasNext() {
            return i >= 0;
        }

        public String next() { 
            if (!hasNext()) throw new NoSuchElementException();
            return a[i--];
        }

        public void remove() {
            throw new UnsupportedOperationException();
        }
    }


    public static void main(String[] args) {
        int max = Integer.parseInt(args[0]);
        FixedCapacityStackOfStrings stack = new FixedCapacityStackOfStrings(max);
        while (!StdIn.isEmpty()) {
            String item = StdIn.readString();
            if (!item.equals("-")) stack.push(item); 
            else if (stack.isEmpty())  StdOut.println("BAD INPUT"); 
            else                       StdOut.print(stack.pop() + " ");
        }
        StdOut.println();

        // print what's left on the stack
        StdOut.print("Left on stack: ");
        for (String s : stack) {
            StdOut.print(s + " ");
        }
        StdOut.println();
    } 
}

1.3.2
答案

was best times of the was the it (1 left on stack)

1.3.3
答案

b f g

1.3.4
官网答案

/******************************************************************************
 *  Compilation:  javac Parentheses.java
 *  Execution:    java Parentheses
 *  Dependencies: In.java Stack.java
 *
 *  Reads in a text file and checks to see if the parentheses are balanced.
 *
 *  %  java Parentheses
 *  [()]{}{[()()]()}
 *  true
 *
 *  % java Parentheses
 *  [(]) 
 *  false
 *
 ******************************************************************************/

public class Parentheses {
    private static final char LEFT_PAREN     = '(';
    private static final char RIGHT_PAREN    = ')';
    private static final char LEFT_BRACE     = '{';
    private static final char RIGHT_BRACE    = '}';
    private static final char LEFT_BRACKET   = '[';
    private static final char RIGHT_BRACKET  = ']';

    public static boolean isBalanced(String s) {
        Stack<Character> stack = new Stack<Character>();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == LEFT_PAREN)   stack.push(LEFT_PAREN);
            if (s.charAt(i) == LEFT_BRACE)   stack.push(LEFT_BRACE);
            if (s.charAt(i) == LEFT_BRACKET) stack.push(LEFT_BRACKET);

            if (s.charAt(i) == RIGHT_PAREN) {
                if (stack.isEmpty())           return false;
                if (stack.pop() != LEFT_PAREN) return false;
            }

            else if (s.charAt(i) == RIGHT_BRACE) {
                if (stack.isEmpty())           return false;
                if (stack.pop() != LEFT_BRACE) return false;
            }

            else if (s.charAt(i) == RIGHT_BRACKET) {
                if (stack.isEmpty())             return false;
                if (stack.pop() != LEFT_BRACKET) return false;
            }
        }
        return stack.isEmpty();
    }


    public static void main(String[] args) {
        In in = new In();
        String s = in.readAll().trim();
        StdOut.println(isBalanced(s));
    }
}

1.3.5
答案

打印 N 的二进制表示 （当n为50时为110010）。

1.3.6
答案

反转队列上的项目

1.3.7
官网答案

/******************************************************************************
 *  Compilation:  javac Stack.java
 *  Execution:    java Stack < input.txt
 *  Dependencies: StdIn.java StdOut.java
 *  Data files:   http://algs4.cs.princeton.edu/13stacks/tobe.txt
 *
 *  A generic stack, implemented using a singly linked list.
 *  Each stack element is of type Item.
 *
 *  This version uses a static nested class Node (to save 8 bytes per
 *  Node), whereas the version in the textbook uses a non-static nested
 *  class (for simplicity).
 *  
 *  % more tobe.txt 
 *  to be or not to - be - - that - - - is
 *
 *  % java Stack < tobe.txt
 *  to be not that or be (2 left on stack)
 *
 ******************************************************************************/

import java.util.Iterator;
import java.util.NoSuchElementException;

public class Stack<Item> implements Iterable<Item> {
    private Node<Item> first;     // top of stack
    private int n;                // size of the stack

    // helper linked list class
    private static class Node<Item> {
        private Item item;
        private Node<Item> next;
    }

    /**
     * Initializes an empty stack.
     */
    public Stack() {
        first = null;
        n = 0;
    }

    /**
     * Returns true if this stack is empty.
     *
     * @return true if this stack is empty; false otherwise
     */
    public boolean isEmpty() {
        return first == null;
    }

    /**
     * Returns the number of items in this stack.
     *
     * @return the number of items in this stack
     */
    public int size() {
        return n;
    }

    /**
     * Adds the item to this stack.
     *
     * @param  item the item to add
     */
    public void push(Item item) {
        Node<Item> oldfirst = first;
        first = new Node<Item>();
        first.item = item;
        first.next = oldfirst;
        n++;
    }

    /**
     * Removes and returns the item most recently added to this stack.
     *
     * @return the item most recently added
     * @throws NoSuchElementException if this stack is empty
     */
    public Item pop() {
        if (isEmpty()) throw new NoSuchElementException("Stack underflow");
        Item item = first.item;        // save item to return
        first = first.next;            // delete first node
        n--;
        return item;                   // return the saved item
    }


    /**
     * Returns (but does not remove) the item most recently added to this stack.
     *
     * @return the item most recently added to this stack
     * @throws NoSuchElementException if this stack is empty
     */
    public Item peek() {
        if (isEmpty()) throw new NoSuchElementException("Stack underflow");
        return first.item;
    }

    /**
     * Returns a string representation of this stack.
     *
     * @return the sequence of items in this stack in LIFO order, separated by spaces
     */
    public String toString() {
        StringBuilder s = new StringBuilder();
        for (Item item : this) {
            s.append(item);
            s.append(' ');
        }
        return s.toString();
    }
       

    /**
     * Returns an iterator to this stack that iterates through the items in LIFO order.
     *
     * @return an iterator to this stack that iterates through the items in LIFO order
     */
    public Iterator<Item> iterator() {
        return new ListIterator<Item>(first);
    }

    // an iterator, doesn't implement remove() since it's optional
    private class ListIterator<Item> implements Iterator<Item> {
        private Node<Item> current;

        public ListIterator(Node<Item> first) {
            current = first;
        }

        public boolean hasNext() {
            return current != null;
        }

        public void remove() {
            throw new UnsupportedOperationException();
        }

        public Item next() {
            if (!hasNext()) throw new NoSuchElementException();
            Item item = current.item;
            current = current.next; 
            return item;
        }
    }


    /**
     * Unit tests the {@code Stack} data type.
     *
     * @param args the command-line arguments
     */
    public static void main(String[] args) {
        Stack<String> stack = new Stack<String>();
        while (!StdIn.isEmpty()) {
            String item = StdIn.readString();
            if (!item.equals("-"))
                stack.push(item);
            else if (!stack.isEmpty())
                StdOut.print(stack.pop() + " ");
        }
        StdOut.println("(" + stack.size() + " left on stack)");
    }
}

1.3.8

没有在书中找到DoublingStackOfStrings的代码
欢迎大家指出

1.3.9
答案

 public static String getCompleteExpression(String exp)  
    {  
        String[] params = exp.split(" ");  
        Stack<String> oprStack = new Stack<String>();  
        Stack<String> dataStack = new Stack<String>();  
        for (int i = 0; i < params.length; i++) {  
            if (isOperator(params[i])) {  
                oprStack.push(params[i]);  
            } else if (params[i].equals(")")) {  
                String d1 = dataStack.pop();  
                String d2 = dataStack.pop();  
                String op = oprStack.pop();  
                dataStack.push("( " + d2 + " " + op + " "+ d1 + " )");  
            } else {  
                dataStack.push(params[i]);  
            }  
        }  
        return dataStack.pop();  
    }  
     
    public static void main(String[] args)  
    {  
        String expression = "1 + 2 ) * 3 - 4 ) * 5 - 6 ) ) )";  
        String result = getCompleteExpression(expression);  
        System.out.println(result);  
    }  
      
    private static boolean isOperator(String s)  
    {  
        return (s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/"));  
    }

1.3.10
答案

/******************************************************************************
 *  Compilation:  javac InfixToPostfix.java
 *  Execution:    java InfixToPostFix
 *  Dependencies: Stack.java StdIn.java StdOut.java
 *
 *  Reads in an infix expression and outputs an equivalent postfix
 *  expression.
 *
 *  Windows users: replace [Ctrl-d] with [Ctrl-z] to signify end of file.
 * 
 *  % java InfixToPostfix
 *  ( 2 + ( ( 3 + 4 ) * ( 5 * 6 ) ) )
 *  [Ctrl-d]
 *  2 3 4 + 5 6 * * + 
 *
 *  % java InfixToPostfix | java EvaluatePostfix
 *  ( 2 + ( ( 3 + 4 ) * ( 5 * 6 ) ) )
 *  [Ctrl-d]
 *  212
 *
 ******************************************************************************/

public class InfixToPostfix {
    public static void main(String[] args) {
        Stack<String> stack = new Stack<String>();
        while (!StdIn.isEmpty()) {
            String s = StdIn.readString();
            if      (s.equals("+")) stack.push(s);
            else if (s.equals("*")) stack.push(s);
            else if (s.equals(")")) StdOut.print(stack.pop() + " ");
            else if (s.equals("(")) StdOut.print("");
            else                    StdOut.print(s + " ");
        }
        StdOut.println();
    }
}

今天时间比较仓促，先pull下来，等明天的时候先扩充答案然后继续发（搬运）下面题的答案。

《算法》第四版 答案（一）习题1.3及环境配置

环境包下载

第一章 1.3 背包，队列和栈

推荐阅读更多精彩内容

《算法》第四版答案（一）习题1.3及环境配置