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

算法(第4版)

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

• Java中Object類(lèi)介紹
• 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)生的森渐。

代碼索引

無(wú)代碼

題目

1.3.4 編寫(xiě)一個(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 [(]).

分析

本人所有簡(jiǎn)書(shū)的算法文章詳細(xì)分析已經(jīng)移入小專(zhuān)欄：算法四習(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è)人開(kāi)發(fā)的APP壁紙寶貝上線了，歡迎大家下載壶运。