ruby - 如何在数学解析器(ruby)中实现加法运算符

Question

我正在尝试为 ruby​​ 中的数学表达式构建自己的求值器，在此之前，我正在尝试实现一个解析器以将表达式分解为树(数组)。它正确地用括号分解了表达式，但是我在试图弄清楚如何使它正确地分解具有运算符优先级的表达式时遇到了很多麻烦。

现在，像 1+2*3+4 这样的字符串变成了 1+[2*[3+4]] 而不是 1+[ 2*3]+4。我正在尝试做最简单的解决方案。

这是我的代码:

@d = 0
@error = false
#manipulate an array by reference
def calc_expr expr, array
    until @d == expr.length
        c = expr[@d]
        case c 
        when "("
            @d += 1
            array.push calc_expr(expr, Array.new)
        when ")"
            @d += 1
            return array
        when /[\*\/]/
            @d +=1
            array.push c
        when /[\+\-]/
            @d+=1
            array.push c
        when /[0-9]/
            x = 0
            matched = false
            expr[@d]
            until matched == true
                y = expr.match(/[0-9]+/,@d).to_s
                case expr[@d+x]
                when /[0-9]/
                    x+=1
                else matched = true
                end
            end
            array.push expr[@d,x].to_i
            @d +=(x)
        else 
            unless @error
                @error = true
                puts "Problem evaluating expression at index:#{@d}"
                puts "Char '#{expr[@d]}' not recognized"
            end
            return
        end
    end

    return array
end
@expression = ("(34+45)+(34+67)").gsub(" ","")
evaluated = calc @expression
puts evaluated.inspect

Answer 1

为了好玩，这里有一个有趣的基于正则表达式的“解析器”，它使用@DavidLjungMadison 建议的漂亮的“由内而外”方法。它首先执行简单的“a*b”乘法和除法，然后是“a+b”加法和减法，然后解开括号 (a) 中剩余的任何数字，然后重新开始。

为了简化正则表达式，我只选择支持整数；将每个 -?\d+ 扩展为更健壮的东西，并将 .to_i 替换为 .to_f 将允许它使用浮点值。

module Math
  def self.eval( expr )
    expr = expr.dup
    go = true
    while go
      go = false
      go = true while expr.sub!(/(-?\d+)\s*([*\/])\s*(-?\d+)/) do
        m,op,n = $1.to_i, $2, $3.to_i
        op=="*" ? m*n : m/n
      end
      go = true while expr.sub!(/(-?\d+)\s*([+-])\s*(-?\d+)/) do
        a,op,b = $1.to_i, $2, $3.to_i
        op=="+" ? a+b : a-b
      end
      go = true while expr.gsub!(/\(\s*(-?\d+)\s*\)/,'\1')
    end
    expr.to_i
  end
end

下面是一些测试:

tests = {
  "1"                            => 1,
  "1+1"                          => 2,
  "1 + 1"                        => 2,
  "1 - 1"                        => 0,
  "-1"                           => -1,
  "1 + -1"                       => 0,
  "1 - -1"                       => 2,
  "2*3+1"                        => 7,
  "1+2*3"                        => 7,
  "(1+2)*3"                      => 9,
  "(2+(3-4) *3 ) * -6 * ( 3--4)" => 42,
  "4*6/3*2"                      => 16
}

tests.each do |expr,expected|
  actual = Math.eval expr
  puts [expr.inspect,'=>',actual,'instead of',expected].join(' ') unless actual == expected
end

请注意，我在运算符上使用 sub! 而不是 gsub! 以便在最后一个测试用例中存活下来。如果我使用了 gsub!，那么 "4*6/3*2" 将首先变成 "24/6"，从而得到结果在 4 中，而不是正确的扩展 "24/3*2" → "8*2" → 16.