在我的计算器解释器中实现运算符优先级

Question

作为学习 Ruby 的一部分，我尝试实现一个基本的解释器，它读取输入并进行基本的算术计算。到目前为止，基本算术运算可以工作，但运算符优先级存在问题。尚未处理。这是代码。我处于初级水平。这段代码中的任何错误都是由于我缺乏知识造成的。如何修改此代码以处理运算符优先级。 示例输出

2+2+2 = 6 #correct
10+10/2 = 10 # incorrect as in irb answer must be 15

该解释器的 Github 存储库

=begin
Basic calculator Interpreter
can add, substract, multiply , divide with any number of operands at a time
Drawback : Lacks operator precedence
=end
class Interpreter   
    attr_accessor :input
    def initialize
        @input = gets.chomp             
    end 
    def intepret        
        first_operand  = []     
        f              = []     
        operator       = '+'        
        array          = Array.new      
        lc             = 0

        @input.split.join.split("").each_with_index.map do |i, index|

            if i.is_number?
                first_operand.push(i)   
                if index == @input.length-1                     
                    array.push(first_operand.join("").to_i)                 
                end
            elsif i.is_plus?                
                f = first_operand
                first_operand = nil
                first_operand = []              
                array.push(f.join("").to_i)
                array.push("+")
            elsif i.is_minus?           
                f = first_operand
                first_operand = nil
                first_operand = []              
                operator = '-'              
                array.push(f.join("").to_i)
                array.push("-")
            elsif i.is_multi?               
                f = first_operand
                first_operand = nil
                first_operand = []              
                operator = '*'              
                array.push(f.join("").to_i)
                array.push("*")
            elsif i.is_divide?              
                f = first_operand
                first_operand = nil
                first_operand = []              
                operator = '/'              
                array.push(f.join("").to_i)
                array.push("/")
            else
                puts "Illegal input exiting.."
                exit            
            end             

            lc = lc+1

        end     
        #apply the appropriate operation on the inputs based on the operand         
        #puts "=======TOKENS======"     
        #puts array.inspect 
        result = 0
        array.each_with_index.map do |x, key|
            result = x if key == 0          
            if x == '+'
                if key == 0 
                    result = add(result, array[key+1])
                else
                    result = add(result, array [key+1])
                end
            elsif x == '-'
                if key == 0 
                    result = minus(result, array[key+1])
                else
                    result = minus(result, array [key+1])
                end
            elsif x == '*'
                if key == 0 
                    result = multi(result, array[key+1])
                else
                    result = multi(result, array [key+1])
                end 
            elsif x == '/'
                begin
                    if key == 0 
                        result = divide(result, array[key+1])
                    else
                        result = divide(result, array [key+1])
                    end 
                rescue
                    puts "Zero Divsion error"
                    exit
                end  
            end 
        end
        puts "Result is: "+result.to_s
    end 
    def print_token(type, value)
        puts type + ' '+ value
    end
    def add(f,s)
        return f.to_i + s.to_i
    end
    def minus(f,s)
        return f.to_i - s.to_i
    end
    def multi(f,s)
        return f.to_i * s.to_i
    end
    def divide(f,s)
        return f.to_i / s.to_i
    end
end
# Override the string class, to directly use methods like obj.is_number? rather than is_number?(obj)
class String
  def is_number?
    true if Float(self) rescue false
  end
  def is_plus?
    true if self == '+' rescue false
  end
  def is_minus?
    true if self == '-' rescue false
  end
  def is_multi?
    true if self == '*' rescue false
  end
  def is_divide?
    true if self == '/' rescue false
  end
end
#continue accepting inputs until exit CTRL + D
while true
    print 'pck>:'
    i_obj = Interpreter.new
    i_obj.intepret
end

Answer 1

首先，使用 Shunting-yard 算法 处理输入。这应该给出一个采用 Reverse Polish notation (RPN) 的标记列表。然后你就可以计算 RPN 表达式了。

Answer 2

我知道这是一个老问题，但它首先出现在谷歌上，并且接受的答案确实没有给我我想要的东西。

我相信原始发帖者正在寻找的东西称为递归体面解析器。基本上实现了一个递归地解决自身问题的解析器。为了理解，让我们看看我们正在尝试做的事情的语法。

EXPR: factor(add|sub factor)*
FACTOR: number

如果我们更新语法，将数字设置为数字或左右括号，我们就可以简单地解决问题：

EXPR: factor(add|sub factor)*
FACTOR: number | lparen expr rparen

这样，如果我们遇到括号，我们只需求解其中的表达式，然后返回其结果。因此我们递归地调用 EXPR。

这里用代码更详细地解释了这一点， 博客：https://ruslanspivak.com/lsbasi-part5/ 代码：https://github.com/rspivak/lsbasi/blob/master/part6/calc6.py#L126-L136