附錄二 堆疊的應用--數學運算式

這一篇文章,將介紹如何用組合語言實作一個計算機程式,CALC.EXE,它可以讓使用者輸入數字 ( 稱為運算元,operand ) 以及「+」、「-」、「×」、「 / 」、「 x^y 」(指數)、「 ( 」、「 ) 」、「log」等運算子 ( operator ),程式會依照先乘除、後加減的次序做運算,再把答案印在螢幕上。畫面如下圖,左邊的圖是輸入運算式,右邊的圖是按下「EXE」按鈕後的結果:


中序運算式 ( infix notation ) 與後序運算式 ( postfix notation )

簡介

一般在小學時,我們所學的運算式都是「中序運算式」,什麼是中序運算式呢?就是運算子在運算元中間的數學運算式,例如:

5*4
33+66
(22+5)*4

都稱為中序運算式。在中序運算式堛犒B算子有優先次序,並不是先遇到的運算子先行運算,大家都知道必須依照先乘除、後加減的規則做運算,假如有括號的話,括號的優先序還比乘除法來得大,應先運算,例如:

(22+5)*4

就得先算 22+5,不可先算乘法。假如運算式中包含了函數 ( 包含指數、對數、三角函數等等 ),例如

3+10*log 2=3+10*0.301

那麼這些函數的優先次序又大於乘除。換句話說,我們可以整理得到對於中序運算式的優先次序是

括號>函數>乘除>加減

後序運算式

後序運算式是波蘭數學家魯卡謝維奇 ( Jan Łukasiewicz ) 所發明的,這種運算式是把運算元寫在前面,而運算子寫在後面,例如 2+5 寫成 2 5 +。後序運算式沒有「(」、「)」,對於在電腦上做四則運算,很有幫助。我們已經很習慣中序表示法,寫成後序表示法很不容易理解,底下是把中序運算式改成後序運算式的步驟:

  1. 先把運算子與其兩旁的運算元以一對小括號括起來,即使是乘號與除號也一樣。
  2. 反覆檢查每個運算子都必須加上括號,因此可能會有好幾層括號。
  3. 由最內層開始,把每個運算元之間的運算子移到每一對括號的右括號上,再把括號除去。

例如要把 2+5*6-4*8 變成後序式,依據上面的原則,而有底下步驟:

  1. 先把每個運算子與兩邊的運算元加上括號,於是變成 2+(5*6)-(4*8)。
  2. 但是僅這樣是不夠的,因為加與減尚未加括號,所以原式再度變成{ [ 2 + ( 5*6 ) ] - ( 4*8 ) },為了表示 2 加 (5*6) 之結果,所以加上一對中括號,[ ];又為了相減,再加上一對大括號,{}。
  3. 然後由內而外,用括號堛犒B算子取代「 ) 」,再消去「 ( 」,所以變成{[ 2 + 5 6 * ] - 4 8 *}。
  4. 接著再移中括號堛犒B算子到「 ] 」位置,去掉「 [ 」,於是變成{2 5 6 * + - 4 8 *}。要注意的是白色與紅色的兩部份都已處理過了,只剩下減號未處理。
  5. 用減號取代「}」位置,再消去「{」,所以最後結果變成 2 5 6 * + 4 8 * -,這個就是 2+5*6-4*8 的後序式。

雖然常用的運算子,如:加、減、乘、除需要有兩個運算元才可運算;但是也有一些運算子只需一個運算元就可運算了,例如負號、對數 ( log )、三角函數等。如果運算式中有這些運算子,想要把它變成後序運算式,方法也像上面相似,只不過直接把用運算子取代「 ) 」,也可說是直接把運算子調到運算元之後。例如把 2+5*LOG 3 改成後序運算式,步驟如下:

  1. 先加上括號,變成{2 + [ 5 * ( LOG 3 ) ]}。
  2. 去掉最內層小括號,同時用 LOG 取代「 ) 」,變成 {2 + [ 5 * 3 LOG ]}。
  3. 用乘號取代「 ] 」,並消去「 [ 」,於是變成 { 2 + 5 3 LOG * }。
  4. 最後變成 2 5 3 LOG * +,就是後序運算式。

上面是人類以大腦把中序式改成後序式的過程,在組合語言運算中,要把中序式改成後序式,須準備一個堆疊,這個堆疊並不是前面所提到的用 PUSH、POP 保存數值或呼叫副程式時所用的,以 ESP 為指標的一塊記憶體。這堜畛羲滌幭|,其實是一個由許多成員所組成的陣列,並且用一個變數指向這個陣列位址,每當有資料要存入此陣列時,只能存在這個變數所指位址,存完之後,變數會指向下一個陣列的位址。當要從陣列取出資料時,也必須由這個變數所指的位址取出來,不能經由其他方式取出,資料取出後,變數則會指向堆疊的前一位址。至於把資料推入這個堆疊後,變數指向較高位址還是指向較低位址,則是無所謂,這一點和 PUSH、POP 存取的堆疊也不同。但是因為這種陣列具有「先進後出」的特性,所以才稱此陣列為堆疊。

在程式中把中序運算式轉換成後序運算式

在實作上,要把中序運算式轉換成後序運算式,可以利用堆疊。在這一章例子堙A小木偶準備了一個字串,做為儲存後序運算式,也準備了一個堆疊做為在轉換過程中儲存運算子之用,或許可以稱此堆疊為運算子堆疊。整個轉換成後序運算式的過程如下:

  1. 每次取出一個運算元或運算子。
  2. 若為運算元,則直接把這運算元輸出到儲存後序運算式的字串中。
  3. 若為運算子,可以分為下面幾種情形:
    1. 若為「(」,則直接推入運算子堆疊中。
    2. 若為「)」,則把堆疊運算子中的運算子依序取出,並輸出到後序式字串堙A直到相對應的「(」為止。而當前的運算子,「)」,則消失不推入運算子堆疊。
    3. 若為其他運算元,則比較運算子之優先次序。如果當前運算子之優先次序 ( ICP,in-coming priority ) 大於堆疊頂運算子之優先次序 ( ISP,in-stack priority ),則把當前運算子推入運算子堆疊;否則自運算子堆疊頂端取出運算元輸出至後序式字串,直到當前運算子之 ICP 小於運算子堆疊頂之運算子的 ISP 為止,再把當前運算子推入堆疊。
  4. 重複步驟 1∼3,直到所有的運算元或運算子都已經處理完畢時,依次把運算子堆疊中的運算子取出,推入後序式字串堙C

後序式運算式計算結果

雖然後序運算式不易理解,但是它有兩個好處。一是沒有括號,二是符合計算機運作方式。這兩句話的意思是使用後序運算式時,不需要考慮運算子的優先序。假如我們已經依照上述方法把中序運算式轉換成後序運算式以後,要計算結果,就很簡單了。這時只需要準備一個堆疊,這個堆疊用來存放運算元,稱為運算元堆疊。計算時,把後序運算式假想成一個字串,由此字串的左邊向右開始計算,每次取出一個運算元或運算子,當遇到運算元時,直接把運算元推入運算元堆疊;當遇到運算子時,則視此運算子需要幾個運算元,自運算元堆疊取出符合該運算元所需運算元的個數,再與運算子計算,然後再把結果推入運算元堆疊。如此一直重複這個步驟,直到後序式字串已經空了,這時在運算元堆疊的數值就是最後的結果。


CALC 原始碼

底下是組合語言原始碼,CALC.ASM:

;具有先乘除後加減的計算機程式
        page    ,132
        .386
        .model  flat,stdcall
        option  casemap:none

DlgProc proto   :DWORD,:DWORD,:DWORD,:DWORD

include         windows.inc
include         user32.inc
include         kernel32.inc
include         masm32.inc
includelib      user32.lib
includelib      kernel32.lib
includelib      masm32.lib

IDE_EXPRESSION  equ     1000
IDB_CLEAR       equ     1001
IDB_EXECUTE     equ     1002

IDM_EXIT        equ     3000
IDM_CLEAR       equ     3001
IDM_PI          equ     3002
IDM_EULER       equ     3003

CD_LEN          equ     100     ;最多輸入100個內碼
;*********************************************************************
                .const
dwTen           WORD    10
DlgName         BYTE    'CalcDlg',0
CalcIcon        BYTE    'CalcIco',0

;parse table (x,y)=(現在的,前一個的)
;                                       10  L
;                                       冪倒O 指
;                       N + - * / ( ) - 方數G 數=
;                       0 1 2 3 4 5 6 7 8 9 A B C
parse_table     BYTE    0,1,1,1,1,0,1,0,1,1,0,1,1  ;0 N
                BYTE    1,0,0,0,0,1,0,1,1,0,1,0,0  ;1 +
                BYTE    1,0,0,0,0,1,0,1,1,0,1,0,0  ;2 -
                BYTE    1,0,0,0,0,1,0,1,1,0,1,0,0  ;3 *
                BYTE    1,0,0,0,0,1,0,1,1,0,1,0,0  ;4 /
                BYTE    1,0,0,0,0,1,0,1,1,0,1,0,0  ;5 (
                BYTE    0,1,1,1,1,0,0,0,0,1,0,1,1  ;6 )
                BYTE    1,1,1,1,1,1,0,2,1,0,1,0,0  ;7 -(負號)
                BYTE    1,0,0,0,0,1,0,1,0,0,1,0,0  ;8 10冪方
                BYTE    0,1,1,1,1,0,1,0,0,1,0,0,1  ;9 x^(-1)倒數(R)
                BYTE    1,0,0,0,0,1,0,1,1,0,1,0,0  ;A LOG
                BYTE    1,0,0,0,0,1,0,1,1,0,1,0,0  ;B x^y指數
                BYTE    1,0,0,0,0,1,0,1,1,0,1,0,1  ;C =

;顯示於IDE_EXPRESSION編輯框內的函數文字
stReciprocal    BYTE    6,'^(-1) ' ;倒數,^(-1) 會顯示於編輯框內。6表示共有6個字元
stLOG           BYTE    3,'LOG'    ;對數,LOG會顯示於編輯框內。3表示共有3個字元
stExponent      BYTE    3,'x^y'

                       ;N + - * / ( ) - E R L ^ =
icp             BYTE    0,2,2,3,3,5,4,5,5,5,5,5,0  ;運算式優先序
isp             BYTE    0,2,2,3,3,1,4,4,4,4,4,4,0  ;堆疊優先序

display_table   BYTE    '+','-','*','/','(',')','-','E'

action          DWORD   number,plus,minus,multiple,divide,0,0,negative
                DWORD   exp10,reciprocal,log,exponent,answer

szErrorMsg0     BYTE    'Syntax Error',0
szErrorMsg1     BYTE    'Invalid Number',0

szPi            BYTE    '3.14159265358979324',0 ;圓周率
szEuler         BYTE    '2.71828182845904524',0 ;尤拉數
;*********************************************************************
                .data
hInstance       HINSTANCE       ?
CommandLine     LPSTR           ?
hwndEdit        HWND            ?

;szExpression存放使用者輸入的字串,此字串由處理按鈕而得,例如使用者依次按下
;按鈕7、按鈕+、按鈕LOG、按鈕2、按鈕0、按鈕EXE,則szExpression會變成 37 2B 4C 4F 47 32 30
;亦即7+LOG20。而stCodeBuffer則是存放各按鈕之內碼,以上例則變成 07 11 1A 02 00
szExpression    BYTE            CD_LEN*2 dup (0)        ;運算式的ASCII碼存放處
stCodeBuffer    BYTE            CD_LEN dup (0ffh)       ;運算式內碼存放處

;ptExpression、ptCodeBuffer則是szExpression、stCodeBuffer之指標,因為按鈕的字串
;不一定等長,例如倒數有6個字「^(-1) 」,對數有3個字「LOG」
ptExpression    LPSTR           ?
ptCodeBuffer    LPSTR           ?

previous_code   BYTE    ?       ;前一個內碼
current_code    BYTE    ?       ;當前內碼

lpPostfix       LPSTR   ?       ;後序運算式字串的指標
lpOpStack       LPSTR   ?       ;運算子堆疊指標
lpNumTemp       LPSTR   ?
lpNumStack      LPSTR   ?       ;運算元堆疊指標

stPostfix       BYTE    CD_LEN dup (0)  ;後序式字串
aryOpStack      BYTE    CD_LEN dup (0)  ;運算子堆疊
aryNumStack     TBYTE   CD_LEN/2 dup (0);運算元堆疊
aryNumTemp      TBYTE   CD_LEN/2 dup (0);暫時存放運算原處

dwNum           WORD    ?

szAnswer        BYTE    20 dup (0)

;若按下「EXE」按鈕後,尚未按下其他按鈕前,bIfExecute為1
bIfExecute      BYTE    0
;*********************************************************************
                .code
;---------------------------------------------------------------------
;初始化szExpression、stCodeBuffer兩字串及其指標,編輯框設為空字串,bIfExecute設為零
Initiation      proc    uses eax ecx edi,hwnd:HWND
        cld
        sub     eax,eax
        mov     edi,offset szExpression
        mov     ecx,CD_LEN/2
        mov     bIfExecute,al
        rep     stosd
        dec     eax
        mov     edi,offset stCodeBuffer
        mov     ecx,CD_LEN/4
        rep     stosd
        invoke  SetDlgItemText,hwnd,IDE_EXPRESSION,offset szExpression
        mov     ptExpression,offset szExpression
        mov     ptCodeBuffer,offset stCodeBuffer
        ret
Initiation      endp
;---------------------------------------------------------------------
;求2 X(求2的X次方)
;輸入:ST-X
;輸出:ST-2^X
two_p_x proc
        local   fpu_cw:word
        fstcw   fpu_cw          ;取得控制字組
        fwait                   ;等待CPU儲存完畢
        mov     ax,fpu_cw       ;保存原控制字組
        and     fpu_cw,0f3ffh   ;使控制字組變成向負無限大捨入,欲達此目
        or      fpu_cw,00400h   ;的必須使控制字組第10、11位元變為 01
        fldcw   fpu_cw          ;載入新的控制字組
        fld     st              ;   x   ;   x   ;       ;
        frndint                 ;i=int x;   x   ;       ;向負無限大捨入
        mov     fpu_cw,ax                               ;取回舊的控制字組
        fldcw   fpu_cw          ;   i   ;   x   ;       ;載入舊的控制字組
        fsub    st(1),st        ;   i   ; f=x-i ;       ;ST(1)為小數部分,f
        fxch                    ;   f   ;   i   ;       ;交換
        f2xm1                   ; 2f-1  ;   i   ;       ;求 2 的小數部分次方
        fld1                    ;   1   ; 2f-1  ;   i   ;載入 1
        faddp   st(1),st        ;   2f  ;   i   ;       ;完成 2 的小數部分次方
        fscale                  ;   2x  ;   i   ;       ;使 2
        fstp    st(1)           ;   2x  ;       ;       ;去掉整數部分
        ret                     ;返回主程式
two_p_x endp
;---------------------------------------------------------------------
;計算 X^Y 之值
;原理:X^Y=2^(log2 X^Y)=2^(Y*log2 X) 此處log2 X表示以2為底,X之對數
;輸入:ST - 底數,X
;      ST1- 指數,Y
;輸出:若錯誤(零的零次方或底數為負值),則進位旗標被設定;
;      若沒錯誤,則進位旗標被清除,且ST為X^Y
x_p_y   proc
        local   fpu_sw:word
        ftst
        fstsw   fpu_sw
        fwait
        mov     ax,fpu_sw       ;把狀態字組移入AX
        sahf                    ;把狀態字組的高位元部份移入旗標
        jz      zero_base       ;底數為0
        jc      err1            ;--st0--;--st1--;若CY,表示底數為負數
                                ;   X   ;   Y
        fyl2x                   ;Ylog2 X;
        call    two_p_x         ;  X^Y  ;
        jmp     ok
zero_base:
        fcomp                   ;底數為零,彈出底數,然後再
        ftst                    ;檢查指數是否為零
        fstsw   fpu_sw
        mov     ax,fpu_sw
        sahf
        jz      err2            ;若為ZR,表示指數也為零
        fcomp
        fldz                    ;底數為零,指數不為零,其答案為零不須計算
ok:     clc
        jmp     exit
err1:   fcomp
err2:   fcomp
        stc
exit:   ret
x_p_y   endp
;---------------------------------------------------------------------
;在stCodeBuffer中,以ptCodeBuffer所指位址挑出一個TOKEN。
;何謂TOKEN呢?例如當stCodeBuffer為 07 11 1A 02 00,表示使用者輸入7+LOG20,
;此時共有4個TOKEN,分別是7、+、LOG、20。注意!一個完整的數值是一個TOKEN,
;因此20只算一個TOKEN,不是兩個TOKEN
GetToken        proc
        local   ifPoint:BYTE    ;數值是否出現小數
        mov     edx,ptCodeBuffer
        mov     ifPoint,0       ;先假設沒有小數點

gt0:    cmp     byte ptr [edx],0ffh
        je      gt5

;檢查TOKEN是否為數值,若為數值,跳至gt1
        cmp     byte ptr [edx],0bh
        jb      gt1

;此TOKEN為運算子
        mov     al,[edx]
        sub     al,10h
        inc     edx
        mov     current_code,al
        cmp     al,2            ;若AL=2,表示此運算子為「-」
        jne     gt5
;檢查「-」是負號或者減號,如果「-」在「)」之後或者「-」出現於
;數字之後,為減號;否則「-」為負號
        cmp     previous_code,6 ;前一運算子為數字或「)」,表示
        je      gt5             ;此TOKEN為減號
        cmp     previous_code,0
        je      gt5
        mov     current_code,7  ;此TOKEN為負號
        jmp     gt5

;此TOKEN為數值(運算元)
gt1:    mov     current_code,0  ;--st0--;--st1--;--st2--;
        fldz                    ;  i=0  ;       ;
gt2:    mov     al,[edx]
        inc     edx
        cbw
        mov     dwNum,ax
        cmp     al,0ah          ;若AL為小數點
        je      gt3
        cmp     ifPoint,0       ;檢查是否曾出現過小數點,若曾
        jne     gt4             ;經則跳至gt4;若否則繼續執行
        fimul   dwTen           ; i=10i ;       ;
        fiadd   dwNum           ; i=i+AL;       ;
        cmp     byte ptr [edx],0bh
        jb      gt2
        jmp     short gt5
gt3:    inc     ifPoint
        cmp     ifPoint,1       ;若ifPoint超過1,表示輸入兩個小數點
        ja      gt6
        fldz                    ;   0   ;   i   ;
        fld1                    ;   1   ;   0   ;   i   ;
        fidiv   dwTen           ; t=0.1 ;  f=0  ;   i   ;
        jmp     gt2
gt4:    fld     st(0)           ;   t   ;   t   ;   f   ;   i   ;
        fimul   dwNum           ;  f*t  ;   t   ;   f   ;   i   ;
        faddp   st(2),st        ;   t   ;f=f*t+f;   i   ;
        fidiv   dwTen           ; t=t/10;   f   ;   i
        cmp     byte ptr [edx],0bh
        jb      gt2
        fcomp   st(0)           ;   f   ;   i   ;
        faddp   st(1),st        ; n=f+i ;
gt5:    mov     ptCodeBuffer,edx
        clc
        jmp     gt7
gt6:    stc
gt7:    ret
GetToken        endp
;---------------------------------------------------------------------
Execute proc    uses esi edi
        local   fpu_sw:word
        finit
        mov     ptCodeBuffer,offset stCodeBuffer
        mov     lpPostfix,offset stPostfix
        mov     lpNumTemp,offset aryNumTemp

;把「=」運算子存於aryOpStack,當取出「=」運算子時表示最後一個運算子
        mov     lpOpStack,offset aryOpStack
        mov     al,0ch
        mov     edx,lpOpStack
        mov     byte ptr [edx],al
        inc     lpOpStack
        mov     current_code,al         ;設定current_code為「=」運算子

;取出一個TOKEN,若CY表示輸入有問題。若NC表示沒問題,若此TOKEN為數值,則該數值
;存於ST(0),current_code為0;若此TOKEN為運算子,則current_code為運算子之內碼。
get_tk: mov     al,current_code
        mov     previous_code,al
        call    GetToken
        jnc     @f
        mov     edx,offset szErrorMsg1
        jmp     complete

;檢查運算子之語法是否正確,檢查方法是建立parse_table,以當前內碼與前一內碼查
;閱此表格。如果為1,表示語法正確;若為0表示語法錯誤。
@@:     movzx   eax,previous_code        ;計算EDX=previous_code*13+current_code
        mov     cx,0dh
        mul     cx
        movzx   edx,current_code
        add     edx,eax
        mov     cl,parse_table[edx]     ;CL=0表語法錯誤,CL=1表語法正確
        mov     al,current_code
        or      cl,cl
        jnz     syntax_correct
syntax_error:
        mov     edx,offset szErrorMsg0
error:  stc
        jmp     complete

;語法正確,開始把中序運算式轉換成後序運算式。
syntax_correct:
        mov     edi,lpPostfix
        cmp     al,0            ;若AL=0,表示TOKEN為運算元
        jnz     not_number
        mov     [edi],al        ;在後序式字串輸出運算元之內碼,0
        inc     lpPostfix
        mov     edx,lpNumTemp
        fstp    tbyte ptr [edx] ;而真正的運算元存放在aryNumTemp陣列
        add     lpNumTemp,10    ;指向aryNumTemp陣列的下一個成員
        jmp     get_tk

not_number:
        cmp     al,6            ;檢查TOKEN是否為「)」
        jne     other_op_code
r_par0: mov     esi,lpOpStack   ;若TOKEN為「)」,則取出運算子堆疊中的運算子
r_par1: mov     al,[esi-1]      ;存入後序運算式字串,直到遇到「(」為止
        cmp     al,0ch          ;檢查運算子堆疊是否已經沒有運算子了
        je      syntax_error    ;,如果沒運算子,表示「)」比「(」多
        dec     esi
        cmp     al,5            ;遇到「(」,結束取出運算子的動作
        je      r_par2
        stosb
        jmp     r_par1
r_par2: mov     lpOpStack,esi
        mov     lpPostfix,edi
        jmp     get_tk

other_op_code:
        movzx   edx,al
        mov     cl,icp[edx]      ;CL=當前TOKEN的ICP
        mov     esi,lpOpStack
        dec     esi
        movzx   edx,byte ptr[esi]
        mov     ch,isp[edx]      ;CH=運算子堆疊頂的ISP
        cmp     cl,ch
        jbe     pop_op_code

;若當前運算子的ICP>運算子堆疊頂的ISP,則把當前運算子推入堆疊
push_op_code:
        mov     al,current_code
        mov     edx,lpOpStack
        mov     [edx],al
        inc     lpOpStack
        jmp     get_tk

;若當前運算子的ICP≦運算子堆疊頂的ISP,則彈出運算子堆疊頂
pop_op_code:
        mov     esi,lpOpStack
        sub     edx,edx
        mov     al,[esi-1]      ;取出運算子堆疊頂之運算子
        stosb                   ;輸出到後序式字串
        dec     esi             ;設定新的堆疊頂
        mov     dl,[esi-1]      ;取出新的運算子堆疊頂之運算子
        mov     ch,isp[edx]
        mov     lpOpStack,esi
        mov     lpPostfix,edi
        cmp     dl,0ch
        je      check_buf       ;若相等,表示運算子堆疊已經空了
        cmp     cl,ch           ;檢查TOKEN之ICP是否大於新運算子堆疊頂之ISP
        ja      push_op_code    ;若大於,則將TOKEN推入運算子堆疊
        jmp     pop_op_code     ;若小於等於,則彈出運算子堆疊頂至後序式字串
check_buf:
        mov     esi,ptCodeBuffer
        cmp     byte ptr [esi],0ffh
        jnz     push_op_code

postfix_ok:
        mov     al,current_code
        mov     edx,lpPostfix
        mov     [edx],al
        inc     lpPostfix
;至此已將中序運算式轉換後序運算式已經處理完成了

;開始計算後序運算式之值
        mov     lpPostfix,offset stPostfix
        mov     lpNumStack,offset aryNumStack
        mov     lpNumTemp,offset aryNumTemp
        mov     esi,lpPostfix
        mov     edi,lpNumStack

nxt_tk: sub     eax,eax
        lodsb
        mov     edx,eax
        shl     edx,2
        mov     ecx,10
        jmp     action[edx]

number::mov     edx,lpNumTemp   ;取得在aryNumTemp的運算元,每個運算元以暫時
@@:     mov     al,[edx]        ;實數型態存放,現在要把它移到aryNumStack
        stosb
        inc     edx
        loop    @b
        mov     lpNumTemp,edx
        mov     lpNumStack,edi
        jmp     nxt_tk

plus::  sub     edi,ecx         ;EDI指向aryNumStack的堆疊頂
        mov     edx,edi         ;EDX指向aryNumStack的堆疊頂的下一個
        sub     edx,ecx
        fld     tbyte ptr[edi]
        fld     tbyte ptr[edx]
        fadd
return: fstp    tbyte ptr[edx]
        mov     lpNumStack,edi
        jmp     nxt_tk

minus:: sub     edi,ecx
        mov     edx,edi
        sub     edx,ecx
        fld     tbyte ptr[edx]
        fld     tbyte ptr[edi]
        fsub
        jmp     return

multiple::
        sub     edi,ecx
        mov     edx,edi
        sub     edx,ecx
        fld     tbyte ptr[edi]
        fld     tbyte ptr[edx]
        fmul
        jmp     return

divide::
        sub     edi,ecx
        mov     edx,edi
        sub     edx,ecx
        fld     tbyte ptr[edx]  ;   x   ;       ;
        fld     tbyte ptr[edi]  ;   y   ;   x   ;
        ftst
        fstsw   fpu_sw
        fwait
        mov     ax,fpu_sw
        sahf
        jz      equal_2_zero    ;除以零是無意義的
        fdiv                    ;  x/y  ;       ;
        jmp     return
less_zero:
equal_2_zero:
        fcompp
err_p:  mov     edx,offset szErrorMsg1
        jmp     error

negative::
        mov     edx,edi
        sub     edx,ecx
        fld     tbyte ptr[edx]
        fchs
        fstp    tbyte ptr[edx]
        jmp     nxt_tk

exp10:: mov     edx,edi
        sub     edx,ecx
        fld     tbyte ptr[edx]
        fild    dwTen
        call    x_p_y
        jmp     return

reciprocal::
        mov     edx,edi
        sub     edx,ecx         ;--st0--;--st1--;
        fld1                    ;   1   ;       ;
        fld     tbyte ptr[edx]  ;   x   ;   1   ;
        ftst                    ;   x   ;   1   ;比較x是否等於零
        fstsw   fpu_sw
        fwait
        mov     ax,fpu_sw
        sahf
        jz      equal_2_zero    ;若x等於零,取其倒數值是無意義的
        fdiv
        fstp    tbyte ptr[edx]
        jmp     nxt_tk

log::   mov     edx,edi
        sub     edx,ecx         ;--st0--;--st1--;
        fld1                    ;   1   ;       ;
        fld     tbyte ptr[edx]  ;   x   ;   1   ;
        ftst                    ;   x   ;   1   ;比較x是否大於零
        fstsw   fpu_sw
        fwait
        mov     ax,fpu_sw
        sahf
        jbe     less_zero       ;若x小於或等於零,則取對數值是無意義的
        fyl2x                   ;1log2 x;        ;
        fldl2t                  ; log2 T; log2 x ;
        fdiv
        fstp    tbyte ptr[edx]
        jmp     nxt_tk

exponent::
        sub     edi,ecx
        mov     edx,edi         ;EDI=指數位址
        sub     edx,ecx         ;EDX=底數位址
        fld     tbyte ptr[edi]
        fld     tbyte ptr[edx]
        call    x_p_y           ;求X的Y次方(X=ST=底數;Y=ST(1)=指數)
        jc      err_p
        jmp     return        

answer::sub     edi,ecx
        fld     tbyte ptr[edi]
        fstp    qword ptr[edi]
        invoke  FloatToStr2,qword ptr [edi],offset szAnswer
        mov     edx,offset szAnswer
        clc
complete:       ret
Execute endp
;---------------------------------------------------------------------
DlgProc proc    hWnd:HWND,uMsg:UINT,wParam:WPARAM,lParam:LPARAM
.if uMsg==WM_COMMAND
        mov     eax,wParam
        cmp     lParam,0
        jnz     bt_ctrl
        ;以下是使用者點選選單
        .if ax==IDM_EXIT
                jmp     exit
        .elseif ax==IDM_CLEAR
                invoke  Initiation,hWnd
        .elseif ax==IDM_PI
                mov     ecx,offset szPi
           pi0: .if bIfExecute!=0
                        invoke  Initiation,hWnd
                .endif
                mov     edx,ptExpression
                push    edi
                mov     edi,ptCodeBuffer
           pi1: mov     al,[ecx]
                inc     ecx
                or      al,al
                jz      pi4
                cmp     al,'.'
                jne     pi2
                mov     [edx],al
                mov     al,0ah
                jmp     pi3
           pi2: mov     [edx],al
                sub     al,'0'
           pi3: stosb
                inc     edx
                jmp     pi1
           pi4: mov     ptCodeBuffer,edi
                mov     ptExpression,edx
                pop     edi
                jmp     ctr4
        .elseif ax==IDM_EULER
                mov     ecx,offset szEuler
                jmp     pi0
        .endif
        jmp     not_deal

        ;以下是使用者選按按鈕
bt_ctrl:mov     edx,eax
        shr     edx,16
        cmp     dx,BN_CLICKED
        jne     not_deal
        cmp     bIfExecute,0            ;若使用者在之前已按下「EXE」按鈕,則表示已
        jz      ctr0                    ;完成計算先前的運算式,故得先初始化一些資料
        invoke  Initiation,hWnd
ctr0:   mov     ecx,ptExpression        ;若運算式內字元超過200則不處理
        sub     ecx,offset szExpression
        cmp     cx,200
        jae     not_deal
        .if ax>=3000
                ;若使用者輸入數字或小數點,其識別碼從3000到3010
                sub     ax,3000
                mov     ecx,ptCodeBuffer
                mov     [ecx],al
                mov     ecx,ptExpression
                cmp     al,10           ;檢查是否為小數點,小數點的識別碼為3010
                jne     ctr1
                sub     al,0ch          ;是小數點,則使AL再加6,小數點內碼為0AH
          ctr1: add     al,'0'
                mov     [ecx],al
          ctr2: inc     ptExpression
          ctr3: inc     ptCodeBuffer
          ctr4: invoke  SetWindowText,hwndEdit,offset szExpression
                ;底下三行是用來設定編輯框內游標(caret)位置在最後一個字元
                mov     ecx,ptExpression
                sub     ecx,offset szExpression
                invoke  SendMessage,hwndEdit,EM_SETSEL,ecx,ecx
                invoke  SetFocus,hwndEdit
        .elseif ax==IDB_CLEAR           ;使用者按下「CLEAR」按鈕
                invoke  Initiation,hWnd
        .elseif ax==IDB_EXECUTE         ;使用者按下「EXECUTE」按鈕
                inc     bIfExecute
                mov     ecx,ptCodeBuffer
                mov     byte ptr [ecx],1ch
                invoke  Execute
                jc      ctr5
                mov     edx,offset szAnswer
          ctr5: invoke  SetDlgItemText,hWnd,IDE_EXPRESSION,edx
        .else   ;以下是使用者按下運算子按鈕
                sub     ax,7c0h         ;把運算子轉換成內碼
                mov     ecx,ptCodeBuffer
                mov     [ecx],al
                cmp     al,19h          ;檢查是否按下倒數、對數、指數按鈕
                jae     ctr7
                sub     al,11h          ;按下加減乘除括號或10的乘冪按鈕
                push    ebx
                mov     ebx,offset display_table
                xlat
                pop     ebx
          ctr6: mov     ecx,ptExpression
                mov     [ecx],al
                jmp     ctr2
          ctr7: ;倒數、對數、指數按鈕的字元不只一個,在ctr7:到ctr9:之間的程式片段處理
            .if al==19h
                mov     ecx,offset stReciprocal
                jmp     ctr8
            .elseif al==1ah
                mov     ecx,offset stLOG
                jmp     ctr8
            .elseif al==1bh
                mov     ecx,offset stExponent
                jmp     ctr8
            .elseif al==1ch
                mov     al,'='
                jmp     ctr6
            .endif
          ctr8: mov     edx,ptCodeBuffer
                mov     [edx],al
                push    edi     ;以下11行是用來把ECX所指字串,填入ptExpression位址中
                push    esi
                sub     eax,eax
                mov     esi,ecx
                lodsb
                mov     ecx,eax
                mov     edi,ptExpression
                add     ptExpression,ecx
                rep     movsb
                pop     esi
                pop     edi
          ctr9: jmp     ctr3
        .endif
not_deal:

.elseif uMsg==WM_INITDIALOG
        invoke  GetDlgItem,hWnd,IDE_EXPRESSION
        mov     hwndEdit,eax
        invoke  Initiation,hWnd

        invoke  LoadIcon,hInstance,offset CalcIcon
        invoke  SendMessage,hWnd,WM_SETICON,ICON_SMALL,eax

.elseif uMsg==WM_CLOSE
exit:   invoke  EndDialog,hWnd,NULL

.else
        mov     eax,FALSE
        ret
.endif
        mov     eax,TRUE
        ret
DlgProc endp
;---------------------------------------------------------------------
start:  invoke  GetModuleHandle,NULL
        mov     hInstance,eax
        invoke  DialogBoxParam,hInstance,offset DlgName,NULL,offset DlgProc,NULL
        invoke  ExitProcess,eax
;*********************************************************************
end     start

底下是資源描述檔,CALC.RC:

#include "c:\masm32\include\resource.h"

#define CalcMenu        1000

#define IDE_EXPRESSION  1000
#define IDB_CLEAR       1001
#define IDB_EXECUTE     1002
#define IDB_ADD         2001
#define IDB_SUB         2002
#define IDB_MUL         2003
#define IDB_DIV         2004
#define IDB_LPAREN      2005
#define IDB_RPAREN      2006
#define IDB_NEG         2007
#define IDB_EXP10       2008
#define IDB_RECIPROCAL  2009
#define IDB_LOG         2010
#define IDB_EXP         2011
#define IDB_N0          3000
#define IDB_N1          3001
#define IDB_N2          3002
#define IDB_N3          3003
#define IDB_N4          3004
#define IDB_N5          3005
#define IDB_N6          3006
#define IDB_N7          3007
#define IDB_N8          3008
#define IDB_N9          3009
#define IDB_DOT         3010

#define IDM_EXIT        3000
#define IDM_CLEAR       3001
#define IDM_PI          3002
#define IDM_EULER       3003

CalcIco ICON    CALC2.ICO

CalcMenu        MENU
BEGIN
  MENUITEM      "離開",IDM_EXIT
  MENUITEM      "清除",IDM_CLEAR
  POPUP         "常數"
    BEGIN
      MENUITEM  "圓周率",IDM_PI
      MENUITEM  "尤拉數",IDM_EULER
    END
END

CalcDlg DIALOG  0,0,111,108
STYLE   DS_SETFONT |WS_POPUP |WS_CAPTION |WS_VISIBLE |WS_SYSMENU
FONT    9,"Cambria"
MENU    CalcMenu
CAPTION "WANKER'S 計算機"
BEGIN
  CONTROL       ""     ,IDE_EXPRESSION,"EDIT"  ,ES_LEFT|WS_BORDER|ES_AUTOHSCROLL|ES_READONLY,3,3,105,12
  PUSHBUTTON    "10^x" ,IDB_EXP10     ,  3, 18, 24, 12
  PUSHBUTTON    "^(-1)",IDB_RECIPROCAL, 30, 18, 24, 12
  PUSHBUTTON    "LOG"  ,IDB_LOG       , 57, 18, 24, 12
  PUSHBUTTON    "x^y"  ,IDB_EXP       , 84, 18, 24, 12
  PUSHBUTTON    "+/-"  ,IDB_NEG       ,  3, 33, 24, 12
  PUSHBUTTON    "("    ,IDB_LPAREN    , 30, 33, 24, 12
  PUSHBUTTON    ")"    ,IDB_RPAREN    , 57, 33, 24, 12
  PUSHBUTTON    "÷"    ,IDB_DIV       , 84, 33, 24, 12
  PUSHBUTTON    "7"    ,IDB_N7        ,  3, 48, 24, 12
  PUSHBUTTON    "8"    ,IDB_N8        , 30, 48, 24, 12
  PUSHBUTTON    "9"    ,IDB_N9        , 57, 48, 24, 12
  PUSHBUTTON    "×"    ,IDB_MUL       , 84, 48, 24, 12
  PUSHBUTTON    "4"    ,IDB_N4        ,  3, 63, 24, 12
  PUSHBUTTON    "5"    ,IDB_N5        , 30, 63, 24, 12
  PUSHBUTTON    "6"    ,IDB_N6        , 57, 63, 24, 12
  PUSHBUTTON    "-"    ,IDB_SUB       , 84, 63, 24, 12
  PUSHBUTTON    "1"    ,IDB_N1        ,  3, 78, 24, 12
  PUSHBUTTON    "2"    ,IDB_N2        , 30, 78, 24, 12
  PUSHBUTTON    "3"    ,IDB_N3        , 57, 78, 24, 12
  PUSHBUTTON    "+"    ,IDB_ADD       , 84, 78, 24, 12
  PUSHBUTTON    "0"    ,IDB_N0        ,  3, 93, 24, 12
  PUSHBUTTON    "."    ,IDB_DOT       , 30, 93, 24, 12
  PUSHBUTTON    "CLEAR",IDB_CLEAR     , 57, 93, 24, 12
  PUSHBUTTON    "EXE"  ,IDB_EXECUTE   , 84, 93, 24, 12
END

底下是製作檔,CALC.MAK:

NAME=CALC
ALL:$(NAME).exe
$(NAME).exe: $(NAME).asm $(NAME).res
        ml $(NAME).asm /link $(NAME).res

$(NAME).res: $(NAME).rc CALC2.ICO
        rc $(NAME).rc

要製作可執行檔時,需要把 CALC.ASM、CALC.MAK、CALC.RC、CALC2.ICO 四個檔案放在同一子目錄,開啟「命令提示字元」,利用「cd」指令切換到含有所在的子目錄堙A再輸入「nmake -f calc.mak」即可得 CALC.EXE 可執行檔,過程如下:

E:\HomePage\SOURCE\CALC>nmake -f calc.mak [Enter]

Microsoft (R) Program Maintenance Utility   Version 1.50
Copyright (c) Microsoft Corp 1988-94. All rights reserved.

        rc CALC.rc
        ml CALC.asm /link CALC.res
Microsoft (R) Macro Assembler Version 6.14.8444
Copyright (C) Microsoft Corp 1981-1997.  All rights reserved.

 Assembling: CALC.asm
Microsoft (R) Incremental Linker Version 5.12.8078
Copyright (C) Microsoft Corp 1992-1998. All rights reserved.

/SUBSYSTEM:WINDOWS
"CALC.obj"
"/OUT:CALC.exe"
"CALC.res"

E:\HomePage\SOURCE\CALC>

解說

處理使用者輸入的資料

CALC 的計算流程大致分為兩階段:處理使用者輸入的資料和計算結果。第一階段是處理使用者輸入的資料,在這階段中,最主要的工作是把使用者所輸入的按鈕,轉變成一個個的「內碼」存於 stCodeBuffer 堙C例如使用者依序按下「7」「+」「LOG」「2」「0」「EXE」六個按鈕,stCodeBuffer 會存入 7、11H、1AH、2、0、1CH 這些內碼。小木偶把數值的內碼規劃成 0∼0AH ( 0∼9 表示數值,0AH 表示小數點 ),而「+」「-」「×」「÷」「(」「)」等運算子的內碼從 11H、12H……開始。( 0BH∼10H 沒有用到 )

除此之外,CALC 還會把使用者所下的每一個按鈕記錄,以字元的方式記錄在 szExpression 字串堙C以上面為例,當使用者依序按下「7」「+」「LOG」「2」「0」「EXE」六個按鈕後,szExpression 會存入「7+LOG20=」這個字串。當然,szExpression 字串與 stCodeBuffer 是同步的。這段程式在標記 bt_ctrl: 到 not_deal: 之間。

在第一階段中,有幾個地方值得一提。第一個是當使用者輸入的資料很多而超過編輯框所能顯示的範圍時,應該要把最後一個字元顯示在編輯框右邊。小木偶找了許多資料,似乎無用,最後只得用一個變通的方法,那就是利用在編輯框中選定一段文字,這樣可以迫使編輯框的游標 ( caret ) 移至選定的文字。我們可以對編輯框發出 EM_SETSEL 訊息來選定文字。

計算結果

CALC 的第二階段是計算,亦即使用者按下「EXE」之後的過程。此過程的第一步是把 bIfExecute 變數設為一,表示已按下「EXE」按鈕。想想我們一般使用計算機時,按下「=」後會在液晶螢幕顯示計算結果,如果還要再繼續計算下一個算式,不須按「C」,可直接按任何一按鈕就會清除所有記錄。bIfExecute 的設定就是為了此一目的,當使用者按下任一按鈕,會先檢查 bIfExecute 是否為一,如果是的話表示前一次按下的按鈕是「EXE」,應先執行 Initiation 副程式,清除 szExpression、stCodeBuffer 之後,再處理其他事情。

接著 CALC 開始計算使用者所輸入運算式了。所有計算的過程都在 Execute 副程式中執行,Execute 副程式會先在 stCodeBuffer 字串堿D選出每一個 TOKEN。所謂 TOKEN 是指每個算式中的運算子或運算元 ( 小木偶不知如何翻譯這個字,故直接以原文表示 ),例如上面所輸入的運算式是「7+LOG20=」,第一個 TOKEN 是 7,第二個 TOKEN 是 +,第三個是 LOG,第四個是 20,最末一個是 =,挑出一個個 TOKEN 的工作由 GetToken 副程式負責。

GetToken 檢查內碼是否超過 0BH 來判斷所取得的是運算子還是運算元,如前面所說,小木偶以 0∼0AH 表示數值,超過這範圍即為運算子。若為數值,則執行標記 gt1: 到 gt7: 之間的程式,這段程式會不斷的從 stCodeBuffer 中讀取一個個的數值內碼,直到不是數值為止。它會把所得的數值存在 ST(0) 堙A並且把 current_code 設為零。如果是運算子的話,則把內碼減去 10H 當成 current_code。

每次取得一個 TOKEN 後,接著要做的事是檢查使用者所輸入的語法是否正確,例如使用者不能輸入類似「7+*LOG20」這種運算式。這段檢查語法正確與否的程是在 check: 標記與 syntax_error: 標記之間。檢查的方法是利用一張叫做「parse table」表格檢查,parse table 的縱座標與橫座標分別是各種不同的 TOKEN ( 運算子或運算元 ),如下表。在這表格堙A運算元用 0 表示,加、減、乘、除、左括號、右括號、負號、10x、x-1、LOG、xy、等於分別用 1、2、3、4、5、6、7、8、9、0AH、0BH、0CH 表示。可以看出來,運算子在 parse table 中的代碼與內碼相差 10H。

;parse table (x,y)=(現在的,前一個的)
;                                       10  L
;                                       冪倒O 指
;                       N + - * / ( ) - 方數G 數=
;                       0 1 2 3 4 5 6 7 8 9 A B C
parse_table     BYTE    0,1,1,1,1,0,1,0,1,1,0,1,1  ;0 N
                BYTE    1,0,0,0,0,1,0,1,1,0,1,0,0  ;1 +
                BYTE    1,0,0,0,0,1,0,1,1,0,1,0,0  ;2 -
                BYTE    1,0,0,0,0,1,0,1,1,0,1,0,0  ;3 *
                BYTE    1,0,0,0,0,1,0,1,1,0,1,0,0  ;4 /
                BYTE    1,0,0,0,0,1,0,1,1,0,1,0,0  ;5 (
                BYTE    0,1,1,1,1,0,0,0,0,1,0,1,1  ;6 )
                BYTE    1,1,1,1,1,1,0,2,1,0,1,0,0  ;7 -(負號)
                BYTE    1,0,0,0,0,1,0,1,0,0,1,0,0  ;8 10冪方
                BYTE    0,1,1,1,1,0,1,0,0,1,0,0,1  ;9 x-1倒數(R)
                BYTE    1,0,0,0,0,1,0,1,1,0,1,0,0  ;A LOG
                BYTE    1,0,0,0,0,1,0,1,1,0,1,0,0  ;B xy指數
                BYTE    1,0,0,0,0,1,0,1,1,0,1,0,1  ;C =

底下,小木偶稍微解釋檢查語法過程。運算式語法的正確與否,是依據上下文來決定,如果使用者輸入「7+*LOG20」這種運算式,7 與 + 連在一起是合理的,但是 + 與 * 連在一起就是錯誤的。以上面為例子:當第一個 TOKEN,7 被取出後,此為運算元,故 current_code 為 0,與前一個 TOKEN 比較 ( 前一個 TOKEN 為「=」,previous_code 為 0CH,在一開始就先假設第零個 TOKEN 是「=」 ),在 parse_table 查出為一 ( 上表藍色字 ),故語法正確。接著取出的 TOKEN 是「+」,與前一 TOKEN,運算元,比較、查表,得到一 ( 上表白色字 )。接著取出的 TOKEN 是「*」,與前一 TOKEN,「+」,比較、查表得零 ( 上表紅字 ),發生語法錯誤。所以 parse table 的用法是先根據前一個的 TOKEN 查出縱座標,再由當前 TOKEN 查橫座標,即可得上下文是否正確。

若語法正確,接下來的步驟就是把中序運算式變成後序運算式,其方法已在前面敘述過了,就不再多說。此處值得一提的是,等到在 stCodeBuffer 堜狾酗瑤X都處理完畢後,後序運算式會存在 stPostfix 字串堙A例如使用者輸入「7+LOG20=」的後序運算式為「7 20 LOG +」。但是在 stPostfix 字串堨H一個位元組表示一個 TOKEN,運算子長僅一個位元組沒有問題,而運算元無法以一個位元組表示。小木偶以零表示此 TOKEN 為運算元來解決這個問題,而真正的運算元則存於 aryNumTemp 陣列堙A此陣列可存放 50 個運算元,每個運算元是 10 位元組長的暫時實數的格式存放,以符合 80x87 的運算。所以最後所得的 stPostfix 是「0 0 0AH 1 0CH」,而 aryNumTemp 陣列則存入 7、20 的暫時實數格式。

緊接著的步驟是計算後序運算式,其方法也在前面提過了,此處也不多說。但在程式的寫作上面,小木偶用了兩個技巧。一是 stPostfix 為後序運算式,堶惘s有使用者輸入的運算元與運算子,運算元以 0 表示,而真正的運算元則存於 aryNumTemp 堙A與 stPostfix 相對應。aryNumStack 則是運算元堆疊,是用來儲存運算元的,前面提過,後序運算式計算結果時,遇運算元則把運算元存於運算元堆疊中,遇運算子時則字運算元堆疊取出運算元計算。二是計算時須依據各運算子跳到不同的程式處執行,此處小木偶不以 .if/.elseif/.endif 的方法檢查,而用底下的方法:

action          DWORD   number,plus,minus,multiple,divide,0,0,negative
                DWORD   exp10,reciprocal,log,exponent,answer
……………………
        jmp     action[edx]
number::        ;處理運算元,亦即推入 aryNumStack
                ……………………
plus::          ;加法
                ……………………
minus::         ;減法
                ……………………
multiple::      ;乘法
                ……………………

這種方式是把各個標記 ( number::、plus::、minus::……) 的位址,都收集起來集合成 action 陣列,然後以 EDX 為索引執行跳躍指令。也就是說,action 陣列其實是 number::、plus::、minus::……等標記位址所組成的陣列,每一標記所處的位址佔有四個位元組,所以只要把運算子的 TOKEN 值乘以四,就可得以 action 為基準的偏移位址,然後以 JMP 指令跳躍至此位址執行所對應的運算。另有一件事值得注意,一般定義標記是用:

符號名:

而此處則是用

符號名::

後者多了一個冒號,不同之處在於前者所能作用的範圍是所定義的副程式,屬於局部的;而後者所能作用的範圍是公用的,屬於全域的。如果您把「number::」寫成「number:」,那麼在組譯時,MASM 會告訴您「error A2006: undefined symbol : plus」。

FloatToStr/2

FloatToStr/2 是 MASM32 Ver. 7 所提供的一個副程式,顧名思義,它的目的是把一個四字組 ( QWORD ) 的浮點數轉變成一個 ASCII 字串,其原型為:

FloatToStr2 proto   stdcall     fpin:QWORD, szDbl:PTR CHAR

在「X:\masm32\masm32.inc」檔案堙A包含了 FloatToStr2 的原型,因此更簡單的方法是直接包含 mams32.inc 以及其程式庫。( 在 X:\masm32\masm32.hlp 有 FloatToStr2 及其他副程式使用方法的說明,這些應該都是撰寫 Win32 組合語言的前輩心血結晶,而被 MASM32 收錄。)