1.1.3 算法四_1.3节_背包，队列_练习题

1.3.4 Write a stack client Parentheses.java that reads in sequence of left and right parentheses, braces, and brackets from standard input and uses a stack to determine whether the sequence is properly balanced. For example, your program should print true for [()]{}{[()()] ()}and false for [(]).

思路：

准备一个栈，用来存储左括号, 从左到右读取括号，
while 还有下一个元素可以读取时，
读取元素
if 是左括号 then
入栈
if 是右括号 then
弹出栈元素，即弹出最后加入栈的左括号
if 弹出的左括号和读取到的右括号不配对 then
return false
return stack.isEmpty();

出错点：

1. 不是说在循环过程中没有返回false，就说明输入的字符串括号全是配对的，在循环结束后，return true;就可以了。
   应该是在循环结束后，判断栈里的元素是否全部弹出来。
   存在这样一种情况 {{{{[]}，如果return true; 那么会判断这个输入字符串是配对的。

优化：

1. 应该将’{’…定义为Parentheses为不可变的常量成员，经常重复的数据应该用变量存储起来。
2. String s = StdIn.readAll().trim();
   String s = StdIn.readAll();后面加上trim()去除收尾空格，减少判断的次数。
3. if (currentChar == RIGHT_PAREN) {
   if (parenthesesStack.isEmpty()) return false;
   if (parenthesesStack.pop() != LEFT_PAREN) return false;
   }
   还可以添加一个判断空 if (parenthesesStack.isEmpty()) return false;
4. 将parenthesesStack定义在方法里，节约内存
   Stack parenthesesStack = new Stack<>();
5. 可以将’{’…当做char类型
   String s = StdIn.readAll();
   for (int i = 0; i < s.length(); i++) {
   char currentChar = s.charAt(i);
   }
   1.3.5 输入一个整数，输出该整数的二进制
   思路：
   while(num ! = 0) then
   int result = num % 2 ；
   stack.push(result);
   num = num / 2;
   打印结果，就是依次弹出堆中存放的元素。

1.3.6 输入一个队列，输出该队列q的翻转队列q
思路：

栈和队列的进出顺序相反,用栈做中转站
Stack stack = new Stack();
while(!q.isEmpty()) { // 将队列中的元素全部转移到栈中
stack.push(q.dequeue());
}
while(!stack.isEmpty()) { // 再将栈中的元素转义到队列中
q.enqueue(stack.pop());
}

1.3.10 Write a filter Program InfixToPostfix.java that converts an arithmetic expression from infix to postfix.实现一个过滤器InfixToPostfix, 将算术表达式由中序表达式转为后序表达式。

1. 计算中序表示式：( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) )

从左到右，依次遍历字符串，如果碰到右括号 ‘)’ 就计算左边紧挨着他的两个数字，如2 , 3和一个操作符+，并将结果5替换掉( 2 + 3 ),依次这样操作。
(1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) )
(1 + ( 5 * ( 4 * 5 ) ) )
(1 + ( 5 * 20 ) )
(1 + 100 )
101
代码：准备一个专门存操作数的栈vals和一个专门存操作符的栈ops，从左到右依次遍历，
if s.equals("(")，then
do nothing
else if s.equal(操作符) then
ops.push(操作符)
else if s.equals(")") then
ops弹出一个操作符，vals弹出两个数字，计算，并将计算结果添加到vals中
else then
vals.push(Double.parseDouble(s));

2. 计算后序表达式：1 2 3 + 4 5 * * +

从左到右，依次遍历字符串，如果碰到操作符，就计算紧挨在操作符左边的两个数字，如+，2和3，计算2 + 3 = 5,并将计算结果5替换掉 2 3 + ，依次这样执行
1 2 3 + 4 5 * * +
1 5 4 5 * * +
1 5 20 * +
1 100 +
101

代码：准备一个vals用来存数字，从左到右依次遍历，
if s.equal("+") then
vals.push(vals.pop() + vals.pop());
else if s.equal("*") then
vals.push(vals.pop() + vals.pop());
else
vals.push(Double.parseDouble(s));
System.out.print(vals.pop());

思路：

计算中序表达式时，碰到数字和操作符分别存入数字栈vals和操作符栈ops，碰到右括号，从栈中取出两个数字和一个操作符，计算，并将结果存入数字栈vals。结果为栈中的唯一剩下的那一个元素

计算后序表达式时，碰到数字存入栈，碰到操作符，取出连个数字，并将计算结果存入栈。结果为栈中的唯一剩下那一个元素。

那么中序转后序肯定是以右括号为准，碰到数字直接打印出来，碰到操作符存入操作符栈ops,碰到右括号则弹出一个操作符，并打印。

代码：准备一个操作符栈ops,从左到右依次遍历
if s.equals("(") then
do nothing
if s.equals("+") then
ops.push("+")
else if s.equals("") then
ops.push("")
else if s.equals(")") then
System.out.print(ops.pop())
else if
System.out.print(s);

1.3.11 Write a program EvaluatePostfix.java that that takes a postfix expression from standard input, evaluates it, and prints the value. (Piping the output of your program from the previous exercise to this program gives equivalent behavior to Evaluate.java.)计算后序表达式的结果Eva

1.3.14 Develop a class ResizingArrayQueueOfStrings that implements the queue abstraction with a fixed-size array, and then extend your implementation to use array resizing to remove the size restriction.
Solution: ResizingArrayQueue.java

思路：

和之前ResizingArrayStack类似，定义一个变量n用来记录在队列中的元素数量，当队列中的元素数量=队列依赖的数组固有长度时，扩容两倍(新建一个数组，元素搬家)；当队列中的元素数量 < 1/4 * 队列依赖的数组固有长度时，s缩容1/2(新建一个数组，元素搬家)；

ResizingArrayStack和ResizingArrayQueue不同点：
ResizingArrayStack是先进先出，删除的是栈最上面的元素，添加是在最上面的元素添加，所以只需要定义一个int first索引（数组的索引是int值，链表的索引是Node，数据结构不同而不同）指向栈最上面的元素。
ResizingArrayQueue是后进先出，删除的是队列最前面的元素，添加是在队列最后一个元素添加，所以需要定义两个int first指向队列最前面的元素，int last指向队列最后面的元素。

注意点：

1. 为了避免对象游离，在取出first索引指向的item后，需要将这个first指向的这个空间赋值为null。接着first索引在往后移一位。

Item item = a[first];
a[first] = null;
first++;

2. 在扩容或缩容时，要注意first和n

1.3.42 Copy a stack. Create a new constructor for the linked-list implementation of Stack.java so that Stack t = new Stack(s) makes t reference a new and independent copy of the stack s.

Recursive solution: create a copy constructor for a linked list starting at a given Node and use this to create the new stack.

Node(Node x) {   
item = x.item;   
if (x.next != null) next = new Node(x.next);
}
public Stack(Stack<Item> s) { first = new Node(s.first); }

Nonrecursive solution: create a copy constructor for a single Node object.

Node(Node x) {
 this.item = x.item; 
 this.next = x.next; 
}
public Stack(Stack<Item> s) { 
  	if (s.first != null) {     
   		first = new Node(s.first);    
   		for (Node x = first; x.next != null; x = x.next)
   			 x.next = new Node(x.next);   
   		 }
   }
   	 

思路：

因为链表的节点之间是依靠上一个节点里存有下一个节点的地址值，这个地址值把上下节点串起来。给一个Node节点，通过next就可以顺藤摸瓜，一直向下，可以找到所有节点，x.next存储着x下一个节点的地址值。
所以先将stack的第一个节点first复制过来，再顺着这个first的next一直找下去，找到stack的所有。

public FIxLinkedStack(FIxLinkedStack stack) {
	this.first = new Node(stack.first);
	for(Node x = this.first.next; x.next != null; x = x.next) {
		x = new Node(x);
	}
}

链表练习

1.3.18 删除节点x后面的一个节点

x.next = x.next.next;

1.3.19 删除链表的尾结点，其中链表的首节点为first

思路：

要删除链表的尾结点，原本last指向链表的尾结点，现在要让last指向尾结点的前一个节点，但问题是现在没有办法知道尾结点的前一个节点的地址值，只有尾结点的后一个节点的地址值。
只能从first节点遍历所有节点，x = first.next.next…;当x的next指向last时，x就是last的前一个节点。

1.3.22 在节点x后面插入一个节点t

t.next = x.next;
x.next = t;

1.3.23 和上面的代码有什么不同

x.next = t;
t.next = x.next;

在更新t.next时，x.next已经不再指向x的后续节点，而是指向t本身。

1.3.37 Josephus problem. In the Josephus problem from antiquity, N people are in dire straits and agree to the following strategy to reduce the population. They arrange themselves in a circle (at positions numbered from 0 to N-1) and proceed around the circle, eliminating every Mth person until only one person is left. Legend has it that Josephus figured out where to sit to avoid being eliminated. Write a Queue client Josephus.javathat takes M and N from the command line and prints out the order in which people are eliminated (and thus would show Josephus where to sit in the circle).

% java Josephus 2 7
1 3 5 0 4 2 6

思路：

所有人构成一个队列，只要队列中还有人，就从队首开始从1~M开始报数。
报1~M-1的人依次站到队尾，这样，报M的人就排到了队首，dequeue(),打印并去除这个人。
打印顺序就是被杀掉人的顺序

 // initial 本来人是按顺序围成一个圈坐着，
        // 现在他们是按顺序排成一个队列站着
  Queue<Integer> queue = new Queue<>();
  for (int i = 0; i < n; i++) {
      queue.enqueue(i);
  }

  while (!queue.isEmpty()) {
       // 从队列的首部开始，报数，从1报到到m-1,
       for (int j = 0; j < m - 1; j++) {
           // 报数为1到m-1的人，全部站到队尾
           queue.enqueue(queue.dequeue());
       }
	   // 此时报数为m的人已经排在了队列的第一个，杀死
       StdOut.print(queue.dequeue() + " "); 
 }
   

最后

以上就是热心发卡为你收集整理的1.1.3 算法四_1.3节_背包，队列_练习题的全部内容，希望文章能够帮你解决1.1.3 算法四_1.3节_背包，队列_练习题所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。