Fortran - スタックの実装（逆ポーランド記法による電卓）！

[ プログラミング, 数学 ] [ Fortran ]

Fortran 95 でスタックの実装を試してみました。
（応用で、逆ポーランド記法による電卓も作成）

0. 前提条件

  • LMDE 3 (Linux Mint Debian Edition 3; 64bit) での作業を想定。
  • GCC 6.3.0 (GFortran 6.3.0) でのコンパイルを想定。

1. テスト用ソースコードの作成

  • モジュール部分と実行部分を別ファイルに分けている。

まず、モジュール部分。

stack.f95
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

!****************************************************
! Stack モジュール
!
! date          name            version
! 2018.08.21    mk-mode.com     1.00 新規作成
!
! Copyright(C) 2018 mk-mode.com All Rights Reserved.
!****************************************************
!
module stack
  implicit none
  private                           ! デフォルトを private に設定
  public :: pop, push               ! pop, push のみ public とする
  ! 以下の変数は private となる。
  integer, parameter :: pmax = 256  ! スタックの最大長
  integer, save :: buf(1:pmax)      ! スタック配列
  integer, save :: p = 0            ! 最後（トップ）の要素の位置
contains
  ! Pop from a stack
  ! : スタックからトップノードを取り出す
  integer function pop()
    implicit none

    if (p > 0) then
      pop = buf(p)                  ! 最後の要素を取り出す
      p = p - 1                     ! 最後の要素の位置を左に 1 つずらす
    else
      print *, "Stack underflow!"
      pop = - huge(p)
    end if
  end function pop

  ! Push into a stack
  ! : スタックに n をトップノードとして付け加える
  !
  ! :param  integer n
  subroutine push(n)
    implicit none
    integer, intent(IN) :: n

    if (p < pmax) then
      p = p + 1                     ! 最後の要素の位置を右に 1 つずらす
      buf(p) = n                    ! 要素を付け加える
    else
      print * "Stack overflow!"
    end if
  end subroutine push
end module stack

そして、実行部分。

test_stack.f95
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

!****************************************************
! テスト (Stack モジュール)
!
! date          name            version
! 2018.08.21    mk-mode.com     1.00 新規作成
!
! Copyright(C) 2018 mk-mode.com All Rights Reserved.
!****************************************************
!
program main
  use stack
  implicit none
  integer :: i

  ! 1, 2, 3 を push
  do i = 1, 3
    call push(i)
  enddo

  ! 3 回 pop
  do i = 1, 3
    print *, pop()
  enddo

  stop
end program main

2. ソースコードのコンパイル

1

$ gfortran -o test_stack stack.f95 test_stack.f95

ちなみに、上の1行の方法ではなく make でビルドするなら、以下のように Makefile を作成する。（当方の例。行頭のインデントはタブ）

Makefile
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

FC = gfortran
CFLAGS = -c -O
TARGET = test_stack
OBJS = stack.o test_stack.o
MODS = stack.mod

.SUFFIXES: .f95

all: $(TARGET)

$(TARGET): $(OBJS)
  $(FC) -o $@ $(OBJS)

.f95.mod:
  $(FC) $(CFLAGS) $<

.f95.o:
  $(FC) $(CFLAGS) $<

clean:
  @rm -f $(TARGET) $(OBJS) $(MODS)

3. 動作確認

1
2
3
4

$ ./test_stack
           3
           2
           1

4. 応用

同じスタックモジュールを使用して、逆ポーランド記法による電卓を作成してみた。

rpn.f95
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

!****************************************************
! 逆ポーランド記法 (Stack モジュール使用)
!
! date          name            version
! 2018.08.21    mk-mode.com     1.00 新規作成
!
! Copyright(C) 2018 mk-mode.com All Rights Reserved.
!****************************************************
!
program main
  use stack
  implicit none
  character(len=80) :: buf
  integer :: i

  print '(A)', "Calculator by Reverse Polish Notation."
  do
    read (*,'(A80)') buf
    if (len(trim(buf)) == 0) exit

    do i = 1, len(trim(buf))
      select case (buf(i:i))
      case (" ")
        cycle
      case ("0":"9")
        call push(ichar(buf(i:i)) - ichar('0'))
      case ("+")
        call push(pop() + pop())
      case ("-")
        call push(- pop() + pop())
      case ("*")
        call push(pop() * pop())
      case ("=")
        exit
      case default
        print *, "Unknown operator."
        exit
      end select
    enddo

    print '(A,I15)', "Ans: ", pop()
  enddo

  stop
end program main

（モジュール部分は前項のものと同じ）

コンパイル。

1

$ gfortran -o rpn stack.f95 rpn.f95

ちなみに、上の1行の方法ではなく make でビルドするなら、以下のように Makefile を作成する。（当方の例）

Makefile
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

FC = gfortran
CFLAGS = -c -O
TARGET = rpn
OBJS = stack.o rpn.o
MODS = stack.mod

.SUFFIXES: .f95

all: $(TARGET)

$(TARGET): $(OBJS)
  $(FC) -o $@ $(OBJS)

.f95.mod:
  $(FC) $(CFLAGS) $<

.f95.o:
  $(FC) $(CFLAGS) $<

clean:
  @rm -f $(TARGET) $(OBJS) $(MODS)

そして、実行。（空 ENTER で終了）

1
2
3
4
5
6

$ ./rpn
Calculator by Reverse Polish Notation.
1 3 4 * + 5 + =
Ans:              18
1 2 + 4 5 + * =
Ans:              27

以上、