計算機中的內(nèi)存尋址是什么？如何實現(xiàn)？

內(nèi)存按字節(jié)編址,地址區(qū)間為[90000H,CFFFFH],若用32K*8bit的存儲器芯片構(gòu)成該內(nèi)存,需要__塊???

（1）首先根據(jù)地址區(qū)間[90000H,CFFFFH]，可以計算地址空間為：CFFFFH - 90000H + 1 = 40000H?
因為10000H = 2^16B 那么 40000H = 4 * (2^16)B?
(2)32K = 32*(2^10)B?
那么內(nèi)存所需芯片數(shù)為： （ 4 * (2^16) ）/ 32*(2^10 ) = 8;

上面這題是一樣的，現(xiàn)在看第二題。每個存儲單元可以存儲16位二進制數(shù)，所以排除了B和D。

400H = 4*2^16; x = 4*2^16 / 16*4 ===> x = 256 , 所以這個芯片的容量是256層樓，每一樓的寬度為16bit.

棧

波蘭式、逆波蘭式是《數(shù)據(jù)結(jié)構(gòu)》課程中講解關(guān)于棧的時候提到的，棧是很簡單的一種數(shù)據(jù)結(jié)構(gòu)。但是這些理論的提出卻是計算機早期發(fā)展領(lǐng)域的重大突破，值得仔細(xì)回味。

中綴表達(dá)式? 我們在數(shù)學(xué)中學(xué)到的表達(dá)式被稱為中綴表達(dá)式，操作符號在操作數(shù)中間，比如 2 + 3 * (5 - 1)。對人類而言，這種表達(dá)方式顯而易見，求值也很直接，先算乘除再算加減，先算括號內(nèi)再算括號外。

然而，這個表達(dá)式對于計算機而言卻很費解。你可能會有疑問：這有什么難理解的嘛，在JavaScript、Python或者Ruby，甚至是Java里面都可以通過eval(“2 + 3 * (5 - 1)”)來計算這個表達(dá)式。當(dāng)然，這里的計算機并不是指現(xiàn)而今強大的計算機和高級編程語言，而是指上個世紀(jì)中頁還處于發(fā)展初期的計算機。

前綴表達(dá)式? 早在1920年，波蘭科學(xué)家揚·武卡謝維奇就發(fā)明了一種不需要括號的表示法，可以用來表示一個計算表達(dá)式。即將操作符號寫在操作數(shù)之前，也就是前綴表達(dá)式，即波蘭式（Polish Notation, PN）。這種表達(dá)式直到1960年計算機出現(xiàn)后才發(fā)揮出其威力。

比如2 + 3 * (5 - 1)這個表達(dá)式的前綴表達(dá)式為+ 2 * 3 - 5 1來表示。

閱讀這個表達(dá)式需要從左至右讀入表達(dá)式，如果一個操作符后面跟著兩個操作數(shù)時，則計算，然后將結(jié)果作為操作數(shù)替換這個操作符和兩個操作數(shù)，重復(fù)此步驟，直至所有操作符處理完畢。從左往右依次讀取，直到遇到- 5 1，做計算后，將表達(dá)式替換為+ 2 * 3 4，然后從左往右再次讀取，直到遇到* 3 4，做計算后將表達(dá)式替換為+ 2 12，然后從左往右依次讀取，讀到+ 2 12，計算得到14，到此結(jié)束。

可以看到，這種計算過程也相當(dāng)復(fù)雜，需要多次遍歷表達(dá)式，而且需要識別一個操作符后面跟著兩個操作數(shù)這種模式，相比而言，下文中的逆波蘭式要更為直接和簡單。

如果你熟悉各種編程語言的話，這很像Lisp語言中的表達(dá)式（如下代碼）。需要注意的是，Lisp語言中的括號并不是數(shù)學(xué)意義上的的括號，Lisp中的函數(shù)是可以攜帶多個參數(shù)的，比如(+ 1 2 3)，因此需要使用括號來標(biāo)明函數(shù)參數(shù)。

Clojure1.5.1? user=>(+2(*3(-51)))14? 3. 后綴表達(dá)式? 后綴表達(dá)式也稱為逆波蘭式（Reverse Polish Notation, RPN），更加廣為人知一些，和前綴表達(dá)式剛好相反，是將操作符號放置于操作數(shù)之后，比如2 + 3 * (5 - 1)用逆波蘭式來表示則是：2 3 5 1 - * +。

逆波蘭式的計算也是從左往右依次讀取，當(dāng)讀到操作符時，將之前的兩個操作數(shù)做計算，然后替換這兩個操作數(shù)和操作符，接著讀取，重復(fù)此步驟。對于這個表達(dá)式，讀到5 1 -，得到4，然后讀取乘號，取出前面的3和上一步的計算結(jié)果4，并計算，到12，接著讀取加號+，計算2 12 +得到14，計算結(jié)束。

上面這個步驟可以很容易的用棧來實現(xiàn)：

從左往右依次讀取表達(dá)式，如果是數(shù)字則將該數(shù)字壓棧，如果是符號，則將之前的兩個數(shù)字出棧，做計算后，將計算結(jié)果壓棧，直到表達(dá)式讀取結(jié)束。棧中剩下的一個數(shù)就是計算結(jié)果。

逆波蘭式看起來像波蘭式反過來，比如5 + 1的波蘭式是+ 5 1，逆波蘭式為5 1 +或者1 5 +。也很明顯，逆波蘭式并不是簡單的將波蘭式反過來，因為，減法和除法中減數(shù)和被減數(shù)、除數(shù)與被除數(shù)是不能交換的，即- 10 5和- 5 10就完全不一樣。

中綴表達(dá)式到后綴表達(dá)式的轉(zhuǎn)換? 因為通過后綴表達(dá)式來進行計算只需要一個棧即可，從硬件和軟件上實現(xiàn)都是極為便利的，因此逆波蘭式在計算機領(lǐng)域的應(yīng)用更加廣泛，因此將中綴表達(dá)式轉(zhuǎn)換為逆波蘭式非常重要。

依然僅僅使用棧就可以將中綴表達(dá)式轉(zhuǎn)換成逆波蘭式，轉(zhuǎn)換過程如下：

從左往右遍歷中綴表達(dá)式中的每個數(shù)字和符號，弱是數(shù)字就輸出，成為逆波蘭式的一部分； 如果是右括號，或者是其他符號并且比當(dāng)前棧頂符號的優(yōu)先級低，則棧頂元素依次出棧并輸出； 然后將當(dāng)前符號進棧，重復(fù)以上操作直到結(jié)束。

還是以2 + 3 * (5 - 1)為例：

首先讀入數(shù)字2，直接將其輸出，輸出為2，棧為空? 接著讀入加號+，由于棧為空，因此將其進棧，輸出為2，棧為+? 接著讀入數(shù)字3，直接將其輸出，輸出為2 3，棧為+? 接著讀入乘號，比棧頂元素優(yōu)先級高，進棧，輸出為2 3，棧為+? 讀入左括號(，直接進棧，輸出2 3，棧為+ * (? 讀入數(shù)字5，直接將其輸出，輸出為2 3 5，棧為+ * (? 讀入減號-，棧頂元素為左括號，進棧，輸出為2 3 5，棧為+ * ( -? 讀入數(shù)字1，直接將其輸出，輸出為2 3 5 1，棧為+ * ( -? 讀入右括號，依次輸出棧頂元素，直到左括號，括號不輸出，輸出2 3 5 1 -，棧為+ *? 已經(jīng)無元素可讀，依次輸出棧頂元素，直到棧為空，輸出2 3 5 1 - * +，棧為空? 這樣可以僅僅使用棧，首先將中綴表達(dá)式轉(zhuǎn)換為逆波蘭式，然后用本文第3節(jié)中的方法對后綴表達(dá)式進行求值，整個過程使用棧來完成即可。

表達(dá)式樹與逆波蘭式? 還可以通過另外一種方法來將一個表達(dá)式轉(zhuǎn)換成波蘭式和逆波蘭式，這種方法依賴與樹，首先需要根據(jù)表達(dá)式構(gòu)建成樹，仍然以2 + 3 * (5 - 1)為例，下圖是其表達(dá)式樹。

我們發(fā)現(xiàn)這個樹的后序遍歷結(jié)果為2 3 5 1 - * +，剛好是其逆波蘭式；而其先序遍歷結(jié)果為+ 2 * 3 - 5 1剛好為其波蘭式；中序遍歷就不用說了，就是我們常見的中綴表達(dá)式。我們也可以通過這種特性來實現(xiàn)表達(dá)式的各種表示方法的轉(zhuǎn)換。