本系列博客習(xí)題來自《算法(第四版)》，算是本人的讀書筆記，如果有人在讀這本書的，歡迎大家多多交流。為了方便討論，本人新建了一個(gè)微信群(算法交流)，想要加入的，請(qǐng)?zhí)砑游业奈⑿盘?hào)：zhujinhui207407 謝謝。另外，本人的個(gè)人博客 http://www.kyson.cn 也在不停的更新中，歡迎一起討論

算法(第4版)

知識(shí)點(diǎn)

• Java中Object類介紹
• Stack的運(yùn)用
• 解釋器、詞法分析

題目

1.3.3 假設(shè)某個(gè)用例程序會(huì)進(jìn)行一系列入棧和出棧操作。入棧操作會(huì)將整數(shù)0到9按順序壓入棧；出棧操作會(huì)打印返回值。下面哪種順序是不可能產(chǎn)生的？

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是不能產(chǎn)生的。

代碼索引

無代碼

題目

1.3.4 編寫一個(gè)Stack的用例Parentheses,從標(biāo)準(zhǔn)輸入中讀取一個(gè)文本流并使用棧判定其中的括號(hào)是否配對(duì)完整.例如[()]{}{[()]}為true,對(duì)于[(])程序則打印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 [(]).

分析

本人所有簡書的算法文章詳細(xì)分析已經(jīng)移入小專欄：算法四習(xí)題詳解，歡迎大家訂閱

答案

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

分析視頻

點(diǎn)此觀看分析視頻：頂級(jí)程序員教你學(xué)算法(27)-Stack運(yùn)用之解釋器(1.3.3-1.3.4)

廣告

我的首款個(gè)人開發(fā)的APP壁紙寶貝上線了，歡迎大家下載。