如何在数学解析器中实现加法运算符 (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

如果您确实需要自己解析表达式，那么您应该搜索表达式的两边（例如“2*3”）并将其替换为您的答案（如果您正在尝试计算答案）或一个表达式对象（例如你的数组树，如果你想保留表达式的结构并在以后评估）。如果您按优先顺序执行此操作，则将保留优先级。

作为一个简化示例，您的表达式解析器应该：

重复搜索所有内部括号：/(([^)+]))/ 并将其替换为对 $1 的表达式解析器的调用（对丑陋的正则表达式感到抱歉:)

现在所有的括号都消失了，所以您正在查看数字之间的数学运算 and/or 表达式对象 - 对它们一视同仁
搜索乘法：/(expr|number)*(expr|number)/ 将其替换为答案或将两个表达式封装在一个新的表达方式。同样，取决于您现在需要答案还是如果你需要表达式树。
搜索加法：...等...

如果您现在正在计算答案，那么这很容易，每次调用表达式解析器最终（在必要的递归之后）returns 一个您可以用来替换原始表达式的数字。如果你想构建表达式树，以及如何处理字符串和表达式对象的混合，那么你可以运行一个正则表达式由你决定，你可以编码一个指向表达式的指针字符串中的对象，或者用对象数组替换外部的整个字符串，并使用类似于正则表达式的东西来搜索数组。

您还应该考虑处理一元运算符：“3*+3” （如果您采取的第一步是将所有数字转换为仅包含数字的简单表达式对象，这可能会简化事情，您可能可以在这里处理一元运算符，但这可能涉及棘手的情况，例如 "-3++ 1")

或者按照提示找一个表达式解析库。 :)

Answer 2

为了好玩，这里有一个有趣的基于正则表达式的 'parser'，它使用 @DavidLjungMadison 建议的很好的 "inside-out" 方法。它首先执行简单的 "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 = .to_i, , .to_i
        op=="*" ? m*n : m/n
      end
      go = true while expr.sub!(/(-?\d+)\s*([+-])\s*(-?\d+)/) do
        a,op,b = .to_i, , .to_i
        op=="+" ? a+b : a-b
      end
      go = true while expr.gsub!(/\(\s*(-?\d+)\s*\)/,'')
    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.

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

How to implement addition operator in math parser (ruby)

ruby

math

parsing