ruby - 支持负数的中缀形式

Question

我正在尝试解决一个问题:

Instructions

Given a mathematical expression as a string you must return the result as a number.

Numbers

Number may be both whole numbers and/or decimal numbers. The same goes for the returned result.

Operators

You need to support the following mathematical operators:

Multiplication *
Division /
Addition +
Subtraction -
Operators are always evaluated from left-to-right, and * and / must be evaluated before + and -.

Parentheses

You need to support multiple levels of nested parentheses, ex. (2 / (2 + 3.33) * 4) - -6

Whitespace

There may or may not be whitespace between numbers and operators.

An addition to this rule is that the minus sign (-) used for negating numbers and parentheses will never be separated by whitespace. I.e., all of the following are valid expressions.

1-1    // 0
1 -1   // 0
1- 1   // 0
1 - 1  // 0
1- -1  // 2
1 - -1 // 2

6 + -(4)   // 2
6 + -( -4) // 10
And the following are invalid expressions

1 - - 1    // Invalid
1- - 1     // Invalid
6 + - (4)  // Invalid
6 + -(- 4) // Invalid
Validation

从而使 '2/2+3 * 4.75- -6' 成为有效表达式。我已经能够为不尊重空格但不给出负数的表达式编写波兰形式。我认为如果负数尊重空格，我可以解决负数的问题。我的问题是，如果不考虑空格并且给出负数，如何实际标记输入表达式。到目前为止，这是我的算法:

def is_operator? s
  operators = ['*', '/', '+', '-']
  operators.include?(s)
end

def is_operand? s
    !(s =~ /^[0-9.]+$/).nil?
end

def priority op
  case op
    when "(" , ")" then 0
    when "/", "*" then 2
    else 1
  end
end

def eval(lt,rt,op)
  case op
    when '+' then lt.to_f + rt.to_f 
    when '-' then lt.to_f - rt.to_f  
    when '*' then lt.to_f * rt.to_f  
    when '/' then lt.to_f / rt.to_f  
  end
end

def indent_string s
    s.gsub(/[^[0-9.]]/) { |m| " #{m} "}.split(" ")
end

def create_polish s
    stack = Array.new()
    array = indent_string s
    fpp = ""
    array.each do |item|
        if is_operand? item
            fpp = fpp + item + " "
        else
            if item == '('
                stack << item
            else if is_operator? item
                    while stack.any? && ( priority(stack[-1]) >= priority(item) )
                        fpp = fpp + stack.pop + " "
                    end
                    stack << item
                 else
                    while stack.any? && !(stack[-1] == '(' )
                        fpp = fpp + stack.pop + " "
                    end
                    stack.pop
                 end
            end
        end
    end
    while stack.any?
        fpp = fpp + stack.pop + " "
    end
    fpp
end

def solve_polish s
  stack = Array.new()
  s.split(" ").each do |item|
    unless is_operator? item 
      stack << item
    else
      elements = stack.pop(2)
      stack << eval(elements[0], elements[1], item)
    end
  end
  puts stack.pop
end

solve_polish(create_polish '(5 + 2) * 9 - 10 + ( 7 * (2 + 3) ) - 3 * (2)')

它解决了不遵守空格规则的非负表达式，因为我创建了 indent_string 方法，该方法在每个运算符之前和之后放置一个空格，然后我只需拆分字符串即可获取标记。这样我就遗憾地失去了负数。有什么想法吗？

更新1:经过考虑，我需要一个正则表达式，如果后面没有其他运算符，则将空格放在前面和后面。因此，“2- -2”将转换为“2 - -2”，因为第二个“-”前面有一个“-”，而不是另一个数字。

Answer 1

您的解析代码本质上是循环遍历符号并尝试识别每个标记。表达式处理的“堆栈”部分很复杂，但识别每个标记的方式非常简单。

您需要调整此标记化以使用“状态机”。在每个点，根据机器的当前状态，您期望一组不同的可能的下一个 token 。您使用当前可能的下一个标记集来帮助您识别下一个标记是什么。您成功识别的每个 token 也可能会改变机器的状态。如果下一个标记不能是基于您当前状态的任何可能的标记，则会出现解析错误。

幸运的是，您的情况是最简单的。您可能想要执行以下操作:以 EXPRESSION_EXPECTED 状态开始。您只想读取左括号或数字。如果您读取到单个“数字”，请转至 OPERATOR_EXPECTED 状态。如果您读取左括号，请递归地读取整个内部表达式。当到达右括号时，进入 OPERATOR_EXPECTED 状态。

现在，当您处于 OPERATOR_EXPECTED 状态时，您唯一乐意阅读的就是操作符。一旦你读完，你就会回到EXPRESSION_EXPECTED状态。 (这里的运算符是指二元运算符，而不是一元减号。)

您可以测试此方案，而不必担心负数，并确保您可以解析与代码当前解析的内容相同的内容。

现在，如果您处于 OPERATOR_EXPECTED 中，减号表示“减”，并且是一个运算符。如果您处于 EXPRESSION_EXPECTED 中，则减号表示“减号”，并且是读取数字的第一部分。

这个概念对于解析至关重要。你的问题没有用 BNF(一种描述语法的标准语言)来表达，但 BNF 可以很好地与有限状态机配合使用。关于这些东西还有很多很多的计算机科学理论，其中一些很复杂，但大部分都很容易理解。