1.3.3 # 解答 # 这个问题的通用解法见习题 1.3.46 的解答。 第 2、6、7 个不可能产生，可以画个栈模拟一下。 第 2 个 输出数 栈内数 4 0~3 6 0~3 + 5 8 0~3 + 5 + 7 7 0~3 + 5 5 0~3 3 0~2 2 0~1 9 0~1 0 Error 第 6 个 输出数 栈内数 0 null 4 1~3 6 1~3 + 5 5 1~3 3 1~2 8 1~2 + 7 1 Error 第 7 个 输出数 栈内数 1 0 4 0 + 2~3 7 0 + 2~3 + 5~6 9 0 + 2~3 + 5~6 + 8 8 0 + 2~3 + 5~6 6 0 + 2~3 + 5 5 0 + 2~3 3 0 + 2 0 Error
1.3.4 # 解答 # 官方 JAVA 版本参考：Parentheses.java。 遇到左括号就入栈，遇到右括号就检查是否和栈顶的左括号匹配，如果匹配则弹栈，否则返回 false。 结束时如果栈不为空则返回 false，否则返回 true。 代码 # var input = "[()]{}{[()()]()}"; Console.WriteLine(IsBalanced(input)); var input2 = "[(])"; Console.WriteLine(IsBalanced(input2)); static bool IsBalanced(string input) { var stack = new Stack<char>(); foreach (var i in input) { if (i == '(' || i == '[' || i == '{') stack.Push(i); else { if (stack.Peek() == '(' && i == ')') stack.Pop(); else if (stack.Peek() == '{' && i == '}') stack. ...
1.3.5 # 解答 # 实际上是用除二取余法求一个十进制数的二进制形式。 代码 # var n = 50; var stack = new Stack<int>(); while (n > 0) { stack.Push(n % 2); n = n / 2; } foreach (var d in stack) { Console.WriteLine(d); } Console.WriteLine(); 另请参阅 # Generics 库
1.3.6 # 解答 # 利用一个栈对队列元素进行反序操作。 先把队列中的元素全部入栈，再依次弹出并加入队列中。 代码 # var q = new Queue<string>(); q.Enqueue("first"); q.Enqueue("second"); q.Enqueue("third"); q.Enqueue("fourth"); var stack = new Stack<string>(); while (!q.IsEmpty()) stack.Push(q.Dequeue()); while (!stack.IsEmpty()) q.Enqueue(stack.Pop()); Console.WriteLine(q.ToString()); 另请参阅 # Generics 库
1.3.7 # 解答 # 链表实现的话就是返回第一个结点 first 的 item 字段。 数组实现的话就是返回 first 对应的数组元素。 这里给出链表实现，完整实现见习题 1.3.2 的代码。 代码 # /// <summary> /// 返回栈顶元素（但不弹出它）。 /// </summary> /// <returns></returns> public Item Peek() { if (IsEmpty()) throw new InvalidOperationException("Stack Underflow"); return this.first.item; }
1.3.8 # 解答 # 首先是 DoublingStackOfStrings 类，据我猜测应该是用数组实现的栈，扩容时长度增加一倍，缩短时长度减小一半。 官方 JAVA 代码参考：FixedCapacityStackOfString.java。 代码 # DoublingStackOfStrings 类 # /// <summary> /// 容量自动加倍的字符串栈。 /// </summary> internal class DoublingStackOfStrings : IEnumerable<string> { private string[] _items; private int _count; /// <summary> /// 新建一个字符串栈。 /// </summary> public DoublingStackOfStrings() { _items = new string[2]; _count = 0; } /// <summary> /// 检查栈是否为空。 /// </summary> /// <returns></returns> public bool IsEmpty() { return _count == 0; } /// <summary> /// 返回栈中字符串的数量。 /// </summary> /// <returns></returns> public int Size() { return _count; } /// <summary> /// 向栈中压入一个字符串。 /// </summary> /// <param name="s"></param> public void Push(string s) { if (_count == _items. ...
1.3.9 # 解答 # 在计算中序表达式算法的基础上做修改。 压入数字时将该数字所在的位置也一并压入。 弹出数字进行运算时在位置靠前的数字前加上左括号。 A + B ) * C + D ) ) 为例。 A 压入栈中并记录位置 。 ‘+’ 压入栈中。 B 压入栈中并记录位置。 ) 计算，在 A 之前加入左括号，结果 E 压入栈中，位置为 A 的位置。 ‘*’ 压入栈中。 C 压入栈中并记录位置。 ‘+’ 压入栈中。 D 压入栈中并记录位置。 ) 计算，在 C 之前加入左括号，结果 F 压入栈中，位置为 C 的位置。 ) 计算，在 E 之前加入左括号（也就是 A 之前），结果 G 压入栈中，位置为 E 的位置。 代码 # var input = "1 + 2 ) * 3 - 4 ) * 5 - 6 ) ) )"; var operators = new Stack<char>(); var numbers = new Stack<Number>(); var leftBrackets = new int[input. ...
1.3.10 # 解答 # 官方 JAVA 代码：InfixToPostfix.java。 其实就是把右括号换成相应运算符 对于 (A + B)，忽略左括号，数字直接输出，运算符入栈，遇到右括号时再弹出 结果 A B +，变成后序表达式 代码 # // 其实就是把右括号换成相应运算符 // 对于 (A + B)，忽略左括号，数字直接输出，运算符入栈，遇到右括号时再弹出 // 结果 A B +，变成后序表达式 var stack = new Stack<string>(); var input = "( 1 + ( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) ) )".Split(' '); foreach (var n in input) { if (n == " ") { continue; } if (n == "+" || n == "-" || n == "*" || n == "/") { stack. ...
1.3.11 # 解答 # 官方 JAVA 代码：EvaluatePostfix.java。 遇到数字就入栈，遇到运算符就弹出两个数字运算，再把结果入栈。 如果倒着读取的话也可以用递归做，当作前序表达式计算即可。 代码 # var stack = new Stack<int>(); var input = "7 16 * 5 + 16 * 3 + 16 * 1 +".Split(' '); foreach (var n in input) { if (n == " ") { continue; } if (n == "+") { stack.Push(stack.Pop() + stack.Pop()); } else if (n == "-") { var temp = stack.Pop(); stack.Push(stack.Pop() - temp); } else if (n == "*") { stack. ...
1.3.12 # 解答 # 先用 foreach 语句遍历一遍栈，把所有元素都压入一个临时栈中。 此时临时栈变成了源栈的一个倒序副本。 再将临时栈中的元素依次压入目标栈中，就得到了源栈的一个副本。 代码 # var src = new Stack<string>(); src.Push("first"); src.Push("second"); src.Push("third"); var des = CopyTo(src); while (!des.IsEmpty()) { Console.WriteLine(des.Pop()); } static Stack<string> CopyTo(Stack<string> src) { var des = new Stack<string>(); var temp = new Stack<string>(); foreach (var s in src) { temp.Push(s); } while (!temp.IsEmpty()) { des.Push(temp.Pop()); } return des; } 另请参阅 # Generics 库