2018年12月1日 星期六

字串

字串


Ching-Tang Tseng
Hamilton, New Zealand
2 December 2018



貼文只是我的義務,不是責任。所以,我有空才貼,逐次貼。這一篇,慢慢貼。



1. 字串元素的建立





此處,

我們把傳統的包封字串稱為小字串,相關操作指令盡量以小寫的 s 起首。

我們把現行巨型包封字串稱為大字串,相關操作指令盡量以 號為起首。



\\\\\\\\\\
Forth 程式語言描述此種字串之資料結構的建立方法為
: string
 create allot align   ( n -- )    創建時
 does>              ( -- addr ) 執行時
;
這樣的設計,對大小字串而言,同樣適用,創建時的宣告範例如
   40  string   name1  小字串
4000  string   name2   大字串
\\\\\\\\\\


事實上,可以不必這麼麻煩。上列程式,只是為了解說方便而寫,確實能夠達到資料結構的宣告目的。

改成下列的宣告方式,產生的結果,將完全相同,我們卻可以在系統中省下一個多餘指令 string 的用名。

解決一件事情的方法,如果可以有好幾個,那麼,最簡單的一個,就是最好的一個。





正規的宣告方式,可以經由下列所示完成

create   name1     40 allot   小字串

create   name2     4000 allot   大字串


2. 輸出顯示字串元素的內容



2.1 小字串

想要印出字串時的執行方法

name1   count    type

count  的執行工作
count   ( addr – addr+1 len )

type    的執行要求
type    ( addr+1 len -- )


2.2 大字串

想要印出字串時的執行方法

name2    $@    type

$@   的執行工作
$@   ( addr --- addr+cell len )

type  的執行要求
type   ( addr+cell len -- )

請注意! 大字串直接使用 type 印出字串的方式,與小字串使用的方式類似。差別僅在大字串使用 $@,小字串使用 count



3. 輸入字串放進字串元素



採取能夠自動形成包封字串的指令 S” ……..” 直接輸入字串時,大小字串的程式寫法也類似。

例如

S” 此字串將存入小字串元素 name1”   name1   s!    小字串

S” 此字串將存入大字串元素 name2”   name2   $!    大字串

這樣的寫法,也可以寫進程式中使用。利用 2 中已介紹過的印出字串方法,則可以驗證執行結果。

S” ……..”    的執行結果,提供了s! $! 所需要的前兩個參數,name1name2則提供出第三個所需要的參數。

S” ……..”    也可以提供type執行前所需要的兩個參數。

S” ……..”    ( -- addr len )

s!   ( addr1 len addr2 -- )   憑三個參數,將addr1處的指定字串,放進小字串元素addr2內。


Lina64中,沒有現成的 s! 指令,簡單的高階定義設計如下:

: s!    ( addr1 len addr2 -- )

 2dup c!  1+ swap  cmove   ;

$!   ( addr1 len addr2 -- )   憑三個參數,將addr1處的指定字串,放進大字串元素addr2內。


4. 存取字串元素內容所需要的額外指令



字串元素的內容經常需要被進行額外的運作,尤其是常須逐漸地加大、加長,我可以舉出許多個自己曾經用過的這種例子。


例如:

想要逐次增加一個內容為龐大規模的字串,最後形成一個檔案。

字串可被分成幾個小段的文字,要先行組合完畢後,才能整串拿來當命令使用。

舉凡,大數字的輸出,都得逐個字元轉換,轉換完畢後,才一次性的印出來。不這樣做,系統的執行速度就會非常慢。

等等。


因此,在初次宣告出字串元素時,我們經常會先行配給較多或較大量的記憶體,供字串元素使用。

字串內容增長的方式具有規律性,是較為常見的需求,配合這種需要,系統提供現成的指令。

每次只增加單一個字元於字串尾部時,指令的慣用名稱為:

: sc+ ( c addr -- )    小字串
  dup >r dup c@ + 1+ c! 1 r> c+! ;

$c+   ( c addr -- )    大字串


每次要增加一個字串於原有字串的尾部時,指令的慣用名稱為:

: s+! ( addr1 len addr2 -- )   小字串
  dup c@ >r 2dup c+! 1+ r> + swap cmove ;

$+!   ( addr1 len addr2 -- )   大字串


Lina64系統中,另有兩個現成較為常要用到的字串操作指令,此處僅列示其執行效果,不做深究。

這些大字串操作指令的功能,同樣適用於小字串,為什麼?請自行體會。這就是為什麼一開始我就把字串的結構設計成那種規格的主因。

String find accorging to c :

$^ ( addr1 len c -- addr2 )


String split according to c :

$/ ( addr1 len1 c -- addr2 len2 addr3 len3 )



5. 字串元素的函數



像數學體系一樣,字串元素所形成的集合,也能進行函數方式的運算。這方面的擴展應用非常廣泛,無法窮舉,此處僅列舉一些用來建立概念的範例。

特別聲明:前兩個指令的原始設計人是 Hugh Aguilar,原始程式曾經由作者公開張貼於國際論壇,我將源程式修改成在 Lina64 系統可以使用的格式,特此致謝,表示尊重。

這幾個指令,都同樣可以使用於大或小字串的操作上,理由同上。

比較兩個字串是否一樣?所得結果為真或為假之值。

: str= ( adrA lenA adrB lenB -- flag )  \ compare the strings for equality
  2 pick <> if  drop drop drop  false exit then
  tuck + swap 
  ?do                        \ -- adrA
       dup c@  I c@  <> if  drop false  unloop exit then
       1+
  loop
  drop true ;

將一個字串的內容就地反轉,產生的結果仍然放在原位址上,但為與原字串反向排列的新字串。

: $reverse ( addr len -- )
  2dup + -rot                  \ -- limit-adr adr cnt
  2/  over + swap
  ?do  1-          \ -- last-adr
       dup    c@  I c@            \ -- last-adr last-char char
       2 pick c!  I c!
  loop
  drop ;

將兩個字串相加,結果放在後一個字串的內容上。

: $+ ( addr1 len1 addr2 len2 -- addr2 len3)
  2swap swap 2over + 2 pick cmove + ;




6. 實際應用範例



整理出上述有關字串指令的資料,是為了用來解決實際問題。

我所設計的 ABC FORTH 系統,過去,只專注於純粹的數學計算,忽略了字串處理。

自從需要處理網路訊息的要求全面到來之後,電腦程式語言就必須面對夾雜了字串處理要求的問題。

我從不久前國際論壇論及的一個知名網站,取用一個簡單問題作為範例,也應特此聲明,表示尊重。

求解這種類似的問題,需要數學計算與字串處理雙方面配合起來應用,才能解決問題。


網址在:

https://projecteuler.net/problem=4

題目為:

Largest palindrome product
Problem 4
A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.

Find the largest palindrome made from the product of two 3-digit numbers.

程式解:

create xy 4 cells allot
create yx 4 cells allot

: str= ( adrA lenA adrB lenB -- flag )      \ compare the strings for equality
    2 pick <> if  drop drop drop  false exit then
    tuck + swap  ?do                        \ -- adrA
        dup c@  I c@  <> if  drop false  unloop exit then
        1+  loop
    drop true ;

: $reverse ( addr len -- )
  2dup + -rot                  \ -- limit-adr adr cnt
  2/  over + swap
  ?do  1-          \ -- last-adr
       dup    c@  I c@            \ -- last-adr last-char char
       2 pick c!  I c!
  loop
  drop ;

4 integers a b x n

: main
basic
10 let n = 0
20 for a = 999 to 100 step -1
30 for b = a   to 100 step -1
40 let x = a * b
50 if x > n then 70
60 goto 120
70 run x (.) 2dup xy $! yx $! yx $@ $reverse
80 if xy $@ yx $@ str= then 100
90 goto 120
100 let n = a * b
110 print " a = " ; a ; " b = " ; b
120 next b
130 next a
140 print " n = " ; n
150 end
;

main

執行結果:

ching@center:~/lina64$ ./f

AMDX86 ciforth 5.3.0
fload palindromic.f
a : ISN'T UNIQUE                                               
b : ISN'T UNIQUE                                               
n : ISN'T UNIQUE                                               

a = 995 b = 583
a = 993 b = 913
n = 906609  OK
.s

S[ ] OK

最終的答案是:906609





沒有留言: