スタックと文字列変換

初期状態が空であるスタックを用いて数字列を置換することを考える.スタックに対して,二つの操作「入力側の数字列の先頭の一つの数字をスタックに入れる」と「スタックから一つの数字を取り出して印字する」があり,それぞれの操作をS とXで表す.S とX を並べた列を操作列という.例えば,入力数字列1234 に対して,SSXSSXXX という操作列の操作を左から右に順に作用させると,数字列1234 は2431 に置換されて印字される.