支持负数的中缀形式

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' 成为一个有效的表达式。我已经能够为不尊重 whitespace 但不给出负数的表达式编写波兰语形式。我想我可以解决负数的问题，如果他们尊重 whitespaces。我的问题是如果不考虑 whitespaces 并且给出负数，如何实际标记输入表达式。到目前为止，这是我的算法：

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)')

它解决了不遵守 whitespace 规则的非负表达式，因为我制作了 indent_string 方法，该方法在每个运算符之前和之后放置了一个 space 然后我只是拆分字符串以获取标记。这样我可悲地失去了负数。有什么想法吗？

更新 1：考虑到这一点后，如果没有其他运算符在他身后，我需要一个将 whitespaces 放在前面和后面的正则表达式。所以 '2- -2' 会转换为 '2 - -2' 因为第二个 '-' 前面有一个 '-' 而不是另一个数字。

Answer 1

你有解析代码，它基本上循环遍历符号并尝试识别每个标记。 'stack' 表达式处理的部分很复杂，但是您识别每个标记的方式非常简单。

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

幸运的是，您的情况几乎是最简单的。您可能想做这样的事情：从 EXPRESSION_EXPECTED 状态开始。您只想读取左括号或数字。如果你读了一个'number'，进入OPERATOR_EXPECTED状态。如果您读取左括号，请递归读取整个内部表达式。当您到达右括号时，转到 OPERATOR_EXPECTED 状态。

现在，当您处于 OPERATOR_EXPECTED 状态时，您唯一喜欢阅读的就是运算符。一旦你读完一个，你就会回到 EXPRESSION_EXPECTED 状态。（这里的运算符是指二元运算符，而不是一元减号。）

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

现在，如果您在 OPERATOR_EXPECTED 中，减号表示 'subtract' 并且是一个运算符。如果您在 EXPRESSION_EXPECTED 中，减号表示 'minus' 并且是读取数字的第一部分。

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

支持负数的中缀形式

Infix form supporting negative numbers

ruby

infix-notation