算法练习(27):Stack运用之解释器(1.3.3-1.3.4

本系列博客习题来自《算法(第四版)》，算是本人的读书笔记，如果有人在读这本书的，欢迎大家多多交流。为了方便讨论，本人新建了一个微信群(算法交流)，想要加入的，请添加我的微信号：zhujinhui207407 谢谢。另外，本人的个人博客 http://www.kyson.cn 也在不停的更新中，欢迎一起讨论

知识点

• Java中Object类介绍
• Stack的运用
• 解释器、词法分析

题目

1.3.3 假设某个用例程序会进行一系列入栈和出栈操作。入栈操作会将整数0到9按顺序压入栈；出栈操作会打印返回值。下面哪种顺序是不可能产生的？

1.3.3 Suppose that a client performs an intermixed sequence of (stack) push and pop operations. The push operations put the integers 0 through 9 in order onto the stack; the pop operations print out the return values. Which of the following sequence(s) could not occur?

(a) 4 3 2 1 0 9 8 7 6 5
(b) 4 6 8 7 5 3 2 9 0 1
(c) 2 5 6 7 4 8 9 3 1 0
(d) 4 3 2 1 0 5 6 7 8 9
(e) 1 2 3 4 5 6 9 8 7 0
(f) 0 4 6 5 3 8 1 7 2 9
(g) 1 4 7 9 8 6 5 3 0 2
(h) 2 1 4 3 6 5 8 7 9 0

答案

b, f, g是不能产生的。

代码索引

无代码

题目

1.3.4 编写一个Stack的用例Parentheses,从标准输入中读取一个文本流并使用栈判定其中的括号是否配对完整.例如[()]{}{[()]}为true,对于[(])程序则打印false。

1.3.4 Write a stack client Parentheses that reads in a text stream from standard input and uses a stack to determine whether its parentheses are properly balanced. For example, your program should print true for [()]{}{()()} and false for [(]).

分析

本人所有简书的算法文章详细分析已经移入小专栏：算法四习题详解，欢迎大家订阅

答案

public class Parentheses {

    public static void main(String[] args) {

//      String stream = "[()]{}{[()()]()}";
        String stream = "[(])";     
        boolean isPaired = true;
        
        Stack<String> ops = new Stack<String>();
        for (int i = 0; i < stream.length(); i++) 
        {
            char item = stream.charAt(i);
            String s = String.valueOf(item);
            
            if (s.equals("[")) {
                ops.push(s);
            }else if (s.equals("(")) {
                ops.push(s);
            }else if (s.equals("{")) {
                ops.push(s);
            }else if(s.equals("]"))
            {
                String popedString = ops.pop();
                if (!popedString.equals("[")) 
                {
                    isPaired = false;
                    break;
                }
            }else if(s.equals("}"))
            {
                String popedString = ops.pop();
                if (!popedString.equals("{")) 
                {
                    isPaired = false;
                    break;
                }
            }else if (s.equals(")")) 
            {
                String popedString = ops.pop();
                if (!popedString.equals("(")) 
                {
                    isPaired = false;
                    break;
                }
            }
        }
//最后加上这一句话，确保站为空
                if (!ops.isEmpty()) {
            isPaired = false;
        }
        System.out.println(isPaired);       
    }
}

代码索引

Parentheses.java

分析视频

点此观看分析视频：顶级程序员教你学算法(27)-Stack运用之解释器(1.3.3-1.3.4)

广告

我的首款个人开发的APP壁纸宝贝上线了，欢迎大家下载。