Ruby - 数式文字列 => 逆ポーランド記法 変換&計算(二分木使用)!

Updated:


Ruby で、入力した数式の文字列を逆ポーランド記法(RPN; 後置記法)に変換する処理を実装してみました。(ついでに、後置・中置・前置記法での計算も)
前回・前々回はスタックを使用した処理についてでした。

今回は二分木を使用した処理についてです。

0. 前提条件

  • Debian GNU/Linux 10.5 buster (64bit) での作業を想定。
  • Ruby 2.7.2 での作業を想定。
  • 演算子は *, /, +, - を想定。(単項演算子は非対応)
  • 括弧は (, ) のみに対応。

1. アルゴリズム

次のリンク先(分かりやすく、きれいにまとまっている)のとおり。(自分で説明しようとすると、煩雑化しそう)

2. Ruby スクリプトの作成

  • 括弧の開きと閉じの対応のチェックも行なう。
  • Shebang ストリング(1行目)では、フルパスでコマンド指定している。(当方の慣習

File: infix2rpn_bt.rb

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
#! /usr/local/bin/ruby
#*********************************************************
# Ruby script to convert string to RPN (by binary tree).
# (Unary operators are not supported)
#*********************************************************

class Node
  attr_reader :expr

  def initialize(expr)
    # ノードを構成するデータ構造
    @expr  = expr  # このノードが表す式
    @left  = nil   # 左の子ノード
    @right = nil   # 右の子ノード
  end

  # 丸カッコ対応数チェック
  #
  # @return bool res: true(OK)|false(NG)
  def valid_bracket
    res = true
    nest = 0  # 丸カッコのネスト数

    begin
      @expr.split(//).each do |e|
        nest += 1 if e == "("
        if e == ")"
          nest -= 1
          break if nest < 0
        end
      end
      res = false unless nest == 0
      return res
    rescue => e
      raise
    end
  end

  # 解析(二分木に分割)
  def parse
    # 数式の最も外側のカッコを除去
    @expr = rm_most_outer_bracket(@expr)
    # 演算子の位置
    pos_operator = get_operator_pos(@expr)
    # 演算子が存在しない場合、項とみなす
    return if pos_operator < 0
    # 子ノード(左)
    @left = Node.new(rm_most_outer_bracket(@expr[0, pos_operator]))
    @left.parse
    # 子ノード(右)
    @right = Node.new(rm_most_outer_bracket(@expr[pos_operator + 1, @expr.size]))
    @right.parse
    # 演算子
    @expr = @expr[pos_operator]
  rescue => e
    raise
  end

  # 文字列生成(後置記法(逆ポーランド記法; RPN))
  def gen_post
    @left .gen_post if @left
    @right.gen_post if @right
    print "#{@expr} "
  rescue => e
    raise
  end

  # 文字列生成(中置記法(挿入記法))
  def gen_in
    print '(' if @left && @right
    @left .gen_in if @left
    print @expr
    @right.gen_in if @right
    print ')' if @left && @right
  rescue => e
    raise
  end

  # 文字列生成(前置記法(ポーランド記法))
  def gen_pre
    print "#{@expr} "
    @left .gen_pre if @left
    @right.gen_pre if @right
  rescue => e
    raise
  end

  # 値の計算
  #
  # @return float res: 計算結果
  def calc
    return @expr.to_f unless @left && @right
    res = 0

    begin
      operand_l = @left.calc
      operand_r = @right.calc
      case @expr
      when '+'; res = operand_l + operand_r
      when '-'; res = operand_l - operand_r
      when '*'; res = operand_l * operand_r
      when '/'; res = operand_l / operand_r
      end
      return res
    rescue => e
      raise
    end
  end

private
  # 数式の最も外側のカッコを除去
  #
  # @param  string expr: 数式文字列(カッコ除去前)
  # @return string expr: 数式文字列(カッコ除去後)
  def rm_most_outer_bracket(expr)
    res  = false  # true: 数式の最も外側にカッコあり, false: なし
    nest = 0      # カッコのネスト数

    begin
      # 最初の文字が "(" の場合、最も外側にカッコがあると仮定
      if expr[0] == "("
        res  = true
        nest = 1
      end
      # 2文字目以降、チェック
      expr[1..].split(//).each_with_index do |e, i|
        case e
        when "("
          nest += 1
        when ")"
          nest -= 1
          # 最後以外でカッコが全て閉じられた場合、最も外側にカッコはないと判断
          # 例:"(1+2)+(3+4)"などの場合
          if nest == 0 && i < expr.size - 2
            res = false
            break
          end
        end
      end
      # 最も外側にカッコがない場合、元の文字列をそのまま返す
      return expr unless res
      # カッコ内がからの場合、エラー
      puts "[ERROR] Empty bracket! #{expr}" if expr =~ /^\(\)$/
      # 最も外側のカッコを除去
      expr = expr[1..-2]
      # 更に最も外側にカッコが残っている場合、再帰的に処理
      expr = rm_most_outer_bracket(expr) if expr =~ /^\(.*?\)$/
      return expr
    rescue => e
      raise
    end
  end

  # 演算子の位置を取得
  #
  # @param string expr: 数式文字列
  # @return    int pos: 演算子の位置
  #                     (演算子が存在しない場合は -1 を返す)
  def get_operator_pos(expr)
    return -1 if expr.to_s.empty?
    pos     = -1  # 演算子の位置初期化
    nest    = 0   # カッコのネスト数
    pri_min = 4   # 演算子のこれまでで最も低い優先度
                  # (値が大きいほど優先度高)

    begin
      expr.split(//).each_with_index do |e, i|
        pri = 0  # 演算子の優先度
        case e
        when "="; pri = 1
        when "+"; pri = 2
        when "-"; pri = 2
        when "*"; pri = 3
        when "/"; pri = 3
        when "("; nest += 1; next
        when ")"; nest -= 1; next
        else; next
        end
        if nest == 0 && pri <= pri_min
          pri_min = pri
          pos = i
        end
      end
      return pos
    rescue => e
      raise
    end
  end
end

class Str2RpnBt
  def exec
    # 数式入力&空白除去
    print 'Formula? '
    f = gets.chomp.gsub(/ /, "")
    # Node クラスのインスタンス化
    root = Node.new(f)
    # 丸カッコ対応数チェック
    unless root.valid_bracket
      puts "[ERROR] Brackets are unbalanced!"
      exit
    end
    # 解析(二分木分割)
    puts "---"
    puts "                Formula: #{root.expr}"
    root.parse
    # 文字列生成(後置記法(逆ポーランド記法; RPN))
    print "Reverse Polish Notation: "
    root.gen_post
    puts
    # 文字列生成(中置記法(挿入記法))
    print "         Infix Notation: "
    root.gen_in
    puts
    # 文字列生成(前置記法(ポーランド記法))
    print "        Polish Notation: "
    root.gen_pre
    puts
    # 値の計算
    print "                Answer = "
    print root.calc
    puts
  rescue => e
    $stderr.puts "[#{e.class}] #{e.message}"
    e.backtrace.each{ |tr| $stderr.puts "\t#{tr}" }
    exit 1
  end
end

Str2RpnBt.new.exec if __FILE__ == $0

3. 動作確認

まず、実行権限を付与。

$ chmod +x infix2rpn_bt.rb

そして、実行。
元の数式(中置記法)を入力してエンターを押下すると、逆ポーランド記法(RPN)・中置記法・前置記法、そして、計算結果が出力される。

$ ./infix2rpn_bt.rb
Formula? 2 * (3 + (12 - 8)) / 7
---
                Formula: 2*(3+(12-8))/7
Reverse Polish Notation: 2 3 12 8 - + * 7 /
         Infix Notation: ((2*(3+(12-8)))/7)
        Polish Notation: / * 2 + 3 - 12 8 7
                Answer = 2.0

以上。





 

Sponsored Link

 

Comments